A Heuristic for Common Due-date Assignment and Job Scheduling on Parallel Machines
作者:
ChengT. C. E.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1989)
卷期:
Volume 40,
issue 12
页码: 1129-1135
ISSN:0160-5682
年代: 1989
DOI:10.1057/jors.1989.194
出版商: Taylor&Francis
关键词: due-date assignment;scheduling;sequencing
数据来源: Taylor
摘要:
AbstractIn this paper we consider the problem of scheduling a set of simultaneously available jobs on several parallel and identical machines. The problem is to find the optimal due-date, assuming this to be the same for all jobs. We also seek to sequence the jobs such that some are early and some are late so as to minimize a penalty function. For the single-machine problem, we present a simple proof of the well-known optimality result that the optimal due-date coincides with one of the job completion times. We show that the optimal job sequence for the single-machine problem can be easily determined. We prove that the same optimal due-date result can be generalized to the parallel-machine problem. However, determination of the optimal job sequence for such a problem is much more complex, and we present a simple heuristic to find an approximate solution. On the basis of a limited experiment, we observe that the heuristic is very effective in obtaining near-optimal solutions.
点击下载:
PDF (3288KB)
返 回