Parallel-Machine Scheduling Problems with Earliness and Tardiness Penalties
作者:
ChengT. C. E.,
L.Z.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1994)
卷期:
Volume 45,
issue 6
页码: 685-695
ISSN:0160-5682
年代: 1994
DOI:10.1057/jors.1994.106
出版商: Taylor&Francis
关键词: scheduling;sequencing;parallel-machine;NP-completeness
数据来源: Taylor
摘要:
AbstractWe 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.
点击下载:
PDF (3928KB)
返 回