no. 1
Two-machine flow shop with synchronized periodic maintenance
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 351-365

In the literature, some works deal with the two-machine flow shop scheduling problem under availability constraints. Most of them consider those constraints only for one machine at a time and also with limited unavailability periods. In this work, we were interested by the unlimited periodic and synchronized maintenance applied on both machines. The problem is NP-hard. We proposed a mixed integer programming model and a variable neighborhood search for solving large instances in order to minimize the makespan. Computational experiments show the efficiency of the proposed methods.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018062
Classification : 90B35, 90C11
Keywords: Flow shop scheduling, preventive maintenance, mixed integer programming model, variable neighborhood search

Krimi, Issam 1 ; Benmansour, Rachid 1 ; Hanafi, Saïd 1 ; Elhachemi, Nizar 1

1 
@article{RO_2019__53_1_351_0,
     author = {Krimi, Issam and Benmansour, Rachid and Hanafi, Sa{\"\i}d and Elhachemi, Nizar},
     title = {Two-machine flow shop with synchronized periodic maintenance},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {351--365},
     year = {2019},
     publisher = {EDP Sciences},
     volume = {53},
     number = {1},
     doi = {10.1051/ro/2018062},
     mrnumber = {3912476},
     zbl = {1414.90159},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2018062/}
}
TY  - JOUR
AU  - Krimi, Issam
AU  - Benmansour, Rachid
AU  - Hanafi, Saïd
AU  - Elhachemi, Nizar
TI  - Two-machine flow shop with synchronized periodic maintenance
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 351
EP  - 365
VL  - 53
IS  - 1
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2018062/
DO  - 10.1051/ro/2018062
LA  - en
ID  - RO_2019__53_1_351_0
ER  - 
%0 Journal Article
%A Krimi, Issam
%A Benmansour, Rachid
%A Hanafi, Saïd
%A Elhachemi, Nizar
%T Two-machine flow shop with synchronized periodic maintenance
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 351-365
%V 53
%N 1
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ro/2018062/
%R 10.1051/ro/2018062
%G en
%F RO_2019__53_1_351_0
Krimi, Issam; Benmansour, Rachid; Hanafi, Saïd; Elhachemi, Nizar. Two-machine flow shop with synchronized periodic maintenance. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 351-365. doi: 10.1051/ro/2018062

[1] R. Aggoune and M.C. Portmann, Flow shop scheduling problem with limited machine availability: a heuristic approach. Int. J. Prod. Econ. 99 (2006) 4–15.

[2] R. Benmansour, H. Allaoui, A. Artiba and S. Hanafi, Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance. Comput. Oper. Res. 47 (2014) 106–113. | MR | Zbl | DOI

[3] M. Benttaleb, F. Hnaien and F. Yalaoui, Two-machine job shop problem for makespan minimization under availability constraint. IFAC-PapersOnLine 49 (2016) 132–137.

[4] J. Błażewicz, J. Breit, P. Formanowicz, W. Kubiak and G. Schmidt, Heuristic algorithms for the two-machine flowshop with limited machine availability. Omega 29 (2001) 599–608.

[5] J. Breit, An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint. Inf. Process. Lett. 90 (2004) 273–278. | MR | Zbl | DOI

[6] J. Breit, A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint. Comput. Oper. Res. 33 (2006) 2143–2153. | MR | Zbl

[7] T.C.E. Cheng and G. Wang, Two-machine flowshop scheduling with consecutive availability constraints. Inf. Process. Lett. 71 (1999) 49–54. | MR | Zbl | DOI

[8] T.C.E. Cheng and G. Wang, An improved heuristic for two-machine flowshop scheduling with an availability constraint. Oper. Res. Lett. 26 (2000) 223–229. | MR | Zbl

[9] F. Ben Chihaoui, I. Kacem, A.B. Hadj-Alouane, N. Dridi and N. Rezg, No-wait scheduling of a two-machine flow-shop to minimise the makespan under non-availability constraints and different release dates. Int. J. Prod. Res. 49 (2011) 6273–6286. | DOI

[10] M.L. Espinouse, P. Formanowicz and B. Penz, Minimizing the makespan in the two-machine no-wait flow-shop with limited machine availability. Comput. Ind. Eng. 37 (1999) 497–500.

[11] A. Gara-Ali and M.L. Espinouse, A two-machine flowshop with a deteriorating maintenance activity on the second machine. In: Industrial Engineering and Systems Management (IESM), 2015 International Conference on. IEEE (2015) 481–488.

[12] M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1 (1976) 117–129. | MR | Zbl | DOI

[13] H. Gholizadeh, R. Tavakkoli-Moghaddam and B. Tootooni, Minimizing the makespan in a flow shop scheduling problem with sequence-dependent setup times and periodic maintenance by a hybrid algorithm. In: 2012 International Conference on Industrial Engineering and Operations Management (2012) 806–814.

[14] F.W. Glover and G.A. Kochenberger, Handbook of Metaheuristics, Vol. 57. Springer Science & Business Media, Berlin (2006). | MR | Zbl

[15] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.R. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979) 287–326. | MR | Zbl | DOI

[16] H. Hadda, A polynomial-time approximation scheme for the two-machine flow shop problem with several availability constraints. Optim. Lett. 6 (2012) 559–569. | MR | Zbl

[17] H. Hadda, N. Dridi and S. Hajri-Gabouj, An improved heuristic for two-machine flowshop scheduling with an availability constraint and nonresumable jobs. 40R-Q J. Oper. Res. 8 (2010) 87–99. | MR | Zbl | DOI

[18] H. Hadda, A (4/3)- approximation algorithm for a special case of the two machine flow shop problem with several availability constraints. Optim. Lett. 3 (2009) 583–592. | MR | Zbl | DOI

