Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
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 mathem...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-05-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/11/10/4425 |
| _version_ | 1797534257489379328 |
|---|---|
| author | Radosław Idzikowski Jarosław Rudy Andrzej Gnatowski |
| author_facet | Radosław Idzikowski Jarosław Rudy Andrzej Gnatowski |
| author_sort | Radosław Idzikowski |
| collection | DOAJ |
| description | 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%. |
| first_indexed | 2024-03-10T11:27:56Z |
| format | Article |
| id | doaj.art-9f479a6c3dc94ec091a01b0ea898a272 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T11:27:56Z |
| publishDate | 2021-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-9f479a6c3dc94ec091a01b0ea898a2722023-11-21T19:31:55ZengMDPI AGApplied Sciences2076-34172021-05-011110442510.3390/app11104425Solving Non-Permutation Flow Shop Scheduling Problem with Time CouplingsRadosław Idzikowski0Jarosław Rudy1Andrzej Gnatowski2Department of Control Systems and Mechatronics, Wrocław University of Science and Technology, 50-370 Wrocław, PolandDepartment of Computer Engineering, Wrocław University of Science and Technology, 50-370 Wrocław, PolandDepartment of Control Systems and Mechatronics, Wrocław University of Science and Technology, 50-370 Wrocław, PolandIn 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%.https://www.mdpi.com/2076-3417/11/10/4425flow shopschedulingtime couplingslimited-idleelimination propertiesmetaheuristics |
| spellingShingle | Radosław Idzikowski Jarosław Rudy Andrzej Gnatowski Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings Applied Sciences flow shop scheduling time couplings limited-idle elimination properties metaheuristics |
| title | Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings |
| title_full | Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings |
| title_fullStr | Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings |
| title_full_unstemmed | Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings |
| title_short | Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings |
| title_sort | solving non permutation flow shop scheduling problem with time couplings |
| topic | flow shop scheduling time couplings limited-idle elimination properties metaheuristics |
| url | https://www.mdpi.com/2076-3417/11/10/4425 |
| work_keys_str_mv | AT radosławidzikowski solvingnonpermutationflowshopschedulingproblemwithtimecouplings AT jarosławrudy solvingnonpermutationflowshopschedulingproblemwithtimecouplings AT andrzejgnatowski solvingnonpermutationflowshopschedulingproblemwithtimecouplings |