Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings

被引:6
作者
Idzikowski, Radoslaw [1 ]
Rudy, Jaroslaw [2 ]
Gnatowski, Andrzej [1 ]
机构
[1] Wroclaw Univ Sci & Technol, Dept Control Syst & Mechatron, PL-50370 Wroclaw, Poland
[2] Wroclaw Univ Sci & Technol, Dept Comp Engn, PL-50370 Wroclaw, Poland
来源
APPLIED SCIENCES-BASEL | 2021年 / 11卷 / 10期
关键词
flow shop; scheduling; time couplings; limited-idle; elimination properties; metaheuristics; tabu search; NONDOMINATED SORTING APPROACH; DEPENDENT SETUP TIMES; OPTIMIZATION ALGORITHM; EVOLUTIONARY ALGORITHMS; GENETIC ALGORITHM; SEARCH ALGORITHM; BOUND ALGORITHM; MACHINE; MAKESPAN;
D O I
10.3390/app11104425
中图分类号
O6 [化学];
学科分类号
0703 ;
摘要
In this paper, a non-permutation variant of the Flow Shop Scheduling Problem with Time Couplings and makespan minimization is considered. Time couplings are defined as machine minimum and maximum idle time allowed. The problem is inspired by the concreting process encountered in industry. The mathematical model of the problem and solution graph representation are presented. Several problem properties are formulated, including the time complexity of the goal function computation and block elimination property. Three solving methods, an exact Branch and Bound algorithm, the Tabu Search metaheuristic, and a baseline Genetic Algorithm metaheuristic, are proposed. Experiments using Taillard-based problem instances are performed. Results show that, for the Tabu Search method, the neighborhood based on the proposed block property outperforms other neighborhoods and the Genetic Algorithm under the same time limit. Moreover, the Tabu Search method provided high quality solutions, with the gap to the optimal solution for the smaller instances not exceeding 2.3%.
引用
收藏
页数:18
相关论文
共 45 条
[1]   The Non-Permutation Flow-Shop scheduling problem: A literature review [J].
Alejandro Rossit, Daniel ;
Tohme, Fernando ;
Frutos, Mariano .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2018, 77 :143-153
[2]   Multi-objective green flowshop scheduling problem under uncertainty: Estimation of distribution algorithm [J].
Amiri, M. Faraji ;
Behnamian, J. .
JOURNAL OF CLEANER PRODUCTION, 2020, 251
[3]   Minimizing flowtime in a flowshop scheduling problem with a biased random-key genetic algorithm [J].
Andrade, Carlos E. ;
Silva, Thuener ;
Pessoa, Luciana S. .
EXPERT SYSTEMS WITH APPLICATIONS, 2019, 128 :67-80
[4]  
Boejko W., 2020, MODELLING PERFORMANC, P31, DOI [10.1007/978-3-030-27652-2_2, DOI 10.1007/978-3-030-27652-2_2]
[5]  
Boejko W., 2021, PERFORMANCE EVALUATI, P1, DOI [10.1007/978-3-030-67063-4_1, DOI 10.1007/978-3-030-67063-4_1]
[6]   Data-driven Algorithm for Scheduling with Total Tardiness [J].
Bouska, Michal ;
Novak, Antonin ;
Sucha, Premysl ;
Modos, Istvan ;
Hanzalek, Zdenek .
PROCEEDINGS OF THE 9TH INTERNATIONAL CONFERENCE ON OPERATIONS RESEARCH AND ENTERPRISE SYSTEMS (ICORES), 2020, :59-68
[7]  
Bozejko Wojciech, 2020, Engineering in Dependability of Computer Systems and Networks. Proceedings of the Fourteenth International Conference on Dependability of Computer Systems DepCoS-RELCOMEX. Advances in Intelligent Systems and Computing (AISC 987), P80, DOI 10.1007/978-3-030-19501-4_8
[8]   Cyclic flow shop scheduling problem with two-machine cells [J].
Bozejko, Wojciech ;
Gnatowski, Andrzej ;
Idzikowski, Radoslaw ;
Wodecki, Mieczyslaw .
ARCHIVES OF CONTROL SCIENCES, 2017, 27 (02) :151-167
[9]   Cyclic hybrid flow-shop scheduling problem with machine setups [J].
Bozejko, Wojciech ;
Gniewkowski, Lukasz ;
Pempera, Jaroslaw ;
Wodecki, Mieczyslaw .
2014 INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE, 2014, 29 :2127-2136
[10]   A BRANCH-AND-BOUND ALGORITHM FOR THE JOB-SHOP SCHEDULING PROBLEM [J].
BRUCKER, P ;
JURISCH, B ;
SIEVERS, B .
DISCRETE APPLIED MATHEMATICS, 1994, 49 (1-3) :107-127