SCHEDULING STOCHASTIC JOIlS ON PARALLEL MACHINES TO HINHIIZE HAKESPi\N OR FLOWTIME

A number of identical machines operating in parallel are to be used to complete the processing of a collection of jobs so as to minimize the jobs ' makespan or flowtime. 111e amount of processing required to complete the jobs have known probability distributions. It has been established by several researchers that when the required amounts of processing are all distributed as exponential random variables, then tile strategy (LEPT) of always processing jobs with the longest expected1. \ strategy (SEPT) of always processing jobs with the shortest expected processing times minimizes the expected value of the flowtime. We prove f l processing times minimizes the expected value of the makespan, and th