Solving the Distributed Permutation Flow-Shop Scheduling Problem Using Constrained Programming

被引:7
作者
Gogos, Christos [1 ]
机构
[1] Univ Ioannina, Dept Informat & Telecommun, Arta 47100, Greece
来源
APPLIED SCIENCES-BASEL | 2023年 / 13卷 / 23期
关键词
scheduling; constraint programming; heuristics; lower bounds; distributed permutation flow-shop scheduling problem; distributed flow-shop scheduling problem; benchmark dataset; GENETIC ALGORITHM; HEURISTIC METHODS; SEARCH ALGORITHM; MAKESPAN;
D O I
10.3390/app132312562
中图分类号
O6 [化学];
学科分类号
0703 ;
摘要
The permutation flow-shop scheduling problem is a classical problem in scheduling that aims at identifying the optimal sequence of jobs that should be processed in a number of machines in an effort to minimize makespan or some other performance criterion. The distributed permutation flow-shop scheduling problem adds multiple factories where copies of the machines exist and asks for minimizing the makespan on the longest-running location. In this paper, the problem is approached using Constraint Programming and its specialized scheduling features, such as interval variables and non-overlap constraints, while a novel heuristic is proposed for computing lower bounds. Two constraint programming models are proposed: one that solves the Distributed Permutation Flow-shop Scheduling problem, and another one that drops the constraint of processing jobs under the same order for all machines of each factory. The experiments use an extended public dataset of problem instances to validate the approach's effectiveness. In the process, optimality is proved for many problem instances known in the literature but has yet to be proven optimal. Moreover, a high speed of reaching optimal solutions is achieved for many problems, even with moderate big sizes (e.g., seven factories, 20 machines, and 20 jobs). The critical role that the number of jobs plays in the complexity of the problem is identified and discussed. In conclusion, this paper demonstrates the great benefits of scheduling problems that stem from using state-of-the-art constraint programming solvers and models that capture the problem tightly.
引用
收藏
页数:26
相关论文
共 33 条
[1]  
Alaghebandha M., 2019, J Optim Ind Eng, V12, P103, DOI 10.22094/JOIE.2018.542997.1510
[2]   Fast Approximation for Scheduling One Machine [J].
Alonso-Pecina, Federico ;
Alberto Hernandez, Jose ;
Maria Sigarreta, Jose ;
Vakhania, Nodari .
MATHEMATICS, 2020, 8 (09)
[3]   Distributed shop scheduling: A comprehensive review on classifications, models and algorithms [J].
Duan, Jianguo ;
Wang, Mengting ;
Zhang, Qinglei ;
Qin, Jiyun .
MATHEMATICAL BIOSCIENCES AND ENGINEERING, 2023, 20 (08) :15265-15308
[4]   A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem [J].
Fernandez-Viagas, Victor ;
Framinan, Jose M. .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2015, 53 (04) :1111-1123
[5]   A review and classification of heuristics for permutation flow-shop scheduling with makespan objective [J].
Framinan, JM ;
Gupta, JND ;
Leisten, R .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2004, 55 (12) :1243-1255
[6]   An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem [J].
Gao, Jian ;
Chen, Rong ;
Deng, Wu .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2013, 51 (03) :641-651
[7]  
Gao J, 2011, INT J COMPUT INT SYS, V4, P497
[8]  
Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
[9]  
Gavranovic Haris., 2012, ENDM, P209, DOI [10.1016/j.endm.2012.10.028, DOI 10.1016/J.ENDM.2012.10.028]
[10]   Scheduling independent tasks on heterogeneous processors using heuristics and Column Pricing [J].
Gogos, Christos ;
Valouxis, Christos ;
Alefragis, Panayiotis ;
Goulas, George ;
Voros, Nikolaos ;
Housos, Efthymios .
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2016, 60 :48-66