Maarten Otten, UT-EWI-SOR
The stochastic Earliness/Tardiness scheduling problem aims to minimize the total expected deviation of the completion times from selectable due dates. We show that the Earliness/Tardiness costs are linear as a function of the standard deviation of the completion time, whenever the optimal due date is selected, for several common probability distributions. We use this result to generate an optimal schedule for the multiple machine variant and then generalize this result to the case in which each job has distinct cost parameters. This optimal schedule is not unique and therefore allows us to consider several optimization objectives in addition to the Earliness/Tardiness objective.