The Hybrid Genetic Algorithm of Single-Machine Materials Manufacturing Process with Periodic Maintenance

Abstract:

This paper investigates single machine materials manufacturing process with periodic maintenance, which has been proved as a NP-hard problem. Such that, combining the advantages of the classic List Scheduling (LS) algorithm, the Longest Processing Time first (LPT) algorithm and the genetic algorithm, two hybrid genetic algorithm (LS-GENETIC algorithm and LPT-GENETIC algorithm) were proposed to solve the problem. Computational results have shown that both LS-GENETIC algorithm and LPT-GENETIC algorithm perform satisfactorily.

• Periodical: Applied Mechanics and Materials (Volume 142)
• Pages: 16-19
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.142.16
• Online since: November 2011
• Authors: Xian Yu Yu, Zhi Yong Rao, Hui Zhu
• Keywords: Computational Complexity, Hybrid Genetic Algorithm, Maintenance

References

[1] J. Breit, Improved approximation for non-preemptive single machine flow time scheduling with an availability constraint, European Journal of Operational Research vol. 183 (2007), p.516–524.

DOI: 10.1016/j.ejor.2006.10.005

[2] T.C.E. Cheng, G. Wang, Two-machine flowshop scheduling with consecutive availability constraints, Information Processing Letters vol. 71 (1999), p.49–54.

DOI: 10.1016/s0020-0190(99)00094-0

[3] T.C.E. Cheng, G. Wang, An improved heuristic for two-machine flowshop scheduling with an availability constraint, Operations Research Letters vol. 26 (2000), p.223–229.

DOI: 10.1016/s0167-6377(00)00033-x

[4] S. Gawiejnowicz, Scheduling deteriorating jobs subject to job or machine availability constraints, European Journal of Operational Research vol. 180 (2007), p.472–478.

DOI: 10.1016/j.ejor.2006.04.021

[5] I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering. Vol. 54 (2008), p.401–410.

DOI: 10.1016/j.cie.2007.08.005

[6] Ji, M., He, Y., Cheng, T.C.E., Single-machine scheduling with periodic maintenance to minimize makespan., Comput. Oper. Res. Vol. 34 (2007), pp.1764-1770.

DOI: 10.1016/j.cor.2005.05.034

[7] Lee, C.Y., Machine scheduling with an availability constraint., Journal of Global Optimization, vol. 9 (1996), pp.395-416.

[8] Liao CJ, Chen WJ. Single-machine scheduling with periodic maintenance and nonresumable jobs. Comput. Oper. Res. Vol. 30 (2003), p.1335–47.

DOI: 10.1016/s0305-0548(02)00074-6

[9] Xu DH, Sun KB, Li HX. Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan. Comput. Oper. Res. Vol. 35 (2008), p.1344 – 1349.

DOI: 10.1016/j.cor.2006.08.015