International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 3, No. 2, 8 Mar. 2011
Cover page and Table of Contents: PDF (size: 302KB)
Design and Application of A New Hybrid Heuristic Algorithm for Flow Shop Scheduling
Full Text (PDF, 302KB), PP.41-49
Views: 0 Downloads: 0
Author(s)
Fang Wang
1,2,*
Yun-qing Rao
1
Yu Hou
2
Index Terms
Heuristic algorithm, genetic algorithm, Benchmark problems test, initial population
Abstract
A new heuristic algorithm was designed by combining with Johnson method, NEH method and characteristics of scheduling, and it was implemented on MATLAB. The efficiency of the new algorithm was tested through eight Car questions and two Hel questions of Benchmark problems, and the results revealed that the new heuristic algorithm was better than the other three heuristic algorithms. Further more; the application of this heuristic algorithm in the intelligent algorithm especially in the genetic algorithms (GA) was discussed. Two GAs were designed for Flow Shop question, and they had the same processes and the same parameters. The only difference is in the production of the initial population. One GA’s initial population is optimized by the new heuristic algorithm, and the other whose initial population is randomly generated entirely. Finally, through the test of eight Car questions, it is demonstrated that the heuristic algorithm can indeed improve efficiency and quality of genetic algorithm because the heuristic algorithm can improve the initial population of GA.
Cite This Paper
Fang Wang, Yun-qing Rao, Yu Hou, "Design and Application of A New Hybrid Heuristic Algorithm for Flow Shop Scheduling", International Journal of Computer Network and Information Security(IJCNIS), vol.3, no.2, pp.41-49, 2011. DOI:10.5815/ijcnis.2011.02.06
Reference
[1]M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco 1979.
[2]K. R. Baker, Introduction to Sequencing and Scheduling, Wiley, New York, 1974.
[3]M. Nawaz, E. Enscore Jr and I. Ham, “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem,” Omega, 11(1), pp. 91–95, 1983.
[4]C. Koulamas, “A new constructive heuristic for the flowshop scheduling problem,” European Journal of Operational Research, 105, pp. 66–71, 1998.
[5]Wang Ling, Shop Scheduling with Genetic Algorithms(in chinese)，Tsinghua University Press,2003.
[6]F. A. Ogbu and D. K. Smith, “The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem,” Computers and Operations Research, 17(3), pp. 243–253, 1990.
[7]C. R. Reeves and T. Yamada, “Genetic algorithms, path relinking and the flowshop sequencing problem,” Evolutionary Computation, 6, pp. 45–60, 1998.
[8]J. Grabowski and J. Pempera, “New block properties for the permutation flowshop problem with application in tabu search,” Journal of Operational Research Society, 52, pp. 210–220, 2001.
[9]J. H. Holland, Adaptation in Nartural and Artifical System, MITPress, Massachusett 1975.
[10]D E.Goldberg, Genetic algorithms in search optimization and machine learning reading, Addison Wesley, MA 1989.
[11]L. Wang and D.-Z. Zheng, An Effective Hybrid Heuristic for Flow Shop Scheduling, Int J Adv Manuf Technol (2003) 21:38–44.
[12]Ceyda OG˘ UZ and M. Fikert Ercan, A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks, Journal of Scheduling 2005, 8, 323-351.
[13]K. A. De JONG, An analysis of the behavior of a class of genetic adaptive systems, University of Michigan, Michigan 1975.