Stochastic scheduling on parallel machines subject to random breakdowns tominimize expected costs for earliness and tardy jobs

This paper addresses a stochastic scheduling problem in which a set of inde pendent 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 stocha stic breakdowns, which are characterized by a Poisson process. The deadline is an exponentially distributed random variable. The objective is to minim ize the expected costs for earliness and tardiness, where the cost for an e arly 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 i s only a single machine or are multiple machines, the decision-maker can ta ke 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 prob lem can be constructed analytically.