N-Job, One Machine Sequencing Problems Under Uncertainty

N jobs simultaneously arrive at a machine where they are to be processed. It is assumed that the processing times and due dates for the jobs are independent random variables whose distributions are known. The problem is to determine the optimal sequences of jobs, before processing begins, for various criteria of tardiness. It is shown that solutions are obtainable by ascertaining the optimal paths through a particular deterministic network. Furthermore, one may utilize a branch and bound technique to find these paths. For special classes of distributions, the solution procedure degenerates, whereby the optimal sequences may be determined by inspection.