Document Open Access Logo

The Hybrid Flexible Flowshop with Transportation Times

Authors Eddie Armstrong, Michele Garraffa, Barry O'Sullivan, Helmut Simonis

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.16.pdf
  • Filesize: 0.83 MB
  • 18 pages

Document Identifiers

Author Details

Eddie Armstrong
  • Johnson & Johnson Research Centre, Limerick, Ireland
Michele Garraffa
  • Confirm SFI Research Centre for Smart Manufacturing, Limerick, Ireland
  • School of Computer Science, University College Cork, Ireland
Barry O'Sullivan
  • Confirm SFI Research Centre for Smart Manufacturing, Limerick, Ireland
  • School of Computer Science, University College Cork, Ireland
Helmut Simonis
  • Confirm SFI Research Centre for Smart Manufacturing, Limerick, Ireland
  • School of Computer Science, University College Cork, Ireland

Funding

This project has received funding from a research grant from Science Foundation Ireland (SFI) under Grant Number 16/RC/3918.

Cite AsGet BibTex

Eddie Armstrong, Michele Garraffa, Barry O'Sullivan, and Helmut Simonis. The Hybrid Flexible Flowshop with Transportation Times. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.16

Abstract

This paper presents the hybrid, flexible flowshop problem with transportation times between stages, which is an extension of an existing scheduling problem that is well-studied in the literature. We explore different models for the problem with Constraint Programming, MILP, and local search, and compare them on generated benchmark problems that reflect the problem of the industrial partner. We then study two different factory layout design problems, and use the optimization tool to understand the impact of the design choices on the solution quality.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Constraints
  • Computing methodologies → Planning and scheduling
