INEQUALITIES AND BOUNDS IN STOCHASTIC SHOP SCHEDULING*

Abstract. In this paper, stochastic shop models with m machines and n jobs are considered. A job has to be processed on all m machines, while certain constraints are imposed on the order of processing. The effect of the variability of the processing times on the expected completion time of the last job (the makespan) and on the sum of the expected completion times of all jobs (the flow time) is studied. Bounds are obtained for the expected makespan when the processing time distributions are New Better (Worse) than Used in Expectation