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

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

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

SHI Yadong, LIU Ran, WANG Chengkai, WU Zerui

表5 启发式算法数值实验结果

Tab.5 Numerical experiment results of heuristic algorithm

算例 分布 LBBD 企业实际方案 Gapmin/ % Gurobi 遗传算法 求解 结果 时间/s 策略1 策略2 策略3 策略4 时间/s 求解 结果 Gapg/ % 时间/s 求解 结果 Gapc/ % 时间/s 24 N 1 700 3 600 3 450 3 638 5 188 4 986 <5 50.72 2 066 21.55 3 600 2 905 41.48 3 600 25 N 1 022 3 600 3 981 4 283 5 850 3 525 <5 71.01 1 109 8.51 3 600 2 484 58.86 3 600 26 N 1 608 3 600 4 256 4 390 7 181 5 437 <5 62.22 2 063 28.30 3 600 2 843 43.44 3 600 27 N 502 3 600 2 771 2 639 2 354 2 986 <5 78.68 588 17.19 3 600 2 211 77.31 3 600 28 N 2 039 3 600 5 751 5 545 7 041 7 408 <5 63.23 2 308 13.19 3 600 2 526 19.28 3 600 29 N 2 804 3 600 5 532 5 447 5 111 6 162 <5 45.14 3 045 8.59 3 600 4 412 36.45 3 600 30 E 2 019 3 600 2 752 2 884 4 027 4 813 <5 26.64 2 206 9.26 3 600 2 981 32.27 3 600 31 E 999 3 600 1 873 2 000 2 269 2 876 <5 46.66 1 259 26.03 3 600 1 617 38.22 3 600 32 E 807 3 600 1 023 1 051 1 348 2 348 <5 21.11 1 016 25.90 3 600 1 498 46.13 3 600 33 U 1 301 3 600 2 756 2 756 4 066 5 757 <5 52.79 1 865 43.35 3 600 2 686 51.56 3 600 34 U 2 148 3 600 3 825 3 943 5 119 7 178 <5 43.84 2 486 15.74 3 600 3 645 41.07 3 600 35 U 1 002 3 600 1 881 1 962 2 138 4 807 <5 46.73 1 082 7.98 3 600 2 738 63.40 3 600