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

✍ Scribed by Soroush H.M.

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 215 KB
• Volume: 113
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(98)00003-4

✦ Synopsis

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 ecient heuristics of order O(n log n) to ®nd candidates for the optimal sequence. It is demonstrated that variations in processing times increase cost and aect 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 signi®cantly dierent 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.