A variable neighborhood search algorithm for solving the single machine scheduling problem with periodic maintenance
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 289-302.

In this paper we propose to solve a single machine scheduling problem which has to undergo a periodic preventive maintenance. The objective is to minimize the weighted sum of the completion times. This criterion is defined as one of the most important objectives in practice but has not been studied so far for the considered problem. As the problem is proven to be NP-hard, and a mathematical model is proposed in the literature, we propose to use General Variable Neighborhood Search algorithm to solve this problem in order to obtain near optimal solutions for the large-sized instances in a small amount of computational time.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018055
Classification : 90–XX, 68–XX
Mots-clés : Single machine scheduling, periodic preventive maintenance, metaheuristic, variable neighborhood search
Krim, Hanane 1 ; Benmansour, Rachid 1 ; Duvivier, David 1 ; Artiba, Abdelhakim 1

1 
@article{RO_2019__53_1_289_0,
     author = {Krim, Hanane and Benmansour, Rachid and Duvivier, David and Artiba, Abdelhakim},
     title = {A variable neighborhood search algorithm for solving the single machine scheduling problem with periodic maintenance},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {289--302},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {1},
     year = {2019},
     doi = {10.1051/ro/2018055},
     zbl = {1414.90158},
     mrnumber = {3912472},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018055/}
}
TY  - JOUR
AU  - Krim, Hanane
AU  - Benmansour, Rachid
AU  - Duvivier, David
AU  - Artiba, Abdelhakim
TI  - A variable neighborhood search algorithm for solving the single machine scheduling problem with periodic maintenance
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 289
EP  - 302
VL  - 53
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018055/
DO  - 10.1051/ro/2018055
LA  - en
ID  - RO_2019__53_1_289_0
ER  - 
%0 Journal Article
%A Krim, Hanane
%A Benmansour, Rachid
%A Duvivier, David
%A Artiba, Abdelhakim
%T A variable neighborhood search algorithm for solving the single machine scheduling problem with periodic maintenance
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 289-302
%V 53
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018055/
%R 10.1051/ro/2018055
%G en
%F RO_2019__53_1_289_0
Krim, Hanane; Benmansour, Rachid; Duvivier, David; Artiba, Abdelhakim. A variable neighborhood search algorithm for solving the single machine scheduling problem with periodic maintenance. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 289-302. doi : 10.1051/ro/2018055. http://www.numdam.org/articles/10.1051/ro/2018055/

[1] F. Ángel-Bello, A. Álvarez, J. Pacheco and I. Martnez, A single machine scheduling problem with availability constraints and sequence-dependent setup costs. Appl. Math. Model. 35 (2011) 2041–2050. | DOI | MR | Zbl

[2] A. Artiba, F. Riane, M.A. Jamali, D. Ait-Kadi and R. Cléroux, Joint optimal periodic and conditional maintenance strategy. J. Qual. Main. Eng. 11 (2005) 107–114. | DOI

[3] S. Ashour, Sequencing Theory. Vol 69. Springer Science & Business Media. Springer Berlin, Heidelberg, New York (2012). | MR

[4] H. Belouadah, M.E. Posner and C.N. Potts, Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Appl. Math. 36 (1992) 213–231. | DOI | MR | Zbl

[5] M. Ben-Daya, D. Ait-Kadi, S.O. Duffuaa, J. Knezevic and A. Raouf, Handbook of maintenance management and engineering. Vol 7. Springer, Springer Dordrecht Heidelberg London New York (2009). | DOI

[6] 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. | DOI | MR | Zbl

[7] W.-J. Chen, Minimizing total flow time in the single-machine scheduling problem with periodic maintenance. J. Oper. Res. Soc. 57 (2006) 410–415. | DOI | Zbl

[8] W.-J. Chen, An efficient algorithm for scheduling jobs on a machine with periodic maintenance. Int. J. Adv. Manuf. Technol. 34 (2007) 1173–1182. | DOI

[9] R. Cruzan, Manager’s Guide to Preventive Building Maintenance. The Fairmont Press, INC. 711 Indian trail Lilburn, GA 300047 (1970).

