This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Cai, X. Articles by Zhou, S. Search for Related Content

Stochastic Scheduling on Parallel Machines Subject to Random Breakdowns to Minimize Expected Costs for Earliness and Tardy Jobs

The Chinese University of Hong Kong, Shatin, Hong Kong
The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

This paper addresses a stochastic scheduling problem in which a set of independent jobs are to be processed by a number of identical parallel machines under a common deadline. Each job has a processing time, which is a random variable with an arbitrary distribution. Each machine is subject to stochastic breakdowns, which are characterized by a Poisson process. The deadline is an exponentially distributed random variable. The objective is to minimize the expected costs for earliness and tardiness, where the cost for an early job is a general function of its earliness while the cost for a tardy job is a fixed charge. Optimal policies are derived for cases where there is only a single machine or are multiple machines, the decision-maker can take a static policy or a dynamic policy, and job preemptions are allowed or forbidden. In contrast to their deterministic counterparts, which have been known to be NP-hard and are thus intractable from a computational point of view, we find that optimal solutions for many cases of the stochastic problem can be constructed analytically.

Subject classifications: production/scheduling; sequencing; earliness/tardiness; multiple machines; production/scheduling, stochastic; random processing times; machine breakdowns; deadline.

This article has been cited by other articles:

				X. Cai, X. Wu, and X. Zhou Stochastic Scheduling Subject to Preemptive-Repeat Breakdowns with Incomplete Information Operations Research, September 1, 2009; 57(5): 1236 - 1249. [Abstract] [PDF]