Using a Hybrid Genetic Algorithm to Minimize the Number of Tardy Jobs in the Flow Shop

Abstract:

Numerous real-world problems relating to flow shops scheduling are complex. The main problem is that the solution space is very large and therefore the set of feasible solutions cannot be enumerated one by one. Current approaches to solve these problems are metaheuristics techniques, which fall in two categories: population-based search and trajectory-based search. Because of their complexity, recent research has turned to genetic algorithms to address such problems. In this paper we present an effective hybrid approach based on genetic algorithm (GA) for minimizing the number of tardy jobs in a flow shop consisting of m machines. Jobs with processing times and due dates randomly arrive to the system. We assume that job arrival or release dates are not known in advance. The objective is to minimize the number of tardy jobs. Although genetic algorithms have been proven to facilitate the entire space search, they lack in fine-tuning capability for obtaining the global optimum. Therefore the proposed approach incorporates a fitness functions and a population trained by a local improvement search based on tabu search with a candidate list strategy into GA for the problem which belongs to NP-hard class. Experimentation results show that the number of cells and the crossover strategy adapted affect the number of tardy jobs found. The results also indicate that hybrid genetic algorithm approach improves the solution quality drastically.

• Periodical: Advanced Materials Research (Volumes 201-203)
• Pages: 1070-1074
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.201-203.1070
• Online since: February 2011
• Authors: Jing Jing Wu
• Keywords: Flow Shop, Hybrid Genetic Algorithm, Scheduling, Tabu Search, Tardy Job

References

[1] J. Moore: Management Science. Vol. 15 (1968), p.102.

[2] W. Maxwell: Management Science. Vol. 16 (1970), p.295.

[3] J.G. Shanthikumar: Computers and Operations Research. Vol. 10 (1983), p.255.

[4] J.H. Holland, in: Adaptation in Natural and Artificial Systems, edited by University of Michigan Press, Cambridge(1992).

[5] R.L. Houpt, S.E. Houpt, in: Practical Genetic Algorithms, edited by Wiley Publication, New York(1998).

[6] C Chen, V.S. Vempati, N. Aljaber: European Journal of Operational Research. Vol. 80 (1995), p.389.

[7] C.R. Reeves: Computers and Operations Research. Vol. 22 (1995), p.5.

[8] C. Prins: Mathematical Methods of Operations Research. Vol. 52 (2000), p.389.

[9] S.M. Lee, A.A. Asllani: Omega. Vol. 32 (2004), p.145.

[10] T. Aldowaisan, A. Allahverdi: Omega. Vol. 32 (2004), p.345.

[11] R. Ruiz, C. Maroto: Omega. Vol. 34 (2006), p.461.

[12] J.W. Barnes, M. Laguna: IIE Transactions. Vol. 25 (1993), p.121.

[13] U. Bilge, F. Kirac, M. Kurtulan: Computers and Operations Research. Vol. 31 (2004), p.397.