A Hybrid Genetic Algorithm for Flexible Job-Shop Scheduling Problem

Abstract:

In this paper, a hybrid genetic algorithm is presented for the flexible job-shop scheduling problem with makespan criterion. A new machine assignment strategy is proposed to improve the initial population. A modified coding scheme is presented, and a population improvement strategy is performed when the best solution of the population did not improve during some generations. This hybrid algorithm is tested on a series of benchmarks instances. Experimental results show that this hybrid algorithm is efficient and competitive compared to some existing methods.

• Periodical: Advanced Materials Research (Volumes 889-890)
• Pages: 1179-1184
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.889-890.1179
• Online since: February 2014
• Authors: Shuang Xi Wang*, Chao Yong Zhang, Liang Liang Jin
• Keywords: Flexible Job-Shop Scheduling Problem, Genetic Algorithm (GA), Initialization, Population Improvement

References

[1] Li T-K, Wang W-L, Zhang W-X. Solving flexible job shop scheduling problem based on cultural genetic algorithm. Computer Integrated Manufacturing Systems. 2010; 16(4): 861-6.

[2] Lin T-L, Horng S-J, Kao T-W, Chen Y-H, Run R-S, Chen R-J, et al. An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Systems with Applications. 2010; 37(3): 2629-36.

DOI: 10.1016/j.eswa.2009.08.015

[3] Li J-Q, Pan Q-K, Suganthan P, Chua T. A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem. The International Journal of Advanced Manufacturing Technology. 2011; 52(5-8): 683-97.

DOI: 10.1007/s00170-010-2743-y

[4] Kacem I, Hammadi S, Borne P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on. 2002; 32(1): 1-13.

DOI: 10.1109/tsmcc.2002.1009117

[5] Pezzella F, Morganti G, Ciaschetti G. A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research. 2008; 35(10): 3202-12.

DOI: 10.1016/j.cor.2007.02.014

[6] Liu A, Yang Y, Deng Q, Lu H, Zhang Y, Zhou Z, et al. Dynamic scheduling on multi-objective flexible Job Shop. Computer Integrated Manufacturing Systems. 2011; 17(12): 2629-37.

[7] SHl G. A genetic algorithm applied to a classic job-shop scheduling problem. International Journal of Systems Science. 1997; 28(1): 25-32.

DOI: 10.1080/00207729708929359

[8] Brandimarte P. Routing and scheduling in a flexible job shop by tabu search. Annals of Operations research. 1993; 41(3): 157-83.

DOI: 10.1007/bf02023073

[9] Chen H, Ihlow J, Lehmann C. A genetic algorithm for flexible job-shop scheduling. Robotics and Automation, 1999 Proceedings 1999 IEEE International Conference on; 1999: IEEE; 1999. pp.1120-5.

DOI: 10.1109/robot.1999.772512

[10] Jia H, Nee A, Fuh J, Zhang Y. A modified genetic algorithm for distributed scheduling problems. Journal of Intelligent Manufacturing. 2003; 14(3-4): 351-62.