The single machine absolute deviation early-tardy problem with random completion times

In this thesis a single machine scheduling problem is considered, where job completion times are delayed due to some stochastic behavior in the system. Such delays may result from stochastic processing times or random machine breakdowns. The objective is to minimize the expected weighted combination of earliness, tardiness, completion times, and due dates. Earliness and tardiness are measured as the absolute deviation from a due date. Scheduling problems involving earliness and tardiness are, in general, known to be NP-complete.;An optimal schedule for such problems is usually characterized by the V-shape property. In this thesis, a more informative characterization of optimal schedules called the V-shape about T, is introduced. The V-shape about T characterization defines a subset of V-shaped schedules centered about a specified point of time, T. This new characterization is used to characterize an optimal schedule for the problem considered in this thesis.;The problem of assigning due dates for jobs in a given schedule is considered for both distinct due date assignment and common due date assignment policies. Optimal due dates are found in terms of distribution functions of job completion times. Conditions under which optimal due dates are independent of the distribution function are identified.;The scheduling aspect of the problem is considered under common due date assignment policy. Two types of scheduling problems are considered: constrained and unconstrained. The common due date is given in the constrained problem and is a decision variable in the unconstrained problem. Some characteristics of an optimal schedule for both problems are identified when delays are caused by machine breakdowns.;The V-shaped about T characterization of optimal schedules is established for the constrained case for two models of machine breakdowns. In both models, breakdown durations are independent, identical, and exponentially distributed random variables. In the first model, the number of breakdowns occurring in a time interval is a Geometrically distributed random variable. In the second model, the number of breakdowns is a homogeneous Poisson counting process. The point T for both models is identified to be the solution of a certain inequality.