SPT sequencing with dependent processing times

This paper investigates the applicability of SPT-based strategies to situations where the processing time for a particular task is not known until some other task has been completed. For comparison a random strategy is used. Two cases are considered: the static case which assumes that all jobs to be processed are present in the shop, and the dynamic case in which jobs arrive randomly over time. The improvement in flow time resulting from the SPT-based strategy is quantified analytically for the static case. For the dynamic case some simulation results are presented. Both sets of results indicate that SPT is a very robust strategy which results in significant reductions in a wide variety of situations.