Makespan Minimisation in Hybrid Flexible Flowshops with Buffers and Machine-Dependent Transportation Times | SpringerLink
Skip to main content
Springer Nature Link
Log in

Makespan Minimisation in Hybrid Flexible Flowshops with Buffers and Machine-Dependent Transportation Times

  • Conference paper
  • First Online:
Advances in Production Management Systems. Production Management Systems for Volatile, Uncertain, Complex, and Ambiguous Environments (APMS 2024)

Part of the book series: IFIP Advances in Information and Communication Technology ((IFIPAICT,volume 733))

  • 478 Accesses

Abstract

Hybrid Flexible Flowshop Scheduling (HFFS) is the problem where a set of jobs must be processed in a given sequence of stages and each stage has a set of (typically identical) parallel machines. The flexibility of HFFS allows a job to skip some stages. Modern production environments, e.g., assembly lines, exhibit additional structure, namely limited-capacity buffers and transportation times between subsequent stages, while the layout also imposes that such times are machine-to-machine dependent. We propose two formal models, namely a Mixed-Integer Linear Program (MILP) that incorporates transportation times but not buffers and a Constraint Program (CP) that handles both, given a sequence of all jobs per machine. This sequence is provided by the MILP or constructive heuristics or a Genetic Algorithm (GA). The scalability and performance of all methods is evaluated computationally on large-scale real-life instances of about 500 jobs on 15 stages with up to 5 machines per stage and 30 machines in total.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 13727
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
JPY 17159
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Lenstra, J.K., Kan, A.R., Brucker, P.: Complexity of machine scheduling problems. Ann. Disc. Math. 1, 343–362 (1977)

    Article  MathSciNet  Google Scholar 

  2. Gupta, S.K., Kyparisis, J.: Single machine scheduling research. Omega 15(3), 207–227 (1987)

    Article  Google Scholar 

  3. Cheng, T.C.E., Sin, C.C.S.: A state-of-the-art review of parallel-machine scheduling research. Eur. J. Oper. Res. 47(3), 271–292 (1990)

    Article  Google Scholar 

  4. Márquez, C.R., Ribeiro, C.C.: Shop scheduling in manufacturing environments: a review. Int. Trans. Oper. Res. 29(6), 3237–3293 (2022)

    Article  MathSciNet  Google Scholar 

  5. Neufeld, J.S., Schulz, S., Buscher, U.: A systematic review of multi-objective hybrid flow shop scheduling. Eur. J. Oper. Res. 309(1), 1–23 (2023)

    Article  MathSciNet  Google Scholar 

  6. Lian, X., Zheng, Z., Wang, C., Gao, X.: An energy-efficient hybrid flow shop scheduling problem in steelmaking plants. Comput. Ind. Eng. 162, 107683 (2021)

    Article  Google Scholar 

  7. Jun, S., Park, J.: A hybrid genetic algorithm for the hybrid flow shop scheduling problem with nighttime work and simultaneous work constraints: A case study from the transformer industry. Expert Syst. Appl. 42(15–16), 6196–6204 (2015)

    Article  Google Scholar 

  8. Li, Z., Wan, G.: Batching and scheduling in a continuous-discrete hybrid flowshop: Lagrangian relaxation-based heuristic algorithms. Int. J. Prod. Res. 61(17), 5934–5955 (2023)

    Article  Google Scholar 

  9. Naderi, B., Zandieh, M., Balagh, A.K.G., Roshanaei, V.: An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Syst. Appl. 36(6), 9625–9633 (2009)

    Article  Google Scholar 

  10. Elmi, A., Topaloglu, S.: Scheduling multiple parts in hybrid flow shop robotic cells served by a single robot. Int. J. Comput. Integr. Manuf. 27(12), 1144–1159 (2014)

    Article  Google Scholar 

  11. Mousavi, S.M., Zandieh, M., Amiri, M.: Comparisons of bi-objective genetic algorithms for hybrid flowshop scheduling with sequence-dependent setup times. Int. J. Prod. Res. 50(10), 2570–2591 (2012)

    Article  Google Scholar 

  12. Dabiri, M., Yazdani, M., Naderi, B., Haleh, H.: Modeling and solution methods for hybrid flow shop scheduling problem with job rejection. Oper. Res. Int. J. 22(3), 2721–2765 (2022)

    Article  Google Scholar 

  13. Öztop, H., Tasgetiren, M.F., Eliiyi, D.T., Pan, Q.K.: Metaheuristic algorithms for the hybrid flowshop scheduling problem. Comput. Oper. Res. 111, 177–196 (2019)

    Article  MathSciNet  Google Scholar 

  14. Gheisariha, E., Tavana, M., Jolai, F., Rabiee, M.: A simulation-optimization model for solving flexible flow shop scheduling problems with rework and transportation. Math. Comput. Simul. 180, 152–178 (2021)

    Article  MathSciNet  Google Scholar 

  15. Abbaszadeh, N., Asadi-Gangraj, E., Emami, S.: Flexible flow shop scheduling problem to minimize makespan with renewable resources. Scientia Iranica 28(3), 1853–1870 (2021)

    Google Scholar 

  16. Lei, C., Zhao, N., Ye, S., Wu, X.: Memetic algorithm for solving flexible flow-shop scheduling problems with dynamic transport waiting times. Comput. Ind. Eng. 139, 105984 (2020)

    Article  Google Scholar 

  17. Naderi, B., Gohari, S., Yazdani, M.: Hybrid flexible flowshop problems: models and solution methods. Appl. Math. Model. 38(24), 5767–5780 (2014)

    Article  MathSciNet  Google Scholar 

  18. Amirteimoori, A., Mahdavi, I., Solimanpur, M., Ali, S.S., Tirkolaee, E.B.: A parallel hybrid PSO-GA algorithm for the flexible flow-shop scheduling with transportation. Comput. Ind. Eng. 173, 108672 (2022)

    Article  Google Scholar 

  19. Mollaei, A., Mohammadi, M., Naderi, B.: A bi-objective MILP model for blocking hybrid flexible flow shop scheduling problem: robust possibilistic programming approach. Int. J. Manag. Sci. Eng. Manag. 14(2), 137–146 (2019)

    Google Scholar 

  20. Armstrong, E., Garraffa, M., O’Sullivan, B., Simonis, H.: The hybrid flexible flowshop with transportation times. In: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2021)

    Google Scholar 

  21. Armstrong, E., Garraffa, M., O’Sullivan, B., Simonis, H.: A two-phase hybrid approach for the hybrid flexible flowshop with transportation times. In: Schaus, P. (ed.) International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, vol. 13292, pp. 1–13. Springer, Heidelberg (2022)

    Google Scholar 

  22. Jiang, S.L., Xu, C., Zhang, L., Ma, Y.: A decomposition-based two-stage online scheduling approach and its integrated system in the hybrid flow shop of steel industry. Expert Syst. Appl. 213, 119200 (2023)

    Article  Google Scholar 

  23. Zhang, H.Y., Xi, S.H., Chen, Q.X., Smith, J.M., Mao, N., Li, X.: Performance analysis of a flexible flow shop with random and state-dependent batch transport. Int. J. Prod. Res. 59(4), 982–1002 (2021)

    Article  Google Scholar 

  24. Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Disc. Math. 5, 287–326 (1979)

    Article  MathSciNet  Google Scholar 

  25. Naderi, B., Ruiz, R., Roshanaei, V.: Mixed-integer programming vs. constraint programming for shop scheduling problems: new results and outlook. INFORMS J. Comput. 35(4), 817–843 (2023)

    Google Scholar 

  26. Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975)

    Google Scholar 

  27. Avgerinos, I., Mourtos, I., Vatikiotis, S., Zois, G.: Weighted tardiness minimisation for unrelated machines with sequence-dependent and resource-constrained setups. Int. J. Prod. Res. 62(1–2), 359–379 (2024)

    Article  Google Scholar 

  28. IBM: IBM ILOG CPLEX 12.7 User’s Manual. IBM ILOG CPLEX Division, Incline Village (2017)

    Google Scholar 

  29. Bynum, M.L., et al.: Pyomo-Optimization Modeling in Python, 3rd edn. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-319-58821-6

    Book  Google Scholar 

  30. Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2024)

    Google Scholar 

  31. Bauer, M., Lucke, M., Johnsson, C., Harjunkoski, I., Schlake, J.C.: KPIs as the interface between scheduling and control. IFAC-PapersOnLine 49(7), 687–692 (2016)

    Article  Google Scholar 

  32. Vallada, E., Ruiz, R., Framinan, J.M.: New hard benchmark for flowshop scheduling problems minimising makespan. Eur. J. Oper. Res. 240(3), 666–677 (2015)

    Article  Google Scholar 

  33. Geurtsen, M., Didden, J.B., Adan, J., Atan, Z., Adan, I.J.B.F.: Production, maintenance and resource scheduling: a review. Eur. J. Oper. Res. 305(2), 501–529 (2023)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

