Tabu search algorithms for cyclic machine scheduling problems

被引：27

作者：

Brucker, P ^{[1
]}

Kampmeyer, T ^{[1
]}

机构：

[1] Univ Osnabruck, Fachbereich Math Informat, D-49069 Osnabruck, Germany

来源：

JOURNAL OF SCHEDULING | 2005年 / 8卷 / 04期

关键词：

cyclic scheduling; job-shop problem; tabu-search; block approach; opt-connectivity;

D O I：

10.1007/s10951-005-1639-4

中图分类号：

T [工业技术];

学科分类号：

08 [工学];

摘要：

Tabu search algorithms are developed for solving a large class of cyclic machine scheduling problems with the objective to minimize the cycle time. Neighborhoods are derived which generalize the block-approach based neighborhoods which have been successfully applied to noncyclic job-shop problems. For a variant of this neighborhood opt-connectivity is proved. The tabu-search procedure is applied to cyclic job-shop scheduling problems. Computational results are presented.

引用

页码：303 / 322

页数：20

共 16 条

[1]

Software pipelining [J].

Allan, VH ;

Jones, RB ;

Lee, RM ;

Allan, SJ .

ACM COMPUTING SURVEYS, 1995, 27 (03) :367-432

[2]

BEASLEY JE, BENCHMARK PROBLEMS

[3]

Brucker Peter, 2004, Scheduling Algorithms

[4]

Carlier J., 1988, PROBLEMES ORDONNANCE

[5]

A LINEAR-SYSTEM-THEORETIC VIEW OF DISCRETE-EVENT PROCESSES AND ITS USE FOR PERFORMANCE EVALUATION IN MANUFACTURING [J].

COHEN, G ;

DUBOIS, D ;

QUADRAT, JP ;

VIOT, M .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1985, 30 (03) :210-220

[6]

Dasdan A., 1999, Proceedings 1999 Design Automation Conference (Cat. No. 99CH36361), P37, DOI 10.1109/DAC.1999.781227

[7]

Glover F., 1990, ORSA Journal on Computing, V2, P4, DOI [10.1287/ijoc.1.3.190, 10.1287/ijoc.2.1.4]

[8]

The complexity of cyclic shop scheduling problems [J].

Hall, NG ;

Lee, TE ;

Posner, ME .

JOURNAL OF SCHEDULING, 2002, 5 (04) :307-327

[9]

STUDY OF A NP-HARD CYCLIC SCHEDULING PROBLEM - THE RECURRENT JOB-SHOP [J].

HANEN, C .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 72 (01) :82-101

[10]

A STUDY OF THE CYCLIC SCHEDULING PROBLEM ON PARALLEL PROCESSORS [J].

HANEN, C ;

MUNIER, A .

DISCRETE APPLIED MATHEMATICS, 1995, 57 (2-3) :167-192

← 1 2 →