[19] H. Hadda, Approximation results for the two-machine job shop under limited machine availability. OPSEARCH 54 (2017) 651–662. | MR | Zbl | DOI

[20] P. Hansen and N. Mladenović, First vs. best improvement: an empirical study. Discrete Appl. Math. 154 (2006) 802–817. | MR | Zbl | DOI

[21] P. Hansen, N. Mladenović and J.A. Moreno Pérez, Variable neighbourhood search: methods and applications. Ann. Oper. Res. 175 (2010) 367–407. | MR | Zbl

[22] P. Hansen, N. Mladenović, R. Todosijević and S. Hanafi, Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5 (2016) 423–454. | MR | Zbl

[23] F. Hnaien, F. Yalaoui and A. Mhadhbi, Makespan minimization on a two-machine flowshop with an availability constraint on the first machine. Int. J. Prod. Econ. 164 (2015) 95–104. | DOI

[24] M. Ji, Y. He and T.C.E. Cheng, Single-machine scheduling with periodic maintenance to minimize makespan. Comput. Oper. Res. 34 (2007) 1764–1770. | MR | Zbl | DOI

[25] S.M. Johnson, Optimal two-and three-stage production schedules with sertup times included. Nav. Res. Logist. Quart. 1 (1954) 61–68. | DOI

[26] I. Kacem and C. Chu, Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint. Int. J. Prod. Econ. 112 (2008) 138–150. | DOI

[27] I. Kacem, C. Chu and A. Souissi, Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times. Comput. Oper. Res. 35 (2008) 827–844. | MR | Zbl

[28] I. Kacem, H. Kellerer and Y. Lanuel, Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals. J. Comb. Optim. 30 (2015) 403–412. | MR | Zbl | DOI

[29] I. Kacem, M. Sahnoune and G. Schmidt, Strongly fully polynomial time approximation scheme for the weighted completion time minimization problem on two-parallel capacitated machines. RAIRO: OR 51 (2017) 1177–1188. | MR | Zbl | Numdam | DOI

[30] W. Kubiak, J. Błażewicz, P. Formanowicz, J. Breit and G. Schmidt, Two-machine flow shops with limited machine availability. Eur. J. Oper. Res. 136 (2002) 528–540. | MR | Zbl | DOI

[31] M.A. Kubzin, C.N. Potts and V.A. Strusevich, Approximation results for flow shop scheduling problems with machine availability constraints. Comput. Oper. Res. 36 (2009) 379–390. | MR | Zbl | DOI

[32] M.A. Kubzin and V.A. Strusevich, Two-machine flow shop no-wait scheduling with machine maintenance. 4OR: A Quart. J. Oper. Res. 3 (2005) 303–313. | MR | Zbl | DOI

[33] M.A. Kubzin and V.A. Strusevich, Planning machine maintenance in two-machine shop scheduling. Oper. Res. 54 (2006) 789–800. | Zbl | DOI

[34] C.Y. Lee, Machine scheduling with an availability constraint. J. Global Optim. 9 (1996) 395–416. | MR | Zbl | DOI

[35] C.Y. Lee, Minimizing the makespan in the two-machine flowshop scheduling problem with availability constraint. Oper. Res. Lett. 20 (1997) 129–139. | MR | Zbl | DOI

[36] C.Y. Lee, Two-machine flowshop scheduling problem with availability constraints. Eur. J. Oper. Res. 114 (1999) 420–429. | Zbl | DOI

[37] L.M. Liao and C.H. Tsai, Heuristics algorithms for two-machine flowshop with availability constraints. Comput. Ind. Eng. 56 (2009) 306–311.

[38] Y. Ma and C. Zuo, A survey of scheduling with deterministic machine availability constraints. Comput. Ind. Eng. 58 (2010) 199–211. | DOI

[39] N. Mladenović and P. Hansen, Variable neighborhood search: Principles and applications. Eur. J. Oper. Res. 130 (2001) 449–467. | MR | Zbl | DOI

[40] B. Naderi, M. Zandieh and M. Aminnayeri, Incorporating periodic preventive maintenance into flexible flowshop scheduling problems. Appl. Soft Comput. 11 (2011) 2094–2101. | DOI

[41] C.T. Ng and M.Y. Kovalyov, An FPTAS for scheduling a two-machine flowshop with one unavailability interval. Nav. Res. Logistics (NRL) 51 (2004) 307–315. | MR | Zbl | DOI

[42] D. Saidy, H. Reza and M. Taghi Taghavi-Fard, Study of scheduling problems with machine availability constraint. J. Ind Syst. Eng. 1 (2008) 360–383.

[43] G. Schmidt, Scheduling with limited machine availability. Eur. J. Oper. Res. 121 (2000) 1–15. | MR | Zbl

[44] R. Todosijević, R. Benmansour, S. Hanafi and N. Mladenović, Nested general variable neighborhood search for the periodic maintenance problem. Eur. J. Oper. Res. 252 (2016) 385–396. | MR | Zbl | DOI

[45] X. Wang and T.C.E. Cheng, Heuristics for two-machine flowshop scheduling with setup times and an availability constraint. Comput. Oper. Res. 34 (2007) 152–162. | Zbl

[46] D. Xu, Z. Cheng, Y. Yin and H. Li, Makespan minimization for two parallel machines scheduling with a periodic availability constraint. Comput. Oper. Res. 36 (2009) 1809–1812. | MR | Zbl | DOI

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

[48] D.L. Yang, C.J. Hsu and W.H. Kuo, A two-machine flowshop scheduling problem with a separated maintenance constraint. Comput. Oper. Res. 35 (2008) 876–883. | MR | Zbl | DOI

Cité par Sources :