One machine scheduling to minimize expected mean tardiness-Part II

A heuristic algorithm is developed for the problem of scheduling a number of simultaneously available jobs with exponentially distributed processing times (with known means), on a single machine, to minimize the mean or total expected tardiness. The performance of the heuristic is evaluated by comparing the results with the optimal values or values of a proposed lower bound. The values of expected total tardiness of the sequences generated by the deterministic and stochastic versions, of the Shortest Processing times sequence and the Earliest Due Date Sequence are compared. Finally, the paper includes a discussion on the limitations of the proposed model and the issue of risk due to uncertainty in processing times.