Keywords
  • Constraint Programming
  • scheduling
  • hybrid flowshop

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Leonard Adler, Nelson Fraiman, Edward Kobacker, Michael Pinedo, Juan Carlos Plotnicoff, and Tso Pang Wu. BPSS: A scheduling support system for the packaging industry. Operations Research, 41(4):641-648, 1993. URL: https://doi.org/10.1287/opre.41.4.641.
  2. Abder Aggoun and Nicolas Beldiceanu. Extending CHIP in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling, 17:57–73, 1993. URL: https://doi.org/10.1016/0895-7177(93)90068-A.
  3. Fardin Ahmadizar and Parmis Shahmaleki. Group-shop scheduling with sequence-dependent set-up and transportation times. Applied Mathematical Modelling, 38(21):50805091, 2014. URL: https://doi.org/10.1016/j.apm.2014.03.035.
  4. Miguel F. Anjos and Manuel V.C. Vieira. Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions. European Journal of Operational Research, 261(1):1-16, 2017. URL: https://doi.org/10.1016/j.ejor.2017.01.049.
  5. Farhad Azadivar and John(Jian) Wang. Facility layout optimization using simulation and genetic algorithms. International Journal of Production Research, 38(17):4369-4383, 2000. URL: https://doi.org/10.1080/00207540050205154.
  6. Javad Behnamian, Seyyed Mohammad Taghi Fatemi Ghomi, Fariborz Jolai, and Omid Amirtaheri. Realistic two-stage flowshop batch scheduling problems with transportation capacity and times. Applied Mathematical Modelling, 36(2):723735, 2012. URL: https://doi.org/10.1016/j.apm.2011.07.011.
  7. Nicolas Beldiceanu and Evelyne Contejean. Introducing Global Constraints in CHIP. Mathematical and Computer Modelling, 20(12):97-123, 1994. URL: https://doi.org/10.1016/0895-7177(94)90127-9.
  8. Fehmi Burcin Ozsoydan and Müjgan Sağir. Iterated greedy algorithms enhanced by hyper-heuristic based learning for hybrid flexible flowshop scheduling problem with sequence dependent setup times: A case study at a manufacturing plant. Computers & Operations Research, 125:105044, 2021. URL: https://doi.org/10.1016/j.cor.2020.105044.
  9. Mats Carlsson and Per Mildner. SICStus Prolog-the first 25 years. Theory and Practice of Logic Programming, 12(1-2):35–66, 2012. URL: https://doi.org/10.1017/S1471068411000482.
  10. Hyun-Seon Choi, Ji-Su Kim, and Dong-Ho Lee. Real-time scheduling for reentrant hybrid flow shops: A decision tree based mechanism and its application to a TFT-LCD line. Expert Systems with Applications, 38(4):3514-3521, 2011. URL: https://doi.org/10.1016/j.eswa.2010.08.139.
  11. Geoffrey Chu. Improving Combinatorial Optimization. PhD thesis, The University of Melbourne, 2011. Google Scholar
  12. Mehmet Dincbas, Pascal Van Hentenryck, Helmut Simonis, Abderrahmane Aggoun, Thomas Graf, and Françoise Berthier. The constraint logic programming language CHIP. In Proceedings of the International Conference on Fifth Generation Computer Systems, FGCS 1988, Tokyo, Japan, November 28-December 2, 1988, pages 693-702. OHMSHA Ltd. Tokyo and Springer-Verlag, 1988. Google Scholar
  13. Housni Djellab and Khaled Djellab. Preemptive hybrid flowshop scheduling problem of interval orders. European Journal of Operational Research, 137(1):37-49, 2002. URL: https://doi.org/10.1016/S0377-2217(01)00094-7.
  14. Amine Drira, Henri Pierreval, and Sonia Hajri-Gabouj. Facility layout problems: A survey. Annual Reviews in Control, 31(2):255-267, 2007. URL: https://doi.org/10.1016/j.arcontrol.2007.04.001.
  15. Atabak Elmi and Seyda Topaloglu. Scheduling multiple parts in hybrid flow shop robotic cells served by a single robot. International Journal of Computer Integrated Manufacturing, 27(12):11441159, 2014. URL: https://doi.org/10.1080/0951192X.2013.874576.
  16. Atabak Elmi and Seyda Topaloglu. Multi-degree cyclic flow shop robotic cell scheduling problem: Ant colony optimization. Computers & Operations Research, 73:67-83, 2016. URL: https://doi.org/10.1016/j.cor.2016.03.007.
  17. Atabak Elmi and Seyda Topaloglu. Multi-degree cyclic flow shop robotic cell scheduling problem with multiple robots. International Journal of Computer Integrated Manufacturing, 30(8):805-821, 2017. URL: https://doi.org/10.1080/0951192X.2016.1210231.
  18. Thibaut Feydy, Adrian Goldwaser, Andreas Schutt, Peter Stuckey, and Kenneth Young. Priority search with MiniZinc. In ModRef 2017: The Sixteenth International Workshop on Constraint Modelling and Reformulation, 2017. Google Scholar
  19. Erik Flores Garcia, Enrique Ruiz Zúñiga, Jessica Bruch, Matias Urenda Moris, and Anna Syberfeldt. Simulation-based optimization for facility layout design in conditions of high uncertainty. Procedia CIRP, 72:334-339, 2018. 51st CIRP Conference on Manufacturing Systems. URL: https://doi.org/10.1016/j.procir.2018.03.227.
  20. Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1979. Google Scholar
  21. Ronald Graham, Eugene Lawler, Jan Karel Lenstra, and Alexander H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5:287-326, 1979. URL: https://doi.org/10.1016/S0167-5060(08)70356-X.
  22. Alain Guinet. Textile production systems: a succession of non-identical parallel processor shops. Journal of the Operational Research Society, 42(8):655-671, 1991. URL: https://doi.org/10.1057/jors.1991.132.
  23. Mohamed Haouari and Lotfi Hidri. On the hybrid flowshop scheduling problem. International Journal of Production Economics, 113:495497, May 2008. URL: https://doi.org/10.1016/j.ijpe.2007.10.007.
  24. Lofti Hidri, Saneur Elkosantini, and Mohammed M. Mabkhot. Exact and heuristic procedures for the two-center hybrid flow shop scheduling problem with transportation times. IEEE Access, 6:21788-21801, 2018. URL: https://doi.org/10.1109/ACCESS.2018.2826069.
  25. Zhihong Jin, Katsuhisa Ohno, Takahiro Ito, and Salah E. Elmaghraby. Scheduling hybrid flowshops in printed circuit board assembly lines. Production and Operations Management, 11(2):216-230, 2002. URL: https://doi.org/10.1111/j.1937-5956.2002.tb00492.x.
  26. Antoine Jouglet, Ceyda Oğuz, and Marc Sevaux. Hybrid flow-shop: a memetic algorithm using constraint-based scheduling for efficient search. Journal of Mathematical Modelling and Algorithms, 8(3):271-292, 2009. URL: https://doi.org/10.1007/s10852-008-9101-1.
  27. Wen-Yang Ku and Christopher Beck. Mixed integer programming models for job shop scheduling: A computational analysis. Computers & Operations Research, 73:165-173, 2016. URL: https://doi.org/10.1016/j.cor.2016.04.006.
  28. Philippe Laborie, Jérôme Rogerie, Paul Shaw, and Petr Vilím. IBM ILOG CP optimizer for scheduling. Constraints, 23(2):210–250, 2018. URL: https://doi.org/10.1007/s10601-018-9281-x.
  29. Michael Langston. Interstage transportation planning in the deterministic flowshop environment. Operations Research, 35(4):556-564, 1987. URL: https://doi.org/10.1287/opre.35.4.556.
  30. Chuanjin Lei, Ning Zhao, Song Ye, and Xiuli Wu. Memetic algorithm for solving flexible flow-shop scheduling problems with dynamic transport waiting times. Computers & Industrial Engineering, 139:105984, 2020. URL: https://doi.org/10.1016/j.cie.2019.07.041.
  31. P.L. Maggu and G. Das. On 2×n sequencing problem with transportaion times of jobs. Pure and Applied Mathematika Sciences, 12:16, 1980. Google Scholar
  32. Byungsoo Na, Shabbir Ahmed, George Nemhauser, and Joel Sokol. A cutting and scheduling problem in float glass manufacturing. Journal of Scheduling, 17(1):95-107, 2014. URL: https://doi.org/10.1007/s10951-013-0335-z.
  33. Bahman Naderi, Sheida Gohari, and Mehdi Yazdani. Hybrid flexible flowshop problems: Models and solution methods. Applied Mathematical Modelling, 38(24):5767-5780, 2014. URL: https://doi.org/10.1016/j.apm.2014.04.012.
  34. Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, and Guido Tack. MiniZinc: Towards a standard CP modelling language. In Christian Bessiere, editor, Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, Providence, RI, USA, September 23-27, 2007, Proceedings, volume 4741 of Lecture Notes in Computer Science, pages 529-543. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74970-7_38.
  35. Andrea Rossi. Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships. International Journal of Production Economics, 153(C):253-267, 2014. URL: https://doi.org/10.1016/j.ijpe.2014.03.006.
  36. Rubén Ruiz and José Antonio Vázquez Rodríguez. The hybrid flow shop scheduling problem. European Journal of Operational Research, 205:1-18, 2010. URL: https://doi.org/10.1016/j.ejor.2009.09.024.
  37. Rubén Ruiz, Funda Sivrikaya Şerifoğlu, and Thijs Urlings. Modeling realistic hybrid flexible flowshop scheduling problems. Computers & Operations Research, 35(4):11511175, 2008. URL: https://doi.org/10.1016/j.cor.2006.07.014.
  38. Helmut Simonis, Michele Garraffa, Barry O'Sullivan, and Eddie Armstrong. Dataset for Article: Hybrid Flexible Flowshop with Transportation Times at CP 2021, August 2021. URL: https://doi.org/10.5281/zenodo.5168966.
  39. Ricardo Soto, Hakan Kjellerstrand, Juan Gutiérrez, Alexis López, Broderick Crawford, and Eric Monfroy. Solving manufacturing cell design problems using constraint programming. In He Jiang, Wei Ding, Moonis Ali, and Xindong Wu, editors, Advanced Research in Applied Artificial Intelligence, pages 400-406, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  40. Ömür Tosun, Mariappan Kadarkarainadar Marichelvam, and Nedret Tosun. A literature review on hybrid flow shop scheduling. International Journal of Advanced Operations Management, 12(2):156194, 2020. URL: https://doi.org/10.1504/ijaom.2020.108263.
  41. Srisatja Vitayasak, Pupong Pongcharoen, and Christian Hicks. Robust machine layout design under dynamic environment:dynamic customer demand and machine maintenance. Expert Systems with Applications, 3:100015, 2019. URL: https://doi.org/10.1016/j.eswax.2019.100015.
  42. Hua Xuan. Hybrid flowshop scheduling with finite transportation capacity. Applied Mechanics and Materials, 65:574578, 2011. URL: https://doi.org/10.4028/www.scientific.net/amm.65.574.
  43. Sami Yamani Douzi Sorkhabi, David Romero, Christopher Beck, and Cristina Amon. Constrained multi-objective wind farm layout optimization: Novel constraint handling approach based on constraint programming. Renewable Energy, 126:341-353, 2018. URL: https://doi.org/10.1016/j.renene.2018.03.053.
  44. Weiya Zhong and Zhi-Long Chen. Flowshop scheduling with interstage job transportation. Journal of Scheduling, 18(4):411-422, 2015. URL: https://doi.org/10.1007/s10951-014-0409-6.
  45. Jinlian Zhou, Ying Guo, and Guipeng Li. On complex hybrid flexible flowshop scheduling problems based on constraint programming. In 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), pages 909-913, 2015. URL: https://doi.org/10.1109/fskd.2015.7382064.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact