Genetic algorithm integrated with artificial chromosomes for multi-objective flowshop scheduling problems

被引:48
作者
Chang, Pei-Chann [1 ]
Chen, Shih-Hsin [2 ]
Fan, Chin-Yuan [2 ]
Chan, Chien-Lung [1 ]
机构
[1] Yuan Ze Univ, Dept Informat Management, Chungli, Taiwan
[2] Yuan Ze Univ, Dept Ind Engn & Management, Chungli, Taiwan
关键词
Genetic algorithm; Flowshop scheduling; Makespan; Maximum tardiness; NSGA II;
D O I
10.1016/j.amc.2008.05.027
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Recently, a wealthy of research works has been dedicated to the design of effective and efficient genetic algorithms in dealing with multi-objective scheduling problems. In this paper, an artificial chromosome generating mechanism is designed to reserve patterns of genes in elite chromosomes and to find possible better solutions. The artificial chromosome generating mechanism is embedded in simple genetic algorithm (SGA) and the non-dominated sorting genetic algorithm (NSGA-II) to solve single-objective and multiobjective flowshop-scheduling problems, respectively. The single-objective problems are to minimize the makespan while the multi-objective scheduling problems are to minimize the makespan and the maximum tardiness. Extensive numerical studies are conducted and the results indicate that artificial chromosomes embedded with SGA and NSGAII are able to further speed up the convergence of the genetic algorithm and improve the solution quality. This promising result may be of interests to industrial practitioners and academic researchers in the field of evolutionary algorithm or machine scheduling. (C) 2008 Elsevier Inc. All rights reserved.
引用
收藏
页码:550 / 561
页数:12
相关论文
共 40 条
[31]   A step forward in studying the compact Genetic Algorithm [J].
Rastegar, Reza ;
Hariri, Arash .
EVOLUTIONARY COMPUTATION, 2006, 14 (03) :277-289
[32]   Genetic Algorithms, Path Relinking, and the Flowshop Sequencing Problem [J].
Reeves, Colin R. ;
Yamada, Takeshi .
EVOLUTIONARY COMPUTATION, 1998, 6 (01) :45-60
[33]   A GENETIC ALGORITHM FOR FLOWSHOP SEQUENCING [J].
REEVES, CR .
COMPUTERS & OPERATIONS RESEARCH, 1995, 22 (01) :5-13
[34]   An evolutionary artificial immune system for multi-objective optimization [J].
Tan, K. C. ;
Goh, C. K. ;
Mamun, A. A. ;
Ei, E. Z. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 187 (02) :371-392
[35]  
Tsutsui S., 2006, INT J HYBRID INTELLI, V3, P11
[36]   An effective hybrid genetic algorithm for flow shop scheduling with limited buffers [J].
Wang, L ;
Zhang, L ;
Zheng, DZ .
COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (10) :2960-2971
[37]   An effective hybrid heuristic for flow shop scheduling [J].
D.-Z. Zheng ;
L. Wang .
The International Journal of Advanced Manufacturing Technology, 2003, 21 (1) :38-44
[38]   An evolutionary algorithm with guided mutation for the maximum clique problem [J].
Zhang, QF ;
Sun, JY ;
Tsang, E .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2005, 9 (02) :192-200
[39]   Combinations of estimation of distribution algorithms and other techniques [J].
Zhang Q. ;
Sun J. ;
Tsang E. .
International Journal of Automation and Computing, 2007, 4 (3) :273-280
[40]  
ZITZLER E, 2004, P WORKSH MULT OBJ ME