Single Machine Scheduling Subject to Random Breakdowns.

The problem of scheduling jobs on unreliable machines has received little attention in the literature, even though it has significant practical applications. Practitioners often completely ignore possible machine failures when developing their original schedule and , hence, need to reschedule in real-time after each disruption. This work presents an alternate approach to scheduling jobs on a single machine subject to random breakdowns to minimize an expected sum of nondecreasing functions of job completion times and due dates. This alternative is to create an initial schedule which is sensitive to the possible breakdown realizations and does not require real-time rescheduling. The major results are: (1) Under special conditions, simple job orderings are optimal. These conditions are usually restrictions on the job data or on the uptimes' probability distributions. (2) When such conditions no longer hold, elimination criteria which define characteristics of an optimal schedule are developed. Elimination criteria are useful in enumeration or combinatorial solution procedures since they decrease the number of feasible schedules and , hence, increase solution procedure efficiency. (3) In general, the objective depends on a possibly infinite number of breakdowns and , so, is difficult to calculate exactly. Therefore, bounds on the accuracy of finite breakdown approximation methods are developed based on estimates of the error induced by the ignored trailing sequence of breakdowns. (4) A computational study demonstrates when a practitioner's deterministic approximation of the stochastic machine problem to minimize expected total weighted tardiness may be effective and when it is better to use a finite breakdown approximation.Ph.D.Industrial engineeringUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/161289/1/8702794.pd