Stochastic scheduling with asymmetric earliness and tardiness penalties under random machine breakdowns

Xiaoqiang Cai*, Xian Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

We study a stochastic scheduling problem of processing a set of jobs on a single machine. Each job has a random processing time Pi and a random due date Di, which are independently and exponentially distributed. The machine is subject to stochastic breakdowns in either preempt-resume or preempt-repeat patterns, with the uptimes following an exponential distribution and the downtimes (repair times) following a general distribution. The problem is to determine an optimal sequence for the machine to process all jobs so as to minimize the expected total cost comprising asymmetric earliness and tardiness penalties, in the form of E[Σαi max {0, Di - Ci} + βi {0, Ci - Di}]. We find sufficient conditions for the optimal sequences to be V-shaped with respect to {E(Pi)/αi} and {E(Pi)/βi} , respectively, which cover previous results in the literature as special cases. We also find conditions under which optimal sequences can be derived analytically. An algorithm is provided that can compute the best V-shaped sequence.

Original languageEnglish
Pages (from-to)635-654
Number of pages20
JournalProbability in the Engineering and Informational Sciences
Volume20
Issue number4
Publication statusPublished - 2006
Externally publishedYes

Fingerprint

Dive into the research topics of 'Stochastic scheduling with asymmetric earliness and tardiness penalties under random machine breakdowns'. Together they form a unique fingerprint.

Cite this