Constraint Programming for Flexible Flow Shop Scheduling Problem with Repeated Jobs and Repeated Operations

• Autorzy: Czerniachowska Kateryna , Wichniarek Radosław , Żywicki Krzysztof

Identyfikatory

DOI

10.12913/22998624/166588

• Języki publikacji: EN

Abstrakty

EN

The manufacturing process relies heavily on production scheduling to guarantee effective production schedules, reduce costs and product shortages, and get away from delays, interruptions, and waste products. Scheduling issues have been effectively solved via constraint programming. In this paper, we consider a constraint programming formulation of the flexible flow shop scheduling problem with repeated jobs and operations repetitions. We also implemented seven fast heuristics and compared the results with the constraint programming solution. The results from using the CPLEX solver as a solution tool were satisfactory. Computational experiments demonstrate that using constraint programming can be significantly more advantageous than using heuristics.

Słowa kluczowe

EN

flexible flow shop scheduling problem; constraint programming; heuristics

• Wydawca: Lublin University of Technology ; Polish Society of Ecological Engineering (PTIE), Branch of PTIE in Lublin
• Czasopismo: Advances in Science and Technology. Research Journal
• Rocznik: 2023
• Tom: Vol. 17, no 3
• Strony: 280--293
• Opis fizyczny: Bibliogr. 29 poz., fig., tab.

Twórcy

autor

Czerniachowska Kateryna

• Wroclaw University of Economics and Business, Wroclaw, Poland

• https://orcid.org/0000-0002-1808-6020

autor

Wichniarek Radosław

• Poznan University of Technology, Poznan, Poland

• https://orcid.org/0000-0003-0714-7462

autor

Żywicki Krzysztof

• Poznan University of Technology, Poznan, Poland

• https://orcid.org/0000-0002-6773-9040

Bibliografia

