Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/21058
Title: Single machine scheduling with a variable common due date and resource-dependent processing times
Authors: Ng, DCT 
Cheng, TCE 
Kovalyov, MY
Lam, SS
Keywords: Common due date assignment
Controllable processing times
Single machine scheduling
Issue Date: 2003
Publisher: Pergamon Press
Source: Computers and operations research, 2003, v. 30, no. 8, p. 1173-1185 How to cite?
Journal: Computers and operations research 
Abstract: The problem of scheduling n jobs with a variable common due date on a single machine is studied. It is assumed that the job processing times are non-increasing linear functions of an equal amount of a resource allocated to the jobs. The due date and resource values can be continuous or discrete. The objective is to minimize a linear combination of scheduling, due date assignment and resource consumption costs. The resource consumption cost function may be non-monotonous. Algorithms with O(n2 log n) running times are presented for scheduling costs involving earliness/tardiness and number of tardy jobs. Computational experiments show that the algorithms can solve problems with n = 5,000 in less than a minute on a standard PC. We study a problem that combines scheduling, common due date assignment and resource allocation decisions. Due date scheduling is an important area of scheduling research because it focuses on customer satisfaction. Variable common due date applies to situations where several items constitute a single customer's order and the due date for the order can be negotiated. Resource-dependent processing times appear whenever resources can be employed to adjust processing requirements. Polynomial time algorithms are presented for minimizing a linear combination of scheduling, due date assignment and resource consumption costs. Computational experiments demonstrate their efficiency in solving large-scale problem instances.
URI: http://hdl.handle.net/10397/21058
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/S0305-0548(02)00066-7
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

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

WEB OF SCIENCETM
Citations

51
Last Week
0
Last month
0
Citations as of Sep 14, 2017

Page view(s)

51
Last Week
3
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.