Minimizing maximum absolute lateness and range of lateness under generalizeddue dates on a single machine

被引：0

作者：

K. Tanaka

M. Vlach

机构：

来源：

Annals of Operations Research | 1999年 / 86卷

关键词：

Single Machine; Small Integer; Absolute Lateness;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We investigate the problems of minimizing the maximum absolute lateness and range oflateness under generalized due dates on a single machine. In contrast to the traditional duedate cases, we show that these problems are unary NP‐hard. Furthermore, we present simpleapproximation algorithms for these problems, and show that they achieve the performanceratios of n for the problem of minimizing the maximum absolute lateness and of [ n/2 ] forthe problem of minimizing the range of lateness, where [ x ] is the smallest integer no lessthan x.

引用

页码：507 / 526

页数：19

共 23 条

[1]

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

[2]

Leung J.Y.-T.(1988)One-processor scheduling with symmetric earliness and tardiness penalties Mathematics of Operations Research 13 330-348

[3]

Garey M.R.(1986)Scheduling problems with generalized due dates IIE Transactions 18 220-222

[4]

Tarjan R.E.(1991)On the complexity of generalized due date scheduling problems European Journal of Operational Research 51 100-109

[5]

Wilfong G.T.(1973)Optimal sequencing of a single machine subject to precedence constraints Management Science 19 544-546

[6]

Hall N.G.(1978)Complexity of scheduling under precedence constraints Operations Research 26 22-35

[7]

Hall N.G.(1980)Complexity results for scheduling chains on a single machine European Journal of Operational Research 4 270-275

[8]

Sethi S.P.(1977)Complexity of machine scheduling problems Annals of Discrete Mathematics 1 343-362

[9]

Sriskandarajah C.(1991)An algorithm for minimizing the range of lateness on a single machine Journal of the Operational Research Society 42 183-186

[10]

Lawler E.L.(1968)An Management Science 15 102-109

← 1 2 3 →