• 1. Lasi, H., Fettke, P., Kemper, H.G., Feld, T. and Hoffmann, M. (2014). Industry 4.0. Business & Information Systems Engineering, 6, 239–242. DOI: https:// doi.org/10.1007/s12599-014-0334-4
• 2. Teppan, E. (2022). Types of Flexible Job Shop Scheduling: A Constraint Programming Experiment. Proceedings of the 14th International Conference on Agents and Artificial Intelligence, Vol. 3: ICAART, 516–523. https://doi. org/10.5220/0010849900003116
• 3. Yin, Y., Stecke, K.E., and Li, D. (2018). The evolution of production systems from Industry 2.0 through Industry 4.0. International Journal of Production Research, 56(1–2), 848–861. DOI: https:// doi.org/10.1080/00207543.2017.1403664
• 4. Da Col, G. and Teppan, E.C. (2019). Google vs IBM: A constraint solving challenge on the job-shop scheduling problem. Electronic Proceedings in Theoretical Computer Science, EPTCS, 306, 259–265. DOI: https://doi.org/10.4204/EPTCS.306.30
• 5. Delfanti, A. and Frey, B. (2021). Humanly Extended Automation or the Future of Work Seen through Amazon Patents. Science Technology and Human Values, 46(3), 655–682. DOI: https://doi org/10.1177/0162243920943665
• 6. Sparrow, R. and Howard, M. (2017). When human beings are like drunk robots: Driverless vehicles, ethics, and the future of transport. Transportation Research Part C: Emerging Technologies, 80, 206– 215. DOI: https://doi.org/10.1016/j.trc.2017.04.014
• 7. Pinedo, M.L. (2016). Scheduling: Theory, Algorithms, and Systems. NewYork: Prentice-Hall.
• 8. Da Col, G. and Teppan, E.C. (2022). Industrial-size job shop scheduling with constraint programming. Operations Research Perspectives, 9, 100249. DOI: https://doi.org/10.1016/j.orp.2022.100249
• 9. Krystek, J. and Kozik, M. (2012). Analysis of the job shop system with transport and setup times in deadlock-free operating conditions. Archives of Control Sciences, 22(4), 417–425. DOI: https://doi. org/10.2478/v10170-011-0032-0
• 10. Applegate, D. and Cook, W. (1991). Computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3(2), 149–156. DOI: https:// doi.org/10.1287/ijoc.3.2.149
• 11. Rossi, F., Beek, P. van, and Walsh, T. (2006). Handbook of Constraint Programming (Foundations of Artificial Intelligence). In Handbook of Constraint Programming.
• 12. Pinedo, M.L. (2016). Scheduling: Theory, algorithms, and systems, fifth edition. In Scheduling: Theory, Algorithms, and Systems, Fifth Edition. DOI: https://doi.org/10.1007/978-3-319-26580-3
• 13. Zäpfel, G. and Wasner, M. (2000). Heuristic solution concept for a generalized machine sequencing problem with an application to radiator manufacturing. International Journal of Production Economics, 68(2), 199–213. DOI: https://doi.org/10.1016/ S0925-5273(98)00229-1
• 14. Abderrahim, M., Bekrar, A., Trentesaux, D., Aissani, N., and Bouamrane, K. (2022). Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints. Optimization Letters, 16(1), 255–280. DOI: https://doi. org/10.1007/s11590-020-01674-0
• 15. Respen, J., Zufferey, N., and Amaldi, E. (2016). Metaheuristics for a job scheduling problem with smoothing costs relevant for the car industry. Networks, 67(3), 246–261. DOI: https://doi. org/10.1002/net.21656
• 16. Homayouni, S.M. and Fontes, D.B.M.M. (2021). Production and transport scheduling in flexible job shop manufacturing systems. Journal of Global Optimization, 79(2), 463–502. DOI: https://doi. org/10.1007/s10898-021-00992-6
• 17. Beauchemin, M., Ménard, M.-A., Gaudreault, J., Lehoux, N., Agnard, S., and Quimper, C.-G. (2022). Dynamic allocation of human resources: case study in the metal 4.0 manufacturing industry. International Journal of Production Research. DOI: https:// doi.org/10.1080/00207543.2022.2139002
• 18. Moslehi, G. and Mahnam, M. (2011). A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search. International Journal of Production Economics, 129(1), 14–22. DOI: https://doi. org/10.1016/j.ijpe.2010.08.004
• 19. Bautista-Valhondo, J. and Alfaro-Pozo, R. (2020). Mixed integer linear programming models for Flow Shop Scheduling with a demand plan of job types. Central European Journal of Operations Research, Vol. 28, No. 1. DOI: https://doi.org/10.1007/ s10100-018-0553-8
• 20. Jolai, F. and Abedinnia, H. (2013). Consideration of transportation lags in a two-machine flow shop scheduling problem. Scientia Iranica, 20(6), 2215–2223.
• 21. Quadt, D. and Kuhn, H. (2007). A taxonomy of flexible flow line scheduling procedures. European Journal of Operational Research, 178(3), 686–698. DOI: https://doi.org/10.1016/j.ejor.2006.01.042
• 22. Ruiz, R. and Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205(1), 1–18. DOI: https://doi.org/10.1016/j.ejor.2009.09.024
• 23. Hasani, A., Hosseini, S.M.H., and Sana, S.S. (2022). Scheduling in a flexible flow shop with unrelated parallel machines and machine-dependent proces stages: Trade-off between Makespan and production costs. Sustainability Analytics and Modeling, 2, 100010. DOI: ttps://doi.org/10.1016/j. samod.2022.100010
• 24. Ribas, I., Leisten, R., and Framinan, J.M. (2010). Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Computers and Operations Research, 37(8), 1439–1454). DOI: https://doi.org/10.1016/j.cor.2009.11.001
• 25. Eskandari, H. and Hosseinzadeh, A. (2014). A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times. Journal of the Operational Research Society, 65(8), 1221–1231. DOI: https://doi.org/10.1057/jors.2013.70
• 26. Luo, H., Zhang, A., and Huang, G.Q. (2015). Active scheduling for hybrid flowshop with family setup time and inconsistent family formation. Journal of Intelligent Manufacturing, 26(1), 169–187. DOI: https://doi.org/10.1007/s10845-013-0771-9
• 27. De Abreu, L.R., Araújo, K.A.G., de Athayde Prata, B., Nagano, M.S., and Moccellin, J.V. (2022). A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions. Engineering Optimization, 54(9), 1563–1582. DOI: https://doi.org/10.1080/0305215X.2021.1957101
• 28. Roundy, R., Chen, D., Chen, P., Çakanyildirim, M., Freimer, M.B., and Melkonian, V. (2005). Capacity- driven acceptance of customer orders for a multistage batch manufacturing system: Models and algorithms. IIE Transactions (Institute of Industrial Engineers), 37(12), 1093–1105. DOI: https://doi. org/10.1080/07408170500288042
• 29. Kopanos, G.M., Méndez, C.A., and Puigjaner, L. (2010). MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: A benchmark scheduling problem of the pharmaceutical industry. European Journal of Operational Research, 207(2), 644–655. DOI: https://doi.org/10.1016/j.ejor.2010.06.002

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).