THE STOCHASTIC SINGLE-MACHINE SCHEDULING PROBLEM WITH EARLINESS AND TARDINESS COSTS

This paper studies the static single machine scheduling problem with e arliness and tardiness costs where job processing times are random var iables and due dates are distinct and deterministic. The objective is to identify an optimal sequence which minimizes the total expected ear liness plus tardiness cost. A case where processing times are normally distributed is fully explored. We demonstrate that variations in proc essing times increase cost and affect sequencing decisions. Three heur istics for finding an optimal sequence are proposed. The illustrative example and computational results indicate that optimal sequences and their expected costs are significantly different from those provided b y the classical deterministic single machine models. Furthermore, our computational experiments show that two of the proposed heuristics per form well in identifying optimal sequences.