A Genetic Algorithm to Schedule the Flow Shop Problem under Preventive Maintenance Activities

Authors: J. Kaabi, Y. Harrath

Abstract:

This paper studied the flow shop scheduling problem under machine availability constraints. The machines are subject to flexible preventive maintenance activities. The nonresumable scenario for the jobs was considered. That is, when a job is interrupted by an unavailability period of a machine it should be restarted from the beginning. The objective is to minimize the total tardiness time for the jobs and the advance/tardiness for the maintenance activities. To solve the problem, a genetic algorithm was developed and successfully tested and validated on many problem instances. The computational results showed that the new genetic algorithm outperforms another earlier proposed algorithm. 

Keywords: Flow shop scheduling, maintenance, genetic algorithm, priority rules.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1338460

References:

[1] M. Ben Ali, M. Sassi, M. Gossa, and Y. Harrath, “Simultaneous scheduling of production and maintenance tasks in the job shop”, International Journal of Production Research, vol. 49, pp. 3891-3918, 2011.
[2] M. Kubzin, C. Potts, and V. Strusevich, “Approximation results for flow shop scheduling problems with machine availability constraints,” Computers & Operations Research, vol 36, pp. 379-390, 2009.
[3] T. C. E. Cheng, and G. Wang, “An improved heuristic for the twomachine flowshop scheduling with an availability constraint”, Operations Research Letters, vol 26, pp. 223-229, 2000.
[4] C.-Y. Lee, “Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint,” Operations. Research. Letter, vol 20, pp. 129–139, 1997.
[5] F. Hnaien, F. Yalaoui, and A. Mhadhbi, “Makespan minimization on a two-machine flowshop with an availability constraint on the first machine,” International Journal of Production Economics, vol 164, pp. 95-104, 2015.
[6] J. Blazewicz, J. Breit, P. Formanowicz, W. Kubiak, and G. Schmidt, “Heuristic algorithms for the two-machine flow shop with limited machine availability,” The International Journal of Management Science, vol 29, pp. 599-608, 2001.
[7] W. Kubiak, J. Blazewicz, P. Formanowicz, J. Breit, and G. Schmidt, 2002. “Two-machine flow shops with limited machine availability,” European Journal of Operational Research vol 136, pp. 528-540, 2002.
[8] X. Wang, and J. Xie, “Two-stage flexible flow shop scheduling with limited machine availability,” First Int. Conf. on Information and Management Sciences, Xi’an, China, 2002.
[9] R. Aggoune, “Ordonnancement d’ateliers sous contraintes de disponibilité des machines,” Ph.D diss., University of Metz, France, 2002.
[10] B. Naderi, M. Zandieh, and M. Aminnayeri, “Incorporating periodic preventive maintenance into flexible flowshop scheduling problems”, Applied Soft Computing, vol 11, pp. 2094-2101, 2011.
[11] D. Golberg, Genetic algorithms in search, optimization and machine learning. Inc, 1989.
[12] L. Davis, “Job shop scheduling with genetic algorithm,” 1st Int. Conf. on Genetic Algorithms and their applications, Lawrence Erlbaum (ED.), Hillsdale, New Jersey, 1985.
[13] C. Y. Lee and Z-L. Chen, “Scheduling jobs and maintenance activities on parallel machines,” Naval Research Logistics, vol 47, pp. 145-165, 2000.
[14] Y. Xu, Y. Tian, and N. Sannomiya, “Three-stage tabu search for solving large-scale flow shop scheduling problems,” Transactions of Institute of Electrical Engineers of Japan, vol 3, pp. 601-608, 2003.
[15] J. Kaabi, C. Varnier, and N. Zerhouni, 2004. “Ordonnancement conjoint de la production et de la maintenance dans un flow shop”, 5ème conférence francophone de Modélisation et Simulation, Nantes, France, 2004.