The flow shop with parallel machines: A tabu search approach

被引:112
作者
Nowicki, E [1 ]
Smutnicki, C [1 ]
机构
[1] Wroclaw Univ Technol, Inst Engn Cybernet, PL-50372 Wroclaw, Poland
关键词
scheduling; heuristics; flexible flow line; flow-shop; parallel machines; tabu search;
D O I
10.1016/S0377-2217(97)00260-9
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
A fast and easily implementable approximation algorithm for the problem of finding a minimum makespan in a flow shop with parallel machines is presented. The algorithm is based on a tabu search technique with a specific neighborhood definition which employs notions of a critical path in a graph and a block of jobs. This is the first improvement algorithm for the considered problem. A special advanced method of implementation improves the local search significantly and increases the speed of the algorithm. Computational experiments (up to 3000 operations and 60 machines) show its excellent numerical properties. The proposed approach can be used for modeling and solving a broad class of flexible flow line scheduling problems. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:226 / 253
页数:28
相关论文
共 17 条
[1]  
Battiti R., 1994, ORSA Journal on Computing, V6, P126, DOI 10.1287/ijoc.6.2.126
[2]   ANALYSIS OF CLASSES OF HEURISTICS FOR SCHEDULING A 2-STAGE FLOW-SHOP WITH PARALLEL MACHINES AT ONE-STAGE [J].
CHEN, B .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1995, 46 (02) :234-244
[3]   HEURISTICS FOR SCHEDULING FLEXIBLE FLOW LINES [J].
DING, FY ;
KITTICHARTPHAYAK, D .
COMPUTERS & INDUSTRIAL ENGINEERING, 1994, 26 (01) :27-34
[4]   FUTURE PATHS FOR INTEGER PROGRAMMING AND LINKS TO ARTIFICIAL-INTELLIGENCE [J].
GLOVER, F .
COMPUTERS & OPERATIONS RESEARCH, 1986, 13 (05) :533-549
[5]  
Glover F., 1989, ORSA Journal on Computing, V1, P190, DOI [10.1287/ijoc.2.1.4, 10.1287/ijoc.1.3.190]
[6]   COMPARATIVE PERFORMANCE ANALYSIS OF PRIORITY RULES IN A CONSTRAINED FLOW-SHOP WITH MULTIPLE PROCESSORS ENVIRONMENT [J].
HUNSUCKER, JL ;
SHAH, JR .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 72 (01) :102-114
[7]  
Labetoulle J., 1984, Progress in combinatorial optimization, P245
[8]   A fast tabu search algorithm for the permutation flow-shop problem [J].
Nowicki, E ;
Smutnicki, C .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 91 (01) :160-175
[9]   A fast taboo search algorithm for the job shop problem [J].
Nowicki, E ;
Smutnicki, C .
MANAGEMENT SCIENCE, 1996, 42 (06) :797-813
[10]  
Reeves, 1993, Modern Heuristic Techniques for Combinatorial Problems, P70