Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/14495
Title: Common due date assignment and scheduling with ready times
Authors: Cheng, TCE 
Chen, ZL
Shakhlevich, NV
Keywords: Due date assignment
Earliness
Single-machine scheduling
Tardiness
Issue Date: 2002
Publisher: Pergamon Press
Source: Computers and operations research, 2002, v. 29, no. 14, p. 1957-1967 How to cite?
Journal: Computers and operations research 
Abstract: We consider the problem of scheduling a set of nonsimultaneously available jobs on one machine. Each job has a ready time only at or after which the job can be processed. All the jobs have a common due date, which needs to be determined. The problem is to determine a due date and a schedule so as to minimize a total penalty depending on the earliness, tardiness and due date. We show that this problem is strongly NP-hard and give an efficient algorithm that finds an optimal due date and schedule when either the job sequence is predetermined or all jobs have the same processing time. We also propose three approximation algorithms for the general and special cases together with their experimental analysis. We consider the single machine due date assignment problem for scheduling jobs which are ready for processing at different times. The problem under consideration arises in production planning and scheduling concerning the setting of appropriate due dates for a number of customer orders arriving over time. Most of the earlier publications on this subject assumed that the jobs are ready for processing simultaneously. This assumption is too restrictive for real-life production systems where jobs arrive at different times. We show that the problem with unequal ready times is NP-hard and develop fast heuristic algorithms for it, and exact algorithms for two special cases.
URI: http://hdl.handle.net/10397/14495
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/S0305-0548(01)00067-3
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

21
Last Week
0
Last month
0
Citations as of Sep 15, 2017

WEB OF SCIENCETM
Citations

18
Last Week
0
Last month
0
Citations as of Sep 7, 2017

Page view(s)

50
Last Week
5
Last month
Checked on Sep 18, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.