估算
分支定界—举例
第3步:可能的方案
方案3-1:{(3), (8)} 方案3-2:{(7)} T31 = 5+3 = 8, S31 = [(46-10-8-8)/10]+3=5 T32 = 6, S31 = [(46-10-8-6)/10]+3=6 选方案3-1进行
估算
分支定界—图示
(1), (2), (5)
(4), (5) (3), (8) (7) (10) (7)
(1), (2), (6)
(3), (5) (4) (7), (5) (3), (9)
(4), (8)
(9), (10)
(10), (11)
(11)
COMSO 2) A为当前所有没有分配的作业集合 3) B为A中从顺序约束的要求的意义上说可选 择的作业集合 4) 如果iB, 且tiT,那么将i置于F, 如果B中没 有任何i能满足, 则T=C 5) 从F中随机选取一个作业i, A=A-i, T=T-ti, 此时,如果A为空,算法停止, 否则转3).
COMSOAL—例子
节拍C=70秒
计算过程
位置排序法
对所有作业i计算它本身和它所有的后续作业 的加工时间的和,记为Pwi, 将Pwi按大小排序 按照排序先后和分配工序。
位置排序法—例
作业
a b
PW
138 118
序号
1 3
作业
g h
PW
102 87
序号
5 7
c
d e f
112
123 85 97
A A A A B B B B i i C C C i i A 0 A A B 0 B B C 0 C C A B