Solving the Distributed Permutation Flow-Shop Scheduling Problem Using Constrained Programming
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 schedu...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-11-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/13/23/12562 |
| _version_ | 1827592557812514816 |
|---|---|
| author | Christos Gogos |
| author_facet | Christos Gogos |
| author_sort | Christos Gogos |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T01:56:14Z |
| format | Article |
| id | doaj.art-e588a6a51abc4ddab5fc8b511e96a5db |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-09T01:56:14Z |
| publishDate | 2023-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-e588a6a51abc4ddab5fc8b511e96a5db2023-12-08T15:10:59ZengMDPI AGApplied Sciences2076-34172023-11-0113231256210.3390/app132312562Solving the Distributed Permutation Flow-Shop Scheduling Problem Using Constrained ProgrammingChristos Gogos0Department of Informatics and Telecommunications, University of Ioannina, 47100 Arta, GreeceThe 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.https://www.mdpi.com/2076-3417/13/23/12562schedulingconstraint programmingheuristicslower boundsdistributed permutation flow-shop scheduling problemdistributed flow-shop scheduling problem |
| spellingShingle | Christos Gogos Solving the Distributed Permutation Flow-Shop Scheduling Problem Using Constrained Programming Applied Sciences scheduling constraint programming heuristics lower bounds distributed permutation flow-shop scheduling problem distributed flow-shop scheduling problem |
| title | Solving the Distributed Permutation Flow-Shop Scheduling Problem Using Constrained Programming |
| title_full | Solving the Distributed Permutation Flow-Shop Scheduling Problem Using Constrained Programming |
| title_fullStr | Solving the Distributed Permutation Flow-Shop Scheduling Problem Using Constrained Programming |
| title_full_unstemmed | Solving the Distributed Permutation Flow-Shop Scheduling Problem Using Constrained Programming |
| title_short | Solving the Distributed Permutation Flow-Shop Scheduling Problem Using Constrained Programming |
| title_sort | solving the distributed permutation flow shop scheduling problem using constrained programming |
| topic | scheduling constraint programming heuristics lower bounds distributed permutation flow-shop scheduling problem distributed flow-shop scheduling problem |
| url | https://www.mdpi.com/2076-3417/13/23/12562 |
| work_keys_str_mv | AT christosgogos solvingthedistributedpermutationflowshopschedulingproblemusingconstrainedprogramming |