Journal of Shanghai Jiao Tong University

Journal of Shanghai Jiaotong University >

2024 , Vol. 58 >Issue 8: 1271 - 1281

DOI: https://doi.org/10.16183/j.cnki.jsjtu.2023.070

Mechanical Engineering

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

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

Received date: 2023-03-02

  Revised date: 2023-04-21

  Accepted date: 2023-05-12

  Online published: 2023-05-19

Fold

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

Cite this article

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 Jiaotong University, 2024 , 58(8) : 1271 -1281 . DOI: 10.16183/j.cnki.jsjtu.2023.070

References

[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.
  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.
  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.
Options
Outlines

/

〈 〉