A bottleneck-based heuristic for minimizing makespan in a flexible flow line with unrelated parallel machines

被引:38
作者
Chen, Chun-Lung [1 ]
Chen, Chuen-Lung [2 ]
机构
[1] Takming Univ Sci & Technol, Dept Accounting Informat, Taipei 11451, Taiwan
[2] Natl Chengchi Univ, Dept MIS, Taipei 11605, Taiwan
关键词
Bottleneck-based multiple insertion heuristic; Flexible flow line; Bottleneck; Unrelated parallel machines; Makespan; SCHEDULING HYBRID FLOWSHOPS; MULTIPLE PROCESSORS; SETUP TIMES; GENETIC ALGORITHM; SEQUENCING HEURISTICS; DUAL CRITERIA; SHOP PROBLEMS; RULES; TARDINESS; JOBS;
D O I
10.1016/j.cor.2009.02.004
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This study developed a bottleneck-based heuristic (BBFFL) to solve a flexible flow line problem with a bottleneck stage, where unrelated parallel machines exist in all the stages, with the objective of minimizing the makespan. The essential idea of BBFFL is that scheduling jobs at the bottleneck stage may affect the performance of a heuristic for scheduling jobs in all the stages. Therefore, in BBFFL, a variant of Johnson's rule is used to develop a bottleneck-based initial sequence generator (BBISG). Then, a bottleneck-based multiple insertion procedure (BBMIP) is applied to the initial sequence to control the order by which jobs enter the bottleneck stage to be the same as that at the first stage. Five experimental factors were used to design 243 different production scenarios and 10 test problems were randomly generated in each scenario. These test problems were used to compare the performance of BBFFL with several well-known heuristics. Computational results show that the BBFFL significantly outperforms all the well-known heuristics. (C) 2009 Elsevier Ltd. All rights reserved.
引用
收藏
页码:3073 / 3081
页数:9
相关论文
共 53 条
[1]   BPSS - A SCHEDULING SUPPORT SYSTEM FOR THE PACKAGING INDUSTRY [J].
ADLER, L ;
FRAIMAN, N ;
KOBACKER, E ;
PINEDO, M ;
PLOTNICOFF, JC ;
WU, TP .
OPERATIONS RESEARCH, 1993, 41 (04) :641-648
[2]   Scheduling of flexible flow lines in an automobile assembly plant [J].
Agnetis, A ;
Pacifici, A ;
Rossi, F ;
Lucertini, M ;
Nicoletti, S ;
Nicolo, F ;
Oriolo, G ;
Pacciarelli, D ;
Pesaro, E .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 97 (02) :348-362
[3]   An immune algorithm approach to the scheduling of a flexible PCB flow shop [J].
Alisantoso, D ;
Khoo, LP ;
Jiang, PY .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2003, 22 (11-12) :819-827
[4]   A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation [J].
Bertel, S ;
Billaut, JC .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 159 (03) :651-662
[5]   Comparison of scheduling rules in a flow shop with multiple processors: A simulation [J].
Brah, SA ;
Wheeler, GE .
SIMULATION, 1998, 71 (05) :302-311
[6]   Heuristics for scheduling in a flow shop with multiple processors [J].
Brah, SA ;
Loo, LL .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 113 (01) :113-122
[7]  
Campbell HerbertG., 1970, Management Science, V16, P630, DOI [10.1287/mnsc.16.10.b630, DOI 10.1287/MNSC.16.10.B630]
[8]   Bottleneck-based heuristics to minimize tardy jobs in a flexible flow line with unrelated parallel machines [J].
Chen, Chun-Lung ;
Chen, Chuen-Lung .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2008, 46 (22) :6415-6430
[9]  
Chen CL, 1998, INT J IND ENG-APPL P, V5, P157
[10]  
Chen YC, 1998, INT J IND ENG-THEORY, V5, P288