AN EFFICIENT ALGORITHM FOR THE SINGLE-MACHINE TARDINESS PROBLEM

被引：20

作者：

KONDAKCI, S

KIRCA, O

AZIZOGLU, M

机构：

[1] Industrial Engineering Department, Middle East Technical University, Ankara

来源：

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS | 1994年 / 36卷 / 02期

关键词：

SCHEDULING; SINGLE MACHINE; TOTAL TARDINESS;

D O I：

10.1016/0925-5273(94)90026-4

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

This study considers the problem of minimizing total tardiness on a single machine. A simple and efficient lower bound and several upper bounds are developed. A branch and bound procedure incorporating the bounds, precedence relations and dominance properties is proposed. An experiment is designed to test the efficiency of the bounds, precedence relations and the branch and bound procedure. Computational experience with problems up to 35 jobs is reported.

引用

页码：213 / 219

页数：7

共 14 条

[1]

Du, Leung, Minimizing tardiness on one machine is NP-hard, Mathematics of Operations Research, 15, pp. 483-495, (1990)

[2]

Held, Karp, A dynamic programming approach to sequencing problems, Journal of the Society for Industrial and Applied Mathematics, 10, pp. 196-210, (1962)

[3]

Schrage, Baker, Dynamic programming solution of sequencing problems with precedence constraints, Oper. Res., 26, pp. 444-449, (1978)

[4]

Elmaghraby, The one machine sequencing problem with delay costs, J. Ind. Eng., 19, pp. 105-108, (1968)

[5]

Shwimer, On the n-job one m/c sequence independent sequencing problem with tardiness penalties A branch and bound solution, Management Science, 18, pp. B301-B313, (1972)

[6]

Rinnooy Kan, Lagewag, Lenstra, Minimizing total costs in one-machine scheduling, Oper. Res., 23, pp. 908-927, (1975)

[7]

Fisher, A dual algorithm for the one-machine scheduling problem, Math. Programming, 11, pp. 229-251, (1976)

[8]

Picard, Queyranne, The time dependent travelling salesman problem and its application to the tardiness problem in one M/C scheduling, Oper. Res., 26, pp. 86-110, (1978)

[9]

Potts, van, A branch and bound algorithm for the total weighted tardiness problem, Oper. Res., 33, pp. 363-377, (1985)

[10]

Tapan, Borah, On the single-machine scheduling problem with tardiness penalties, Journal of the Operational Research Society, 42, pp. 695-702, (1991)

← 1 2 →