Skip to main content
SpringerLink
Log in

Solving the Total Weighted Earliness Tardiness Blocking Flowshop Scheduling Problem

  • Living reference work entry
  • First Online:
Handbook of Formal Optimization

  • 23 Accesses

Abstract

Punctual delivery is of great importance to industrial companies because their customers typically need to receive orders by a specific date. In this study, we examine the flowshop scheduling problem with blocking constraints, which involves finding the optimal schedule to minimize the total weighted earliness and tardiness from the due date window. Previous research has demonstrated that this problem is NP-hard, meaning that it is computationally difficult to solve. To address this issue, we propose an effective iterated greedy algorithm. The effectiveness of our approach is evaluated using a set of 110 benchmark instances and compared to seven other methods from the scheduling literature that have been selected and re-implemented for comparison. The results of the study show that our approach is efficient.

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

Access this chapter

Log in via an institution

Institutional subscriptions

References

  • Abreu LR, Cunha JO, Prata BA, Framinan JM (2020) A genetic algorithm for scheduling open shops with sequence-dependent setup times. Comput Oper Res 113:104793

    Article  MathSciNet  MATH  Google Scholar 

  • Aggoune R (2004) Minimizing the makespan for the flow shop scheduling problem with availability constraints. Eur J Oper Res 153(3):534–543

    Article  MathSciNet  MATH  Google Scholar 

  • Aziza H, Krichen S (2020) A hybrid genetic algorithm for scientific workflow scheduling in cloud environment. Neural Comput Applic 32(18):15263–15278

    Article  Google Scholar 

  • Engin O, Döyen A (2004) A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Futur Gener Comput Syst 20(6):1083–1095

    Article  Google Scholar 

  • Graham RL, Lawler EL, Lenstra JK, Kan AR (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals of discrete mathematics, vol 5. Elsevier, pp 287–326

    Google Scholar 

  • Gupta JN (1971) A functional heuristic algorithm for the flowshop scheduling problem. J Oper Res Soc 22(1):39–47

    Article  MathSciNet  MATH  Google Scholar 

  • Hall NG, Sriskandarajah C (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 44(3):510–525

    Article  MathSciNet  MATH  Google Scholar 

  • Han Y, Gong D, Li J, Zhang Y (2016) Solving the blocking flow shop scheduling problem with makespan using a modified fruit fly optimisation algorithm. Int J Prod Res 54(22):6782–6797

    Article  Google Scholar 

  • Han YY, Pan QK, Li JQ, Sang Hy (2012) An improved artificial bee colony algorithm for the blocking flowshop scheduling problem. Int J Adv Manuf Technol 60(9–12):1149–1159

    Article  Google Scholar 

  • Heinzl B, Kastner W (2020) A general variable neighborhood search for simulation-based energy-aware flow shop scheduling. In: Proceedings of the 2020 Summer Simulation Conference, pp 1–12

    Google Scholar 

  • Huang YY, Pan QK, Huang JP, Suganthan PN, Gao L (2021) An improved iterated greedy algorithm for the distributed assembly permutation flowshop scheduling problem. Comput Ind Eng 152:107021

    Article  Google Scholar 

  • Iyer SK, Saxena B (2004) Improved genetic algorithm for the permutation flowshop scheduling problem. Comput Oper Res 31(4):593–606

    Article  MathSciNet  MATH  Google Scholar 

  • Johnson SM (1954) Optimal two-and three-stage production schedules with setup times included. Nav Res Logist Q 1(1):61–68

    Article  MATH  Google Scholar 

  • Kahraman C, Engin O, Kaya I, Kerim Yilmaz M (2008) An application of effective genetic algorithms for solving hybrid flow shop scheduling problems. Int J Comput Intell Syst 1(2):134–147

    Article  Google Scholar 

  • Koulamas C (1998) A new constructive heuristic for the flowshop scheduling problem. Eur J Oper Res 105(1):66–71

    Article  MathSciNet  MATH  Google Scholar 

  • Mao Jy, Pan Qk, Miao Zh, Gao L (2021) An effective multi-start iterated greedy algorithm to minimize makespan for the distributed permutation flowshop scheduling problem with preventive maintenance. Expert Syst Appl 169:114495

    Article  Google Scholar 

  • Missaoui A, Boujelbene Y (2021a) Artificial bee colony for blocking flowshop with due date windows. In: 2021 International Conference on Data Analytics for Business and Industry (ICDABI), pp 557–561. https://doi.org/10.1109/ICDABI53623.2021.9655907

  • Missaoui A, Boujelbene Y (2021b) An effective iterated greedy algorithm for blocking hybrid flow shop problem with due date window. RAIRO-Oper Res 55(3):1603–1616

    Article  MathSciNet  Google Scholar 

  • Missaoui A, Boujelbene Y (2021c) Hybrid genetic algorithm for blocking flowshop scheduling with due date windows. In: 2021 International Conference on Decision Aid Sciences and Application (DASA), pp 745–750. https://doi.org/10.1109/DASA53625.2021.9682275

  • Missaoui A, Ruiz R (2022) A parameter-less iterated greedy method for the hybrid flowshop scheduling problem with setup times and due date windows. Eur J Oper Res 303(1):99–113

    Article  MathSciNet  MATH  Google Scholar 

  • Miyata HH, Nagano MS (2019) The blocking flow shop scheduling problem: A comprehensive and conceptual review. Expert Syst Appl 137:130–156

    Article  Google Scholar 

  • Moslehi G, Khorasanian D (2013) Optimizing blocking flow shop scheduling problem with total completion time criterion. Comput Oper Res 40(7):1874–1883

    Article  MathSciNet  MATH  Google Scholar 

  • Naderi B, Zandieh M, Roshanaei V (2009) Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness. Int J Adv Manuf Technol 41(11):1186–1198

    Article  Google Scholar 

  • Pan QK, Wang L (2012) Effective heuristics for the blocking flowshop scheduling problem with makespan minimization. Omega 40(2):218–229

    Article  Google Scholar 

  • Pan QK, Gao L, Li XY, Gao KZ (2017a) Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times. Appl Math Comput 303:89–112

    MathSciNet  MATH  Google Scholar 

  • Pan QK, Ruiz R, Alfaro-Fernández P (2017b) Iterated search methods for earliness and tardiness minimization in hybrid flowshops with due windows. Comput Oper Res 80:50–60

    Article  MathSciNet  MATH  Google Scholar 

  • Pinedo ML (2012) Scheduling: Theory, Algorithms, and Systems. Springer, NY, USA

    Book  MATH  Google Scholar 

  • Ribas I, Companys R, Tort-Martorell X (2017) Efficient heuristics for the parallel blocking flow shop scheduling problem. Expert Syst Appl 74:41–54

    Article  Google Scholar 

  • Ribas I, Companys R, Tort-Martorell X (2019) An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem. Expert Syst Appl 121:347–361

    Article  Google Scholar 

  • Ruiz R, Stützle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177(3):2033–2049

    Article  MATH  Google Scholar 

  • Ruiz R, Pan QK, Naderi B (2019) Iterated greedy methods for the distributed permutation flowshop scheduling problem. Omega 83:213–222

    Article  Google Scholar 

  • Sabuncuoglu I, Lejmi T (1999) Scheduling for non-regular performance measure under the due window approach. Omega 27(5):555–568

    Article  Google Scholar 

  • Shojaie AA, Sajedi S (2017) Particle swarm optimization for minimizing total earliness/tardiness costs of two-stage assembly flowshop scheduling problem in a batched delivery system. J Ind Syst Eng 10(special issue on scheduling):78–91

    Google Scholar 

  • Tasgetiren MF, Kizilay D, Pan QK, Suganthan PN (2017) Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion. Comput Oper Res 77:111–126

    Article  MathSciNet  MATH  Google Scholar 

  • Wang L, Pan QK, Tasgetiren MF (2011) A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem. Comput Ind Eng 61(1):76–83

    Article  Google Scholar 

  • Yang T, Kuo Y, Chang I (2004) Tabu-search simulation optimization approach for flow-shop scheduling with multiple processors – a case study. Int J Prod Res 42(19):4015–4030

    Article  MATH  Google Scholar 

  • Zhang Q, Tian Z, Wang S, Liu S (2020) Iterated greedy algorithm for solving a hybrid flow shop scheduling problem with reentrant jobs. In: 2020 Chinese Control And Decision Conference (CCDC). IEEE, pp 5636–5641

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculté des Sciences Économiques et de Gestion de Sfax, Université de Sfax, Sfax, Tunisia

    Ahmed Missaoui & Younes Boujelbene

Authors
  1. Ahmed Missaoui
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Younes Boujelbene
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute of Artificial Intelligence, MIT World Peace University, Pune, Pune, Maharashtra, India

    Anand J. Kulkarni

  2. Faculty of Engineering and IT, University of Technology Sydney, Ultimo, NSW, Australia

    Amir H. Gandomi

Section Editor information

  1. Institute of Artificial Intelligence, MIT World Peace University, Pune, MH, India

    Anand J Kulkarni

Rights and permissions

Reprints and permissions

Copyright information

© 2023 Springer Nature Singapore Pte Ltd.

About this entry

Check for updates. Verify currency and authenticity via CrossMark

Cite this entry

Missaoui, A., Boujelbene, Y. (2023). Solving the Total Weighted Earliness Tardiness Blocking Flowshop Scheduling Problem. In: Kulkarni, A.J., Gandomi, A.H. (eds) Handbook of Formal Optimization. Springer, Singapore. https://doi.org/10.1007/978-981-19-8851-6_25-1

Download citation

  • DOI: https://doi.org/10.1007/978-981-19-8851-6_25-1

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-19-8851-6

  • Online ISBN: 978-981-19-8851-6

  • eBook Packages: Springer Reference Intelligent Technologies and RoboticsReference Module Computer Science and Engineering

Publish with us

Policies and ethics

Search

Navigation