A heuristic for the stochastic single-machine problem with E/T costs

This paper addresses the problem of simultaneous due-date determination and sequencing of a set of jobs on a stochastic single machine environment with distinct job earliness and tardiness penalty costs. It was assumed that the jobs processing times are statistically independent and follow a normal distribution whose mean and variance are given and not necessarily integer values. The objective is to determine the optimal sequence and the optimal deterministic integer due dates which jointly minimize the expected total earliness and tardiness cost. Previous theoretical results regarding normally distributed processing times and expected values of earliness and tardiness costs are reviewed. It is proposed an efficient insertion-based construction heuristic to find candidates for the optimal sequence with polynomial time complexity. It was shown that the heuristic solution method includes safety time and the sequence obtained remains the same regardless of disruptions, meaning that the result is robust. Illustrative examples and computational experiments reveal that the proposed heuristic procedure performs well and is nearly always optimal. The heuristic was applied for 680 different problems with sizes between 5 and 12 jobs, resulting in an optimality percentage of 99.85%. When applied to a sample of 480 problems with sizes between 13 and 1000 jobs, it yielded at least the same results found in the literature, providing solutions with better costs in more than 80% of cases. Furthermore, it was proved that the heuristic is asymptotically optimal, so it can be recommended for problems of any siz