Lagrangian bounds for just-in-time job-shop scheduling

被引：42

作者：

Baptiste, Philippe ^{[1
]}

Flamini, Marta

Sourd, Francis

机构：

[1] Ecole Polytech, CNRS, LIX Lab, F-91128 Palaiseau, France

[2] Univ Roma 3, Dipartimento Informat & Automaz, Rome, Italy

[3] CNRS, LIP6 Lab, Paris, France

来源：

COMPUTERS & OPERATIONS RESEARCH | 2008年 / 35卷 / 03期

关键词：

job-shop scheduling; earliness-tardiness; Lagrangian relaxation;

D O I：

10.1016/j.cor.2006.05.009

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We study the job-shop scheduling problem with earliness and tardiness penalties. We describe two Lagrangian relaxations of the problem. The first one is based on the relaxation of precedence constraints while the second one is based on the relaxation of machine constraints. We introduce dedicated algorithms to solve the corresponding dual problems. The second one is solved by a simple dynamic programming algorithm while the first one requires the resolution of an NP-hard problem by branch and bound. In both cases, the relaxations allow us to derive lower bounds as well as heuristic solutions. We finally introduce a simple local search algorithm to improve the best solution found. Computational results are reported. (c) 2006 Elsevier Ltd. All rights reserved.

引用

页码：906 / 915

页数：10

共 14 条

[1]

[Anonymous], 2003, 5 INT WORKSH INT AI

[2] A hybrid approach to scheduling with earliness and tardiness costs [J].

Beck, JC ;

Refalo, P .

ANNALS OF OPERATIONS RESEARCH, 2003, 118 (1-4) :49-71

[3] An alternative framework to Lagrangian relaxation approach for job shop scheduling [J].

Chen, HX ;

Luh, PB .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 149 (03) :499-512

[4] An improvement of the Lagrangean relaxation approach for job shop scheduling: A dynamic programming method [J].

Chen, HX ;

Chu, CB ;

Proth, JM .

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1998, 14 (05) :786-795

[5] PERT scheduling with convex cost functions [J].

Chrétienne, P ;

Sourd, F .

THEORETICAL COMPUTER SCIENCE, 2003, 292 (01) :145-164

[6]

Danna E, 2003, LECT NOTES COMPUT SC, V2833, P817

[7]

DEMEULEMEESTER EL, 2002, PROFJECT SCHEDULING

[8] FORMULATING THE SINGLE-MACHINE SEQUENCING PROBLEM WITH RELEASE DATES AS A MIXED INTEGER-PROGRAM [J].

DYER, ME ;

WOLSEY, LA .

DISCRETE APPLIED MATHEMATICS, 1990, 26 (2-3) :255-270

[9] Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem [J].

Hendel, Y ;

Sourd, F .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 173 (01) :108-119

[10] An implementation of Shor's r-algorithm [J].

Kappel, F ;

Kuntsevich, AV .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2000, 15 (02) :193-205

← 1 2 →