[10] W.-W. Cui and Z. Lu, Minimizing the makespan on a single machine with flexible maintenances and jobs release dates. Comput. Oper. Res. 80 (2017) 11–22. | DOI | MR | Zbl

[11] A. Ebrahimy Zade and M. Bagher Fakhrzad, A dynamic genetic algorithm for solving a single machine scheduling problem with periodic maintenance. ISRN. Ind. Eng. 2013 (2013) 11.

[12] F.W. Glover and G.A. Kochenberger, Handbook of Metaheuristics. Vol 57, Springer Science & Business Media. Kluwer Academic Publishers. New York, Boston, Dordrecht, London, Moscow (2006). | MR

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

[14] P. Guo, W. Chen and Y. Wang, A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Preprint arXiv: 1301.7134 (2013). | MR | Zbl

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

[16] P. Hansen, N. Mladenović and D. Perez-Britos, Variable neighborhood decomposition search. J. Heuristics 7 (2001) 335–350. | DOI | Zbl

[17] K. Helsgaun, An effective implementation of K-opt moves for the Lin-Kernighan TSP heuristic. Ph.D. thesis, Roskilde University, Department of Computer Science (2006).

[18] A. Ilić, D. Urošević, J. Brimberg and N. Mladenović, A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem. Eur. J. Oper. Res. 206 (2010) 289–300. | DOI | MR | Zbl

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

[20] 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. | DOI | MR | Zbl

[21] H. Krim, R. Benmansour and D. Duvivier, Minimizing the weighted completion time on a single machine with periodic maintenance. In: ROADEF 2016, Compiégne, France (Februrary 2016).

[22] C.-Y. Lee and S.D. Liman, Single machine flow-time scheduling with scheduled maintenance. Acta Info. 29 (1992) 375–382. | DOI | MR | Zbl

[23] J.-Y. Lee and Y.-D. Kim, Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance. Comput. Oper. Res. 39 (2012) 2196–2205. | DOI | MR | Zbl

[24] H. Lei, G. Laporte and B. Guo, A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times. TOP 20 (2012) 99–118. | DOI | MR | Zbl

[25] C.-J. Liao and W.-J. Chen, Single-machine scheduling with periodic maintenance and nonresumable jobs. Comput. Oper. Res. 30 (2003) 1335–1347. | DOI | MR | Zbl

[26] C. Low, C.-J. Hsu and C.-T. Su, A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance. Expert Syst. Appl. 37 (2010) 6429–6434. | DOI

[27] W. Luo and F. Liu, On single-machine scheduling with workload-dependent maintenance duration. Omega 68 (2017) 119–122. | DOI

[28] A. Mjirda, R. Todosijevic, S. Hanafi, P. Hansen and N. Mladenovic, Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem. ITOR 24 (2017) 615–633. | MR | Zbl

[29] N. Mladenović and P. Hansen, Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097–1100. | DOI | MR | Zbl

[30] M.E. Posner, Minimizing weighted completion times with deadlines. Oper. Res. 33 (1985) 562–574. | DOI | MR | Zbl

[31] O. Roux, D. Duvivier, G. Quesnel and E. Ramat, Optimization of preventive maintenance through a combined maintenance-production simulation model. Int. J. Prod. Econ. 143 (2013) 3–12. | DOI

[32] W.E. Smith, Various optimizers for single-stage production. Nav. Res. Log. Q. 3 (1956) 59–66. | DOI | MR

[33] L.-H. Su and H.-M. Wang, Minimizing total absolute deviation of job completion times on a single machine with cleaning activities, Comput. Ind. Eng. 103 (2017) 242–249. | DOI

[34] R. Todosijevic, R. Benmansour, S. Hanafi, N. Mladenovic and A. Artiba, Nested general variable neighborhood search for the periodic maintenance problem. Eur. J. Oper. Res. 252 (2016) 385–396. | DOI | MR | Zbl

[35] M. Yazdani, A. Aleti, S.M. Khalili and F. Jolai, Optimizing the sum of maximum earliness and tardiness of the job shop scheduling problem. Comput. Ind. Eng. 107 (2017) 12–24. | DOI

Cité par Sources :