This research has been supported by the EU through the MODAPTO Horizon 2020 project, grant number 101091996.

Author information

Authors and Affiliations

  1. ELTRUN Research Lab, Department of Management Science and Technology, Athens University of Economics and Business, Athens, Greece

    Stavros Vatikiotis, Ilias Mpourdakos, Dimitrios Papathanasiou & Ioannis Mourtos

Authors
  1. Stavros Vatikiotis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ilias Mpourdakos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dimitrios Papathanasiou
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ioannis Mourtos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stavros Vatikiotis .

Editor information

Editors and Affiliations

  1. Chemnitz University of Technology, Chemnitz, Germany

    Matthias Thürer

  2. West Saxon University of Applied Sciences Zwickau, Zwickau, Germany

    Ralph Riedel

  3. ZF Friedrichshafen AG, Friedrichshafen, Germany

    Gregor von Cieminski

  4. Tecnológico de Monterrey, Mexico City, Mexico

    David Romero

Ethics declarations

Disclosure of Interests

The authors have no competing interests to declare that are relevant to the content of this article.

Rights and permissions

Reprints and permissions

Copyright information

© 2024 IFIP International Federation for Information Processing

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Vatikiotis, S., Mpourdakos, I., Papathanasiou, D., Mourtos, I. (2024). Makespan Minimisation in Hybrid Flexible Flowshops with Buffers and Machine-Dependent Transportation Times. In: Thürer, M., Riedel, R., von Cieminski, G., Romero, D. (eds) Advances in Production Management Systems. Production Management Systems for Volatile, Uncertain, Complex, and Ambiguous Environments. APMS 2024. IFIP Advances in Information and Communication Technology, vol 733. Springer, Cham. https://doi.org/10.1007/978-3-031-71645-4_18

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-71645-4_18

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-71644-7

  • Online ISBN: 978-3-031-71645-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships