Scheduling Jobs with Exponentially Distributed Processing Times on Two Machines with Resource Constraints

We consider the problem of minimizing the expected makespan of n jobs with independent exponentially distributed processing times on two parallel machines, under resource constraints. Job j has expected processing time 1/\mu _j and requires throughout its processing an amount r_j of a resource; the total amount of resource available is r. In the case where 1/\mu ₁ < \cdots < 1/\mu _n and r₁ < \cdots < r_n, we characterize all the optimal policies in the class of preemptive schedules, and show that the following nonpreemptive policy is optimal: Find the largest k for which r_k + r_k-1 < r, and start processing jobs k - 1, k. Thereafter, at any job completion, start processing on the machine that is freed, the longest job compatible with the job running on the other machine.