A DE-Based Hybrid Algorithm for the Flexible Job-Shop Scheduling Problem

Abstract:

Article Preview

This paper presents a hybrid algorithm to address the flexible job-shop scheduling problem (FJSP). Based on Differential Evolution (DE), a global search method is introduced in the hybrid algorithm, where variations are made to the mutation and crossover operators in DE, according to the quantum rotation gate. And an Interchange-based local search method is further adopted in the proposed algorithm to gain a better performance. Experiments are performed to show the efficiency of the proposed algorithm.

Info:

Periodical:

Edited by:

Dayun Xu

Pages:

502-507

DOI:

10.4028/www.scientific.net/AMR.630.502

Citation:

H. Y. Wang "A DE-Based Hybrid Algorithm for the Flexible Job-Shop Scheduling Problem", Advanced Materials Research, Vol. 630, pp. 502-507, 2013

Online since:

December 2012

Authors:

Export:

Price:

$38.00

[1] John B. Chambers, J. Wesley Barnes. Reactive Search for Flexible Job Shop Scheduling. Graduate program in operations research and industrial engineering. The University of Texas at Austin, technical report series ORP98-100, (1996).

[2] Kacem I, Hammadi S, Borne P. Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job-Shop Scheduling Problems. IEEE Transactions on Systems, Man and Cybemetics, Part C, 2002, 32(1): 408-419.

DOI: 10.1109/tsmcc.2002.1009117

[3] Zhang HP, Gen M. Multistage-Based Genetic Algorithm for Flexible Job-Shop Scheduling Problem. Complexity International 2005; 11: 223-232.

[4] Zhang CY, Rao YQ, et al. Bilevel Genetic Algorithm for the Flexible Job-Shop Scheduling Problem. Chinese Journal of Mechanical Engineering 2007; 43(4): 119-124.

DOI: 10.3901/jme.2007.04.119

[5] Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB. Sequencing and scheduling: Algorithms and complexity. Handbook in Operations Research and Management Science, 1993, 4: 445–522.

DOI: 10.1016/s0927-0507(05)80189-6

[6] Storn R., Price K. Differential Evolution-A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[R]. Technical Report TR-95-012, ICSI, 1995. 3.

[7] Onwubolu G, Davendra D. Scheduling flow shops using differential evolution algorithm. European Journal of Operational Research 2006; 171(2): 674-692.

DOI: 10.1016/j.ejor.2004.08.043

[8] Wang L, Pan QK, Suganthan PN, Wang WH, Wang YM. A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems. Computers & Operations Research 2010; 37(3): 509-520.

DOI: 10.1016/j.cor.2008.12.004

[9] Qian B, Wang L, Huang DX et al. Scheduling multi-objective job shops using a memetic algorithm based on differential evolution. International Journal of Advanced Manufacturing Technology 2008; 35(9-10): 1014-1027.

DOI: 10.1007/s00170-006-0787-9

[10] Nearchou AC. A differential evolution approach for the common due date early/tardy job scheduling problem. Computers & Operations Research 2008; 35(4): 1329-1343.

DOI: 10.1016/j.cor.2006.08.013

[11] Liu B, Wang L, Jin YH. Advances in differential evolution. Control and Decision 2007; 22(7): 721-729.

[12] Godfrey C. Onwubolu, Donald Davendra. Differential Evolution: A Handbook for Global Permutation-Based Combinatorial Optimization, first ed., Springer, Berlin, (2009).

DOI: 10.1007/978-3-540-92151-6

In order to see related information, you need to Login.