Research on two-machine flow shop scheduling problem with release dates and truncated learning effects

被引：19
作者：
Lv, Dan-Yang [1 ,2 ]
Wang, Ji-Bo [1 ,2 ]
机构：
[1] Shenyang Aerosp Univ, Sch Mechatron Engn, Shenyang, Peoples R China
[2] Shenyang Aerosp Univ, Minist Educ, Lab Rapid Dev & Mfg Technol Aircraft, Shenyang, Peoples R China
来源：
ENGINEERING OPTIMIZATION | 2025年 / 57卷 / 07期
关键词：
Scheduling; release date; truncated learning effect; flow shop; dominance condition; SINGLE-MACHINE; MINIMIZE;
D O I：
10.1080/0305215X.2024.2372633
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
In this article, a two-machine flow shop scheduling problem with release dates and truncated learning effects is studied. The objective is to find a sequence such that the total completion time is minimized. This problem is NP-hard and cannot be solved in polynomial time. Therefore, a branch-and-bound algorithm (dominance conditions, lower bounds and an upper bound are needed) and an heuristic algorithm are proposed. In addition, simulated annealing and tabu search are developed to obtain near-optimal solutions for the problem. A large number of computational tests have been conducted, and the data show that the branch-and-bound algorithm can handle small-sized problems effectively within 14 jobs, while the proposed heuristic algorithm has a shorter running time for large-sized problems.
引用
收藏
页码：1828 / 1848
页数：21
相关论文
共 52 条
[1]   A Modified Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem [J].
Al Aqel, Ghiath ;
Li, Xinyu ;
Gao, Liang .
CHINESE JOURNAL OF MECHANICAL ENGINEERING, 2019, 32 (01)
[2]   Scheduling problems under learning effects: classification and cartography [J].
Azzouz, Ameni ;
Ennigrou, Meriem ;
Ben Said, Lamjed .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2018, 56 (04) :1642-1661
[3]   Effective algorithms for single-machine learning-effect scheduling to minimize completion-time-based criteria with release dates [J].
Bai, Danyu ;
Xue, Hanyu ;
Wang, Ling ;
Wu, Chin-Chia ;
Lin, Win-Chin ;
Abdulkadir, Danladi H. .
EXPERT SYSTEMS WITH APPLICATIONS, 2020, 156
[4]   Flow shop learning effect scheduling problem with release dates [J].
Bai, Danyu ;
Tang, Mengqian ;
Zhang, Zhi-Hai ;
Santibanez-Gonzalez, Ernesto D. R. .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2018, 78 :21-38
[5]   Permutation flow shop scheduling problem to minimize nonlinear objective function with release dates [J].
Bai, Danyu ;
Liang, Jianheng ;
Liu, Bingqian ;
Tang, Mengqian ;
Zhang, Zhi-Hai .
COMPUTERS & INDUSTRIAL ENGINEERING, 2017, 112 :336-347
[6]   Two-machine flow shop scheduling with a common due date to maximize total early work [J].
Chen, Xin ;
Miao, Qian ;
Lin, Bertrand M. T. ;
Sterna, Malgorzata ;
Blazewicz, Jacek .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 300 (02) :504-511
[7]  
Dutta D., 2022, INFOR, V60, P109, DOI [https://doi.org/10.1080/03155986.2020.1807243, DOI 10.1080/03155986.2020.1807243]
[8]  
Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
[9]   Anomalies in Special Permutation Flow Shop Scheduling Problems [J].
Gui, Lin ;
Gao, Liang ;
Li, Xinyu .
CHINESE JOURNAL OF MECHANICAL ENGINEERING, 2020, 33 (01)
[10]   Discrete evolutionary multi-objective optimization for energy-efficient blocking flow shop scheduling with setup time [J].
Han, Yuyan ;
Li, Junqing ;
Sang, Hongyan ;
Liu, Yiping ;
Gao, Kaizhou ;
Pan, Quanke .
APPLIED SOFT COMPUTING, 2020, 93
123456