STOCHASTIC SINGLE-MACHINE SCHEDULING WITH QUADRATIC EARLY-TARDY PENALTIES

We address the problem of scheduling n jobs on a single machine, which is subject to random breakdowns, to minimize an expected sum of nonre gular penalty functions. A simple recourse model is considered when th e penalty function is the squared deviation of job completion times fr om a common due date, and a deterministic equivalent objective functio n is developed. Characterizations of optimal schedules for this quadra tic objective function are established both when the common due date i s a decision variable and when it is given and fixed. Most importantly , the V-shaped nature of optimal schedules is investigated for a class of Poisson processes, {N(t), t > 0}, describing the number of breakdo wns in the interval (0, t). In addition, relationships to a class of b icriteria models are demonstrated.