A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines

被引:182
作者
Cochran, JK [1 ]
Horng, SM [1 ]
Fowler, JW [1 ]
机构
[1] Arizona State Univ, Dept Ind Engn, Tempe, AZ 85287 USA
基金
美国国家科学基金会;
关键词
genetic algorithms; multiple objectives; parallel machine scheduling;
D O I
10.1016/S0305-0548(02)00059-X
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
In this paper we propose a two-stage multi-population genetic algorithm (MPGA) to solve parallel machine scheduling problems with multiple objectives. In the first stage, multiple objectives are combined via the multiplication of the relative measure of each objective. Solutions of the first stage are arranged into several sub-populations, which become the initial populations of the second stage. Each sub-population then evolves separately while an elitist strategy preserves the best individuals of each objective and the best individual of the combined objective. This approach is applied in parallel machine scheduling problems with two objectives: makespan and total weighted tardiness (TWT). The MPGA is compared with a benchmark method, the multi-objective genetic algorithm (MOGA), and shows better results for all of the objectives over a wide range of problems. The MPGA is extended to scheduling problems with three objectives: makespan, TWT, and total weighted completion times (TWC), and also performs better than MOGA.
引用
收藏
页码:1087 / 1102
页数:16
相关论文
共 16 条
[1]   A genetic algorithm approach to optimization for the radiological worker allocation problem [J].
Chen, Y ;
Narita, M ;
Tsuji, M ;
Sa, S .
HEALTH PHYSICS, 1996, 70 (02) :180-186
[2]   USING GENETIC ALGORITHMS TO SOLVE A MULTIOBJECTIVE GROUNDWATER MONITORING PROBLEM [J].
CIENIAWSKI, SE ;
EHEART, JW ;
RANJITHAN, S .
WATER RESOURCES RESEARCH, 1995, 31 (02) :399-409
[3]  
FOWLER JW, 2000, INT J MANUFACTURING, V1, P3
[4]  
FRY TD, 1989, OMEGA, V17, P594
[5]  
Gross D., 1988, FUNDAMENTALS QUEUEIN, V3rd
[6]   A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines [J].
Hyun, CJ ;
Kim, Y ;
Kim, YK .
COMPUTERS & OPERATIONS RESEARCH, 1998, 25 (7-8) :675-690
[7]  
Jaszkiewicz A., 1997, Foundations of Computing and Decision Sciences, V22, P169
[8]  
Lee C. Y., 1993, Complexity in numerical optimization, P269
[9]   A MULTI-OBJECTIVE PRODUCTION PLANNING-MODEL IN A FLEXIBLE MANUFACTURING ENVIRONMENT [J].
LEE, SM ;
JUNG, HJ .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1989, 27 (11) :1981-1992
[10]   A comparison of neighborhood search techniques for multi-objective combinatorial problems [J].
Marett, R ;
Wright, M .
COMPUTERS & OPERATIONS RESEARCH, 1996, 23 (05) :465-483