Optimal Stochastic Allocation of Machines under Waiting-Time Constraints

The nonpreemptive scheduling of n 1 stochastic jobs is considered to minimize the expected number of parallel machines needed to meet given waiting-time constraints. The number of machines available is unlimited. The running times of the jobs are denoted T₁ , … ,Tₙ and are taken to be independent samples of an exponentially distributed random variable T with mean 1. Job waiting times are to be bounded stochastically by a nonnegative random variable W, independent of T₁ , … ,Tₙ. At time zero, a timer is started with an initial value W, and job scheduling begins. When the timer expires, all jobs still waiting for a machine are assigned to available machines. Only the distributions of W and the job durations T₁ , … ,Tₙ are known to the scheduler in advance. A scheduling policy is defined which is proven to be optimal when W has an exponential distribution, and is asymptotically optimal as n → ∞, when W is a constant (hard-deadline). In the exponential case, an explicit formula for the cost function is derived. The uniqueness question is also resolved. The paper concludes with a partial analysis of the general hard-deadline problem, which leads to a policy that we think is optimal. A proof of optimality, however, remains an open problem.