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

doi:10.16183/j.cnki.jsjtu.2023.070

上海交通大学学报 ›› 2024, Vol. 58 ›› Issue (8): 1271-1281.doi: 10.16183/j.cnki.jsjtu.2023.070

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

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

上海交通大学机械与动力工程学院,上海 200240

收稿日期:2023-03-02 修回日期:2023-04-21 接受日期:2023-05-12 出版日期:2024-08-28 发布日期:2024-08-27
通讯作者: 刘冉,副教授,博士生导师;E-mail: Liuran2009@sjtu.edu.cn.
作者简介:石亚东(1999-),硕士生,主要研究方向为运筹优化算法设计.
基金资助:
上海市科委“科技创新行动计划”高新技术领域项目(22511103603)

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

SHI Yadong, LIU Ran(), WANG Chengkai, WU Zerui

School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Received:2023-03-02 Revised:2023-04-21 Accepted:2023-05-12 Online:2024-08-28 Published:2024-08-27

摘要/Abstract

摘要：

针对交期随机的批量流车间调度问题,以最小化工件延期期望之和为目标,推导出工件交期符合3类经典随机分布条件下问题目标的闭式计算表达式.建立考虑换模时间与随机交期的问题数学模型,针对模型高度非线性特征对其线性化.设计一种基于逻辑的Benders分解(LBBD)与分枝定界相结合的优化算法,提出两种有效加速策略提升算法求解效率.数值实验结果验证了算法的有效性,通过随机交期与确定交期结果的比较,验证了考虑随机的必要性.

关键词: 随机交期, 批量流, Benders分解, 分枝定界

Abstract:

The lot-streaming flowshop scheduling problem with stochastic due time is addressed in this paper, with the objective of minimizing the sum of expected job delays. Closed-form expressions for the expected delays of jobs are derived under three classical distribution conditions. A mathematical model is then formulated, considering set-up times and stochastic due time. To address the highly nonlinear nature of the model, a linearization is performed. Furthermore, an optimization algorithm is designed using a Logic-based Benders decomposition (LBBD) approach combined with branch-and-bound. Two effective acceleration strategies are introduced to improve the efficiency of the algorithm. The numerical experiments demonstrate the effectiveness of the proposed algorithm, and the necessity of considering stochastic lead times is verified by comparing the results with those obtained from deterministic due time.

Key words: stochastic due time, lot-streaming, Benders decomposition, branch-and-bound

中图分类号:

TH186

石亚东, 刘冉, 王铖恺, 吴泽锐. 基于Benders分解和分枝定界的随机交期批量流流水车间调度[J]. 上海交通大学学报, 2024, 58(8): 1271-1281.

SHI Yadong, LIU Ran, WANG Chengkai, WU Zerui. Stochastic Due-Date Lot-Streaming Flowshop Scheduling with Benders Decomposition and Branch-and-Bound[J]. Journal of Shanghai Jiao Tong University, 2024, 58(8): 1271-1281.

图/表 7

图1

表1

表2

图2

表3

表4

精确求解数值实验结果

算例	分布类型	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

表4

表5

参考文献 18

[1]	GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research, 1976, 1(2): 117-129.
[2]	CHUNG C S, FLYNN J, KIRCA Ö. A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems[J]. European Journal of Operational Research, 2006, 174(1): 1-10.
[3]	GMYS J, MEZMAZ M, MELAB N, et al. A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem[J]. European Journal of Operational Research, 2020, 284(3): 814-833.
[4]	RAD S F. A new ant algorithmic approach for solving PFSP[J]. Iranian Journal of Science and Technology, Transactions A: Science, 2022, 46(1): 181-188.
[5]	黎阳, 李新宇, 牟健慧. 基于改进模拟退火算法的大规模置换流水车间调度[J]. 计算机集成制造系统, 2020, 26(2): 366-375.
	LI Yang, LI Xinyu, MOU Jianhui. Large-scale permutation flowshop scheduling method based on improved simulated annealing algorithm[J]. Computer Integrated Manufacturing Systems, 2020, 26(2): 366-375.
