A Heuristic Algorithm for Flowshop Scheduling Problem

Abstract:

Flow Shop Scheduling Problem is a class of scheduling problems with a work shop in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of machines in compliance with given processing orders. In this paper, we propose a new heuristic algorithm based on the analysis and research of which problem, the new method introducing a evaluate mechanism of the relative position of any two jobs to the completion time, and the efficiency and performance has been improved .The result of simulation experiments shows that, our new heuristic algorithm has good performance, and the average quality and stability of scheduling sequences generated by new method is significantly better than other heuristic algorithm which has the same complexity.

• Periodical: Advanced Materials Research (Volumes 591-593)
• Pages: 626-630
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.591-593.626
• Online since: November 2012
• Authors: Dan Tang, Hong Ping Shu
• Keywords: Flow Shop, Heuristic Algorithm , NEH, Production Scheduling

References

[1] Garey M R,Johnson D S,Scthi R R.The complexity of flowshop and jobshop scheduling.Math Opns Res,1976,1:117-129.

[2] Baker K R. Introduction to sequencing and scheduling[M] .New York: Wiley, 1974.

[3] L. Wang, L. Zhang and D.-Z. Zheng, An effective hybrid genetic algorithm for flow shop scheduling with limited buffers, Computers & Operations Research, vol. 33, no. 10, pp.2960-2971, 2006.

DOI: 10.1016/j.cor.2005.02.028

[4] Kuo I H,Horng S J,Kao T W,et al. An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model[J]. Expert Systems with Applications, 2009, 36(3): 7027-7032.

DOI: 10.1016/j.eswa.2008.08.054

[5] Guenther Fuellerer, Karl F. Doerner, Richard F. Hartl, Manuel Iori. Ant colony optimization for the two-dimensional loading vehicle routing problem. Computers & Operations Research, Vol. 36, No. 3. (March 2009), pp.655-673.

DOI: 10.1016/j.cor.2007.10.021

[6] Palmer D S. Sequencing Jobs through a Multi-Stage Process in the Minimum Total Time- a Quick Method of Obtaining a near Optimum [J]. Operational Research Quarterly, 1965, 16: 101-107.

DOI: 10.1057/jors.1965.8

[7] Gupta J. A Functional Heuristic Algorithm for the Flowshop Scheduling Problem [J]. Operational Research Quarterly, 1971, 22: 39-47.

DOI: 10.2307/3008015

[8] Campbell H G, Dudek R A, Smith M L. A Heuristic Algorithm for the n-Job, m-Machine Scheduling Problem. [J]. Management Science, 1970, 16:630 - 637.

DOI: 10.1287/mnsc.16.10.b630

[9] Dannenbring D G. An Evaluation of Flow Shop Sequencing Heuristics [J]. Management Science, 1977, 23(11): 1174-1182.

DOI: 10.1287/mnsc.23.11.1174

[10] Nawaz M, Enscore E, Ham I. A Heuristic Algorithm for the m Machine, n Job Flow Shop [J]. OMEGA: The International Journal of Management Sciences, 1983, 11(1): 91-95.

DOI: 10.1016/0305-0483(83)90088-9

[11] Dong X Y,Huang H K,Chen P. Study on heuristics for the permutation flowshop with sequence dependent setup times[C] .EEE IRI2009. Las Vegas,USA. 2009.

DOI: 10.1109/iri.2009.5211589