基于Benders分解和分枝定界的随机交期批量流流水车间调度

基于Benders分解和分枝定界的随机交期批量流流水车间调度

石亚东, 刘冉, 王铖恺, 吴泽锐

Stochastic Due-Date Lot-Streaming Flowshop Scheduling with Benders Decomposition and Branch-and-Bound

SHI Yadong, LIU Ran, WANG Chengkai, WU Zerui

表4 精确求解数值实验结果

Tab.4 Numerical experiment results of exact algorithm

算例	分布类型	LBBD结合分枝定界					LBBD结合Gurobi				上界 Gap/%
算例	分布类型	上界, $B_{b}^{U}$	下界, $B_{b}^{L}$	Gap_b/%	时间/s		上界, $B_{b}^{U}$	下界, $B_{b}^{L}$	Gap_b/%	时间/s	上界 Gap/%
9	N	73.9	73.9	0	1 575		89.9	43.40	51.60	3600	17.73
10	N	282.5	282.5	0	963		306.3	38.50	87.40	3600	7.77
11	N	397.8	397.8	0	1 378		397.9	67.10	83.10	3600	0.03
12	N	338.7	338.7	0	1 621		380.2	64.00	83.20	3600	10.92
13	N	524.0	524.0	0	1 940		639.1	44.70	93.00	3600	18.01
14	E	400.3	379.2	5.20	3 600		416.5	113.30	72.80	3600	3.90
15	E	471.8	471.8	0	163		478.2	195.80	59.10	3600	1.34
16	E	424.4	420.3	1.00	1 280		434.3	150.70	65.30	3600	2.28
17	E	163.1	161.9	0.70	1 228		181.0	52.30	71.10	3600	9.87
18	E	582.5	578.5	0.70	2 847		674.6	175.40	74.00	3600	13.65
19	U	77.4	77.4	0	2 880		126.7	14.10	88.90	3600	38.91
20	U	96.2	96.2	0	422		110.5	25.70	76.70	3600	12.94
21	U	464.1	464.1	0	2 078		541.3	93.00	82.80	3600	14.26
22	U	47.4	47.4	0	152		47.8	0.06	99.90	3600	0.84
23	U	205.9	205.9	0	948		236.7	12.55	94.70	3600	13.01