Asymmetric Earliness and Tardiness Scheduling with Exponential Processing Times on an Unreliable Machine

Xiaoqiang Cai*, Xian Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

25 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)313-331
Number of pages19
JournalAnnals of Operations Research
Volume98
Issue number1-4
Publication statusPublished - 2000
Externally publishedYes

Keywords

  • Dynamic programming
  • Earliness-tardiness scheduling
  • Random due dates
  • Random processing times
  • Stochastic machine breakdowns

Fingerprint

Dive into the research topics of 'Asymmetric Earliness and Tardiness Scheduling with Exponential Processing Times on an Unreliable Machine'. Together they form a unique fingerprint.

Cite this