Please use this identifier to cite or link to this item:
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.
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/S0305-0548(02)00066-7
Appears in Collections:Journal/Magazine Article

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


Last Week
Last month
Citations as of Apr 11, 2018


Last Week
Last month
Citations as of Apr 18, 2018

Page view(s)

Last Week
Last month
Citations as of Apr 23, 2018

Google ScholarTM



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