[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Variable neighborhood search algorithms for the permutation flowshop scheduling problem with the preventive maintenance

  • Original paper
  • Published:
Operational Research Aims and scope Submit manuscript

Abstract

This paper addresses to the permutation flowshop scheduling problem while considering the preventive maintenance in the non-resumable case. The criterion to be optimized is the makespan. Two variable neighborhood search algorithms are proposed. In the first algorithm, only one initial solution is generated according to a constructive heuristic. In the second algorithm, a learning process using a probabilistic model is introduced to the variable neighborhood algorithm in order to generate the initial solution. The computational results show the high performance of the proposed algorithms according to the compared approaches. Besides, the change of the initial solution during the optimization procedure may improve the performance of the variable neighborhood search algorithm.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

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

    Article  Google Scholar 

  • Al-Turki O, Ayar T, Yilbas B-S, Sahin A-Z (2014) Integrated maintenance planning in manufacturing systems. Springer, Berlin

    Book  Google Scholar 

  • Allaoui H, Lamouri S, Artiba A, Aghezzaf E (2008) Simultaneously scheduling n jobs and the preventive maintenance on the two-machine flow shop to minimize the makespan. Int J Prod Econ 112(1):161–167

    Article  Google Scholar 

  • Aloise DJ, Aloise D, Rocha CTM, Ribeiro CC, Ribeiro Filho JC, Moura LSS (2006) Scheduling workover rigs for onshore oil production. Discret Appl Math 154(5):695–702 (IV ALIO/EURO Workshop on Applied Combinatorial Optimization)

    Article  Google Scholar 

  • Benbouzid-Si Tayeb F, Belkaaloul W (2014) Towards an artificial immune system for scheduling jobs and preventive maintenance operations in flowshop problems. In 23rd IEEE international symposium on industrial electronics, ISIE 2014, Istanbul, Turkey, June 1-4, 2014, p 1065–1070

  • Benbouzid-Sitayeb F, Guebli S-A, Bessadi Y, Varnier C, Zerhouni N (2011) Joint scheduling of jobs and preventive maintenance operations in the flowshop sequencing problem: a resolution with sequential and integrated strategies. Int J Manuf Res 6(1):30–48

    Article  Google Scholar 

  • Besbes W, Teghem J, Loukil T (2010) Scheduling hybrid flow shop problem with non-fixed availability constraints. Eur J Ind Eng 4(10):413–433

    Article  Google Scholar 

  • Birolini A (2010) Reliability engineering: theory and practice. Springer, Berlin

    Book  Google Scholar 

  • Graham R L, Lawler E L, Lenstra J K, Kan A H G Rinnooy (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 5(2):287–326

    Article  Google Scholar 

  • Hansen P, Mladenović N (2001) Variable neighborhood search: principles and applications. Eur J Op Res 130(3):449–467

    Article  Google Scholar 

  • Jarboui B, Eddaly M, Siarry P (2009) An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems. Comput Op Res 36:2638–2646

    Article  Google Scholar 

  • Kubiak W, Błażewicz J, Formanowicz P, Breit J, Schmidt G (2002) Two-machine flow shops with limited machine availability. Eur J Op Res 136(3):528–540

    Article  Google Scholar 

  • Laalaoui Y, M’Hallah R (2016) A binary multiple knapsack model for single machine scheduling with machine unavailability. Comput Op Res 72:71–82

    Article  Google Scholar 

  • Ladj A, Tayeb F Benbouzid-Si, Varnier C, Dridi A-A, Selmane N (2017) A hybrid of variable neighbor search and fuzzy logic for the permutation flowshop scheduling problem with predictive maintenance. Procedia Comput Sci 112:663–672

    Article  Google Scholar 

  • Lee C-Y (1997) Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint. Op Res Lett 20(3):129–139

    Article  Google Scholar 

  • Lee C-Y, Chen Z-L (2000) Scheduling jobs and maintenance activities on parallel machines. Nav Res Logist (NRL) 47(2):145–165

    Article  Google Scholar 

  • Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Op Res 24(11):1097–1100

    Article  Google Scholar 

  • Msakni MK, Haouari M (2018) Short-term planning of liquefied natural gas deliveries. Transp Res Part C Emerg Technol 90:393–410

    Article  Google Scholar 

  • Mühlenbein H, Paaß G (1996) From recombination of genes to the estimation of distributions i. binary parameters. In: Voigt H-M, Ebeling W, Rechenberg I, Schwefel H-P (eds) Parallel problem solving from nature–PPSN IV. Springer, Berlin, pp 178–187

    Chapter  Google Scholar 

  • Naderi B, Zandieh M, Aminnayeri M (2011) Incorporating periodic preventive maintenance into flexible flowshop scheduling problems. Appl Soft Comput 11(2):2094–2101

    Article  Google Scholar 

  • Nawaz M, Enscor E-E, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11(1):91–95

    Article  Google Scholar 

  • Osman I-H, Potts C-N (1989) Simulated annealing for permutation flow-shop scheduling. Omega 17(6):551–557

    Article  Google Scholar 

  • Pacheco J, Porras S, Casado S, Baruque B (2018) Variable neighborhood search with memory for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times. Knowl-Based Syst 145:236–249

    Article  Google Scholar 

  • Rajendran C, Ziegler H (2004) Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. Eur J Op Res 155(2):426–438

    Article  Google Scholar 

  • Ruiz R, Garcia-Diaz J-C, Maroto C (2007) Considering scheduling and preventive maintenance in the flowshop sequencing problem. Comput Op Res 34(11):3314–3330

    Article  Google Scholar 

  • Ruiz R, Maroto C, Alcaraz C (2006) Two new robust genetic algorithms for the flowshop scheduling problem. Omega 34(5):461–476

    Article  Google Scholar 

  • Todosijević R, Benmansour R, Hanafi S, Mladenović N, Artiba A (2016) Nested general variable neighborhood search for the periodic maintenance problem. Eur J Op Res 252(2):385–396

    Article  Google Scholar 

  • Widmer M, Hertz A (1989) A new heuristic method for the flow shop sequencing problem. Eur J Op Res 41(2):186–193

    Article  Google Scholar 

  • Xu D, Cheng Z, Yin Y, Li H (2009) Makespan minimization for two parallel machines scheduling with a periodic availability constraint. Comput Op Res 36(6):1809–1812

    Article  Google Scholar 

  • Xu D, Sun K, Li H (2008) Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan. Comput Op Res 35(4):1344–1349

    Article  Google Scholar 

  • Xu D, Yang D-L (2013) Makespan minimization for two parallel machines scheduling with a periodic availability constraint: mathematical programming model, average-case analysis, and anomalies. Appl Math Model 37(14):7561–7567

    Article  Google Scholar 

  • Yang D-L, Hsu C-J, Kuo W-H (2008) A two-machine flowshop scheduling problem with a separated maintenance constraint. Comput Op Res 35(3):876–883 (Part Special Issue: New Trends in Locational Analysis)

    Article  Google Scholar 

  • Yazdani M, Khalili S Mohammad, Babagolzadeh M, Jolai F (2017) A single-machine scheduling problem with multiple unavailability constraints: a mathematical model and an enhanced variable neighborhood search approach. J Comput Des Eng 4(1):46–59

    Google Scholar 

  • Ying M, Chengbin C, Chunrong Z (2010) A survey of scheduling with deterministic machine availability constraints. Comput Ind Eng 58(2):199–211 (Scheduling in Healthcare and Industrial Systems)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. MODILS Laboratory, FSEGS, Université de Sfax, Sfax, Tunisia

    Wahiba Jomaa

  2. College of Business and Economics, Qassim University, Buraydah, Kingdom of Saudi Arabia

    Mansour Eddaly

  3. ISAEG, Université de Gafsa, Gafsa, Tunisia

    Mansour Eddaly

  4. Higher Colleges of Technology, Abu Dhabi, United Arab Emirates

    Bassem Jarboui

Authors
  1. Wahiba Jomaa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mansour Eddaly
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bassem Jarboui
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mansour Eddaly.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jomaa, W., Eddaly, M. & Jarboui, B. Variable neighborhood search algorithms for the permutation flowshop scheduling problem with the preventive maintenance. Oper Res Int J 21, 2525–2542 (2021). https://doi.org/10.1007/s12351-019-00507-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12351-019-00507-y

Keywords

Mathematics Subject Classification

Search

Navigation