Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs

This paper studies the problem of simultaneous due-date determination and sequencing of a set of n jobs on a single machine where processing times are random variables and job earliness and tardiness costs are distinct. The objective is to determine the optimal sequence and the optimal due-dates which jointly minimize the expected total earliness and tardiness cost. We present an analytical approach to determine optimal due-dates, and propose two efficient heuristics of order O(n log n) to find candidates for the optimal sequence. It is demonstrated that variations in processing times increase cost and affect sequencing and due-date determination decisions. Our illustrative examples as well as computational results show that the proposed model produces optimal sequences and optimal due-dates that are significantly different from those provided by the classical deterministic single machine models. Furthermore, our computational experiments reveal that the proposed heuristics perform well in providing either optimal sequences or good candidates with low overcosts. (C) 1999 Elsevier Science B.V. All rights reserved.