[6]	赵芮, 顾幸生. 求解零空闲流水车间调度问题的离散正弦优化算法[J]. 上海交通大学学报, 2020, 54(12): 1291-1299. doi: 10.16183/j.cnki.jsjtu.2019.321
	ZHAO Rui, GU Xingsheng. A discrete sine optimization algorithm for No-idle flow-shop scheduling problem[J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1291-1299.
[7]	高丽, 周炳海, 杨学良, 等. 基于多规则资源分配的柔性作业车间调度问题多目标集成优化方法[J]. 上海交通大学学报, 2015, 49(8): 1191-1198.
	GAO Li, ZHOU Binghai, YANG Xueliang, et al. A multi-objective integrated optimization method for FJSP based on multi-rule resource allocation[J]. Journal of Shanghai Jiao Tong University, 2015, 49(8): 1191-1198.
[8]	汤洪涛, 王丹南, 邵益平, 等. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213. doi: 10.16183/j.cnki.jsjtu.2020.435
	TANG Hongtao, WANG Dannan, SHAO Yiping, et al. A modified migrating birds optimization for multi-objective lot streaming hybrid flowshop scheduling[J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 201-213.
[9]	CHEN T L, CHENG C Y, CHOU Y H. Multi-objective genetic algorithm for energy-efficient hybrid flow shop scheduling with lot streaming[J]. Annals of Operations Research, 2020, 290(1): 813-836.
[10]	PAN Y X, GAO K Z, LI Z W, et al. Improved meta-heuristics for solving distributed lot-streaming permutation flow shop scheduling problems[J]. IEEE Transactions on Automation Science and Engineering, 2023, 20(1): 361-371.
[11]	SANG H Y, PAN Q K, DUAN P Y, et al. An effective discrete invasive weed optimization algorithm for lot-streaming flowshop scheduling problems[J]. Journal of Intelligent Manufacturing, 2018, 29(6): 1337-1349.
[12]	TSENG C T, LIAO C J. A discrete particle swarm optimization for lot-streaming flowshop scheduling problem[J]. European Journal of Operational Research, 2008, 191(2): 360-373.
[13]	ALFIERI A, GLASS C, VAN DE VELDE S. Two-machine lot streaming with attached setup times[J]. IIE Transactions, 2012, 44(8): 695-710.
[14]	VILLARINHO P A, PANADERO J, PESSOA L S, et al. A simheuristic algorithm for the stochastic permutation flowshop problem with delivery dates and cumulative payoffs[J]. International Transactions in Operational Research, 2021, 28(2): 716-737.
[15]	LIU R, FAN X Y, WU Z R, et al. The physician scheduling of fever clinic in the COVID-19 pandemic[J]. IEEE Transactions on Automation Science and Engineering, 2022, 19(2): 709-723.
[16]	BELZUNCE F, MARTÍNEZ-RIQUELME C, MULERO J. An introduction to stochastic orders[M]. New York, American: Academic Press, 2015.
[17]	NAWAZ M, ENSCORE E E, HAM I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. Omega, 1983, 11(1): 91-95.
[18]	RUIZ R, STÜTZLE T. An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives[J]. European Journal of Operational Research, 2008, 187(3): 1143-1159.

参数符号	含义
k	机器的索引号,k∈{1, 2,…, K}
j, h	工件i, g的子批索引号,j∈{1, 2,…, u_i}, h∈{1, 2,…, u_g}
i, g, n	工件的索引号,i, g, n∈{1, 2,…, N}

决策变量	含义
a_ij	辅助变量,用于顺序记录
r_ij	整数变量,工件i的第j个子批的最小批量个数,可以为0,0≤i≤N, 1≤j≤u_i
t_ijk	连续变量,工件i的第j个子批在机器k上的完工时间, 0≤i≤N, 1≤j≤u_i, 1≤k≤K
y_ij	0-1变量,r_ij>0时,y_ij=1,r_ij=0时,y_ij=0. 0≤i≤N, 1≤j≤u_i
z_ijgh	0-1变量,当工件i的第j个子批和工件g的第h个子批均不为0,且工件i的第j个子批为工件g的第h个子批的紧前子批时,z_ijgh=1;否则,z_ijgh=0. 0≤i≤N, 1≤j≤u_i, 0≤g≤N, 1≤h≤u_g
S_ij	整数变量,工件i的第j个子批的工件数量,0≤i≤N, 1≤j≤u_i

算例	分布	LBBD		企业实际方案					Gap_min/ %	Gurobi			遗传算法
算例	分布	求解结果	时间/s	策略1	策略2	策略3	策略4	时间/s	Gap_min/ %	求解结果	Gap_g/ %	时间/s	求解结果	Gap_c/ %	时间/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

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

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 18

相关文章 2

编辑推荐

Metrics

本文评价

算例	分布类型	交期标准差	结果	分批数
1	N	20	239.8	14
2	N	50	252.9	13
3	N	100	282.6	13
4	N	150	334.6	12
5	U	20	241.4	14
6	U	50	254.2	15
7	U	100	282.4	10
8	U	150	331.1	11

[1]	汤洪涛, 王丹南, 邵益平, 赵文彬, 江伟光, 陈青丰. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213.
[2]	朱奕,杨根科,潘常春. 基于阈值深度优先策略求解非对称旅行商问题的混合分枝定界算法[J]. 上海交通大学学报（自然版）, 2008, 42(10): 1665-1668.