An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems

被引:101
作者
Engin, Orhan [1 ]
Ceran, Gulsad [1 ]
Yilmaz, Mustafa K. [1 ]
机构
[1] Selcuk Univ, Dept Ind Engn, Fac Eng & Architecture, Konya, Turkey
关键词
Hybrid flow shop; Multiprocessor task scheduling problems; Genetic algorithm; Design of experiment; BOUND ALGORITHM; 2-STAGE; BRANCH; OPTIMIZATION;
D O I
10.1016/j.asoc.2010.12.006
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The hybrid flow shop scheduling with multiprocessor task (HFSMT) problem is a substantial production scheduling problem for minimizing the makespan, and there exist many difficulties in solving large scale HFSMT problems which include many jobs, machines and tasks. The HFSMT problems known as NP-hard and the proposal of an efficient genetic algorithm (GA) were taken into consideration in this study. The numerical results prove that the computational performance of a GA depends on the factors of initial solution, reproduction, crossover, and mutation operators and probabilities. The implementation details, including a new mutation operator, were described and a full factorial experimental design was determined with our GA program by using the best values of the control parameters and the operators. After a comparison was made with the studies of Oguz [1], Oguz and Ercan [2] and Kahraman et al. [3] related to the HFSMT problems, the computational results indicated that the proposed genetic algorithm approach is very effective in terms of reduced total completion time or makespan (C-max) for the attempted problems. (C) 2010 Elsevier B. V. All rights reserved.
引用
收藏
页码:3056 / 3065
页数:10
相关论文
共 40 条
[1]   Using ant colony optimization to solve hybrid flow shop scheduling problems [J].
Alaykyran, Kemal ;
Engin, Orhan ;
Doyen, Alper .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2007, 35 (5-6) :541-550
[2]   Scheduling multi-stage parallel-processor services to minimize average response time [J].
Allahverdi, A ;
Al-Anzi, FS .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2006, 57 (01) :101-110
[3]   Scheduling two-stage hybrid flow shop with availability constraints [J].
Allaoui, H ;
Artiba, A .
COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (05) :1399-1419
[4]   Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints [J].
Allaoui, H ;
Artiba, A .
COMPUTERS & INDUSTRIAL ENGINEERING, 2004, 47 (04) :431-450
[5]  
Back T., 1997, IEEE Transactions on Evolutionary Computation, V1, P3, DOI 10.1109/4235.585888
[6]   BRANCH AND BOUND ALGORITHM FOR THE FLOW-SHOP WITH MULTIPLE PROCESSORS [J].
BRAH, SA ;
HUNSUCKER, JL .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1991, 51 (01) :88-99
[7]   Tsp-based scheduling in a batch-wise hybrid flow-shop [J].
Caricato, P. ;
Grieco, A. ;
Serino, D. .
ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING, 2007, 23 (02) :234-241
[8]   Adaptive multi-objective genetic algorithms for scheduling of drilling operation in printed circuit board industry [J].
Chang, Pei-Chann ;
Hsieh, Jih-Chang ;
Wang, Chih-Yuan .
APPLIED SOFT COMPUTING, 2007, 7 (03) :800-806
[9]   A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies [J].
Cheng, RW ;
Gen, M ;
Tsujimura, Y .
COMPUTERS & INDUSTRIAL ENGINEERING, 1999, 36 (02) :343-364
[10]   An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem [J].
De Giovanni, L. ;
Pezzella, F. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 200 (02) :395-408