Please use this identifier to cite or link to this item:
Title: Asymmetric Earliness and Tardiness Scheduling with Exponential Processing Times on an Unreliable Machine
Authors: Cai, X
Zhou, X
Keywords: Dynamic programming
Earliness-tardiness scheduling
Random due dates
Random processing times
Stochastic machine breakdowns
Issue Date: 2000
Publisher: Springer
Source: Annals of operations research, 2000, v. 98, no. 1-4, p. 313-331 How to cite?
Journal: Annals of operations research 
Abstract: We address the problem of processing a set of jobs on a single machine under random due dates with a common distribution. The processing times of the jobs are exponentially distributed random variables with means μi, and the machine is subject to stochastic breakdowns governed by a Poisson process. Each job i is associated with a job-dependent weight wi. The objective is to schedule the jobs so as to minimize the expected sum of the weighted earliness and tardiness costs of all jobs, which are quadratic functions of the deviations of job completion times from the due dates. We show that the problem is NP-complete. Nevertheless, important optimality properties exist, which can be utilized to develop effective algorithms to solve the problem. Specifically, we prove that, in the case where the weights assigned to both the earliness and tardiness are symmetric, an optimal sequence for the problem must be V-shaped with respect to {μi/wi}, in the sense that the sequence will first process jobs in a nonincreasing order of {μi/wi} and then in a nondecreasing order of {μi/wi}. In the case where asymmetric weights are assigned to the earliness and tardiness costs, the optimal sequence must also be V-shaped with respect to {μi/wi}, if the due dates are exponentially distributed. Dynamic programming algorithms are proposed which can find the best V-shaped sequences.
ISSN: 0254-5330
EISSN: 1572-9338
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 Aug 14, 2018

Page view(s)

Last Week
Last month
Citations as of Aug 12, 2018

Google ScholarTM


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