Tardiness minimization in a flexible job shop: A tabu search approach

被引:64
作者
Scrich, CR
Armentano, VA
Laguna, M
机构
[1] Univ Estadual Campinas, Fac Engn Eletr & Computacao, BR-13083970 Campinas, SP, Brazil
[2] Inst Nacl Pesquisas Espaciais, Lab Associado Computacao & Matemat Aplicada, BR-12201970 Sao Jose Dos Campos, SP, Brazil
[3] Univ Colorado, Leeds Sch Business, UCB 419, Boulder, CO 80309 USA
基金
巴西圣保罗研究基金会;
关键词
scheduling; flexible job shop; due dates; heuristic; tabu search;
D O I
10.1023/B:JIMS.0000010078.30713.e9
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper addresses the problem of scheduling jobs in a flexible job shop with the objective of minimizing total tardiness. The flexible job shop differs from the classical job shop in that each of the operations associated with a job can be processed on any of a set of alternative machines. Two heuristics based on tabu search are developed for this problem: a hierarchical procedure and a multiple start procedure. The procedures use dispatching rules to obtain an initial solution and then search for improved solutions in neighborhoods generated by the critical paths of the jobs in a disjunctive graph representation. Diversification strategies are also implemented and tested. The outcomes of extensive computational results are reported.
引用
收藏
页码:103 / 115
页数:13
相关论文
共 32 条
[1]  
Aarts E. H., 1994, ORSA Journal on Computing, V6, P118, DOI 10.1287/ijoc.6.2.118
[2]   THE SHIFTING BOTTLENECK PROCEDURE FOR JOB SHOP SCHEDULING [J].
ADAMS, J ;
BALAS, E ;
ZAWACK, D .
MANAGEMENT SCIENCE, 1988, 34 (03) :391-401
[3]   2 NEW RULES TO MINIMIZE TARDINESS IN A JOB SHOP [J].
ANDERSON, EJ ;
NYIRENDA, JC .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1990, 28 (12) :2277-2292
[4]  
[Anonymous], 1997, Tabu Search
[5]   Tabu search for minimizing total tardiness in a job shop [J].
Armentano, VA ;
Scrich, CR .
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2000, 63 (02) :131-140
[6]   SEQUENCING RULES AND DUE-DATE ASSIGNMENTS IN A JOB SHOP [J].
BAKER, KR .
MANAGEMENT SCIENCE, 1984, 30 (09) :1093-1104
[8]   SOLVING THE JOB-SHOP SCHEDULING PROBLEM WITH TABU SEARCH [J].
BARNES, JW ;
CHAMBERS, JB .
IIE TRANSACTIONS, 1995, 27 (02) :257-263
[9]  
Brandimarte P., 1993, Annals of Operations Research, V41, P157, DOI 10.1007/BF02023073
[10]  
Chakrapani J., 1993, Annals of Operations Research, V41, P327, DOI 10.1007/BF02022999