The processor minimization problem with independent waiting-time constraints

AbstractThis paper studies a dual of classical stochastic scheduling of parallel processor systems. The given data are n jobs with running times T1,…, Tn and waiting-time constraints W1,…, Wn; these sequences are independent and each consists of i.i.d. random variables. Although the Ti and Wi are not known in advance, they are known to be samples from exponential distributions with given parameters. Scheduling policies are nonpreemptive and have the option, for each i, of making the ith job wait during [0, Wi). However, by the random deadline Wi, the ith job must be assigned to a processor, if it is still waiting. In this paper, we find a policy that minimizes the expected number of processors used, among all policies of the above type. We also estimate the expected number of processors used under this policy. There appears to be no simple, exact formula for this quantity, so we turn to an asymptotic analysis based on a continuous approximation