NEIGHBORHOOD SEARCH-BASED OPTIMIZATION ALGORITHMS FOR PRODUCTION SCHEDULING - A SURVEY

被引:5
作者
BRANDIMARTE, P
机构
[1] Dipartimento di Automatica e Informatica, Politecnico di Torino, 10129 Torino
来源
COMPUTER INTEGRATED MANUFACTURING SYSTEMS | 1992年 / 5卷 / 02期
关键词
NEIGHBORHOOD SEARCH; OPTIMIZATION ALGORITHMS; COMPUTER-INTEGRATED MANUFACTURING;
D O I
10.1016/0951-5240(92)90010-A
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Neighbourhood search is one of the general strategies used in designing heuristic algorithms for discrete optimization. Apart from its simplicity from the conceptual and implementation point of view, a notable characteristic of neighbourhood search is its generality: no assumption is made about the objective and the constraints, whereas other heuristic methods depend on the particular problem at hand. Neighbourhood search is, to say the least, mathematically unexciting, and for many problems specific heuristic algorithms exist with better performance. However, from a practical point of view, the ease of conception and implementation of a neighbourhood search algorithm make it a most interesting candidate for the quick prototyping of optimization software for many domains, including manufacturing. These characteristics have justified the continuous interest in neighbourhood search. Some algorithms have been proposed to overcome the greatest shortcoming of neighbourhood search, i.e. the tendency to get stuck in a local minimum. In this paper the two most interesting neighbourhood search-based algorithms, simulated annealing and tabu search, are presented and evaluated by comparing them with an exact algorithm for a simple scheduling problem. Due to the complexity of optimization problems encountered in the CIM world, the practitioner will find these algorithms a most useful tool.
引用
收藏
页码:167 / 176
页数:10
相关论文
共 34 条
[1]   THE SHIFTING BOTTLENECK PROCEDURE FOR JOB SHOP SCHEDULING [J].
ADAMS, J ;
BALAS, E ;
ZAWACK, D .
MANAGEMENT SCIENCE, 1988, 34 (03) :391-401
[2]   COMPARATIVE STUDY OF FLOW-SHOP ALGORITHMS [J].
BAKER, KR .
OPERATIONS RESEARCH, 1975, 23 (01) :62-73
[3]   HYBRID HIERARCHICAL SCHEDULING AND CONTROL-SYSTEMS IN MANUFACTURING [J].
BONA, B ;
BRANDIMARTE, P ;
GRECO, C ;
MENGA, G .
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1990, 6 (06) :673-686
[4]  
BRANDIMARTE P, 1987, 3RD C SIM MAN TOR, P235
[5]   A BOTTLENECK-BASED BEAM SEARCH FOR JOB SCHEDULING IN A FLEXIBLE MANUFACTURING SYSTEM [J].
CHANG, YL ;
MATSUO, H ;
SULLIVAN, RS .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1989, 27 (11) :1949-1961
[6]  
CLEVELAND GA, 1989, PROCEEDINGS OF THE THIRD INTERNATIONAL CONFERENCE ON GENETIC ALGORITHMS, P160
[7]  
Davis L, 1987, GENETIC ALGORITHMS S
[8]   SIMULATED ANNEALING - A TOOL FOR OPERATIONAL-RESEARCH [J].
EGLESE, RW .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 46 (03) :271-281
[9]  
ESCUDERO LF, 1987, MODERN PRODUCTION MA, P231
[10]   THE LAGRANGIAN-RELAXATION METHOD FOR SOLVING INTEGER PROGRAMMING-PROBLEMS [J].
FISHER, ML .
MANAGEMENT SCIENCE, 1981, 27 (01) :1-18