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

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. 

• J. Kaabi
• Y. Harrath

• Flow shop scheduling
• maintenance
• genetic algorithm
• priority rules.

[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.