journal article·2023-11-21Open access

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

Christos Gogos

Applied Sciences· Volume 13· Issue 23

Abstract

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.
Source: crossref · Quality: baseline

Research context

OpenAlex topics: Scheduling and Optimization Algorithms · Assembly Line Balancing Optimization · Advanced Manufacturing and Logistics Optimization

SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.

Affiliations

Department of Informatics and Telecommunications, University of Ioannina, 47100 Arta, Greece

References (33)

Show source-provided references
1. The distributed permutation flowshop scheduling problem10.1016/j.cor.2009.06.019 ↗
2. Optimization and approximation in deterministic sequencing and scheduling: A survey10.1016/S0167-5060(08)70356-X ↗
3. The complexity of flowshop and jobshop scheduling10.1287/moor.1.2.117 ↗
4. Benchmarks for basic scheduling problems10.1016/0377-2217(93)90182-M ↗
5. Pinedo, M.L. (2022). Scheduling, Springer International Publishing.10.1007/978-3-031-05921-6 ↗
6. Optimal two-and three-stage production schedules with setup times included10.1002/nav.3800010110 ↗
7. Flowshop scheduling/sequencing research: A statistical review of the literature, 1952–199410.1109/17.618173 ↗
8. Flowshop scheduling research after five decades10.1016/j.ejor.2005.02.001 ↗
9. Improved genetic algorithm for the permutation flowshop scheduling problem10.1016/S0305-0548(03)00016-9 ↗
10. A review and classification of heuristics for permutation flow-shop scheduling with makespan objective10.1057/palgrave.jors.2601784 ↗
11. Addressing the gap in scheduling research: A review of optimization and heuristic methods in production scheduling10.1080/00207549308956713 ↗
12. A scatter search algorithm for the distributed permutation flowshop scheduling problem10.1016/j.ejor.2014.05.024 ↗
13. Iterated Greedy methods for the distributed permutation flowshop scheduling problem10.1016/j.omega.2018.03.004 ↗
14. Perez-Gonzalez, P., and Framinan, J.M. (2023). A review and classification on distributed permutation flowshop scheduling problems. Eur. J. Oper. Res.10.1016/j.ejor.2023.02.001 ↗
15. Distributed shop scheduling: A comprehensive review on classifications, models and algorithms10.3934/mbe.2023683 ↗
16. Liu, H., and Gao, L. (2010, January 13–15). A discrete electromagnetism-like mechanism algorithm for solving distributed permutation flowshop scheduling problem. Proceedings of the 2010 International Conference on Manufacturing Automation, Hong Kong, China.10.1109/ICMA.2010.17 ↗
17. A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem
18. Solving multi-factory flowshop problems with a novel variable neighbourhood descent algorithm
19. An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem10.1080/00207543.2011.644819 ↗
20. Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm10.1080/00207543.2013.790571 ↗
21. An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem10.1080/0305215X.2013.827673 ↗
22. A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem10.1080/00207543.2014.948578 ↗
23. An effective Benders decomposition algorithm for solving the distributed permutation flowshop scheduling problem10.1016/j.cor.2020.105006 ↗
24. Effective heuristics and metaheuristics to minimise total tardiness for the distributed permutation flowshop scheduling problem10.1080/00207543.2020.1837982 ↗
25. Economic lot sizing and scheduling in distributed permutation flow shops
26. Scheduling independent tasks on heterogeneous processors using heuristics and Column Pricing10.1016/j.future.2016.01.016 ↗
27. Variable neighborhood search for google machine reassignment problem10.1016/j.endm.2012.10.028 ↗
28. Valouxis, C., Gogos, C., Dimitsas, A., Potikas, P., and Vittas, A. (2022). A Hybrid Exact–Local Search Approach for One-Machine Scheduling with Time-Dependent Capacity. Algorithms, 15.10.3390/a15120450 ↗
29. Alonso-Pecina, F., Hernández, J.A., Sigarreta, J.M., and Vakhania, N. (2020). Fast approximation for scheduling one machine. Mathematics, 8.10.3390/math8091524 ↗
30. Perron, L., and Didier, F. (2023, October 15). Google’s ORTools CP-SAT. Available online: https://developers.google.com/optimization/cp/cp_solver.
31. A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime10.1016/j.cor.2012.05.018 ↗
32. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem10.1016/0305-0483(83)90088-9 ↗
33. Some efficient heuristic methods for the flow shop sequencing problem10.1016/0377-2217(90)90090-X ↗