Note—A Note on Single Machine Sequencing with Random Processing Times

It is shown that Lawler's efficient (order n²) algorithm for the n-job, one-machine scheduling problem (where the objective is to minimize the maximum deferral cost subject to arbitrary precedence relationships) also applies when the processing times are random variables and the objective is to minimize the maximum expected deferral cost. Several special cases are explored.