Optimal due-date assignment for a single machine sequencing problem with random processing times

Abstract

Given a set of n jobs with independent random processing times and the same start times, the problem is to find the optimal processing time multiple k* for the total work content due-date assignment method, and the optimal sequence π* to minimize the expected total amount of missed due-dates. It is shown that k* is a constant for a given job set. Although in general π* cannot be determined analytically, it is shown that, under certain circumstances, π* should be in shortest-expected-processing-time sequence to minimize the objective function.