Scheduling Jobs with Exponential Processing and Arrival Times on Identical Processors so as to Minimize the Expected Makespan

In this note we study a problem related to the scheduling of jobs on p identical processors (p ≥ 2). Jobs arrive randomly, interarrival times being exponentially distributed. The processing times are also exponential with mean drawn upon arrival from an arbitrary distribution function. Preemptions are allowed. The objective is to minimize the expected time until this M/G/p queuing system is first empty. We prove that an optimal policy processes jobs currently in the system in decreasing order of expected processing time.