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

Abstract

It is shown that Lawler's efficient (order n 2 ) 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.