THE SINGLE-MACHINE ABSOLUTE-DEVIATION EARLY-TARDY PROBLEM WITH RANDOMCOMPLETION TIMES

We consider sequencing n jobs on a single machine subject to job compl etion times arising from either machine breakdowns or other causes. Th e objective is to minimize an expected weighted combination of due dat es, completion times, earliness, and tardiness penalties. The determin ation of optimal distinct due dates or optimal common due dates for a given schedule is investigated. The scheduling problem for a fixed com mon due date is considered when random completion times arise from ma chine breakdowns. The optimality of a V-shaped about ( a point) T sequ ence is established when the number of machine breakdowns follows eith er a Poisson or a geometric distribution and the duration of a breakdo wn has an exponential distribution. (C) 1996 John Wiley & Sons, Inc.