PARALLEL-MACHINE SCHEDULING PROBLEMS WITH EARLINESS AND TARDINESS PENALTIES

被引：5

作者：

CHENG, TCE ^{[1
]}

CHEN, ZL ^{[1
]}

机构：

[1] SHANGHAI TRANSPORTAT PLANNING INST,SHANGHAI,PEOPLES R CHINA

来源：

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 1994年 / 45卷 / 06期

关键词：

SCHEDULING; SEQUENCING; PARALLEL-MACHINE; NP-COMPLETENESS;

D O I：

10.1038/sj/jors/0450608

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. We show that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, we show that the special case in which all jobs have an equal processing time is polynomially-solvable.

引用

页码：685 / 695

页数：11

共 9 条

[1] A STATE-OF-THE-ART REVIEW OF PARALLEL-MACHINE SCHEDULING RESEARCH
CHENG, TCE
SIN, CCS
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 47 (03) : 271 - 292
[2] MINIMIZING THE MAXIMUM DEVIATION OF JOB COMPLETION-TIME ABOUT A COMMON DUE-DATE
CHENG, TCE
[J]. COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1987, 14 (04) : 279 - 283
[3] A HEURISTIC FOR COMMON DUE-DATE ASSIGNMENT AND JOB SCHEDULING ON PARALLEL MACHINES
CHENG, TCE
[J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1989, 40 (12) : 1129 - 1135
[4] CHENG TCE, 1992, ASIA PAC J OPER RES, V9, P235
[5] ON THE MULTIPLE-MACHINE EXTENSION TO A COMMON DUE-DATE ASSIGNMENT AND SCHEDULING PROBLEM
DE, P
GHOSH, JB
WELLS, CE
[J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1991, 42 (05) : 419 - 422
[6] DIAMOND JE, 1991, UNPUB APPROXIMATE SO
[7] French S., 1982, SEQUENCING SCHEDULIN
[8] COMMON DUE DATE ASSIGNMENT TO MINIMIZE TOTAL PENALTY FOR THE ONE MACHINE SCHEDULING PROBLEM
PANWALKAR, SS
SMITH, ML
SEIDMANN, A
[J]. OPERATIONS RESEARCH, 1982, 30 (02) : 391 - 399
[9] MINIMIZING THE SUM OF ABSOLUTE LATENESS IN SINGLE-MACHINE AND MULTIMACHINE SCHEDULING
SUNDARARAGHAVAN, PS
AHMED, MU
[J]. NAVAL RESEARCH LOGISTICS, 1984, 31 (02) : 325 - 333

← 1 →