Optimal Scheduling of Jobs with Exponential Service Times on Identical Parallel Processors

The scheduling of jobs with stochastically independent, exponentially distributed service times on identical parallel processors is considered. General sufficient conditions for optimality in expectation of priority policies for certain cost functions are given, including cases of the weighted flow time. The priority policies under consideration may be more general than the longest expected processing time (LEPT) or the shortest expected processing time (SEPT) policy. We deal with a fixed number of processors as well as certain more general resource constraints. Finally, precedence relations between jobs given by strict interval orders are admitted and an optimality result for LEPT is stated for this situation.