Scheduling Jobs with Exponentially Distributed Processing Times on Two Machines with Resource Constraints
研究在两台并行机器上，最小化n个独立指数分布加工时间作业的期望完工时间，并受资源总量限制。当加工时间和资源需求均递增时，给出了最优抢占策略，并证明一个非抢占策略最优。
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/μ 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/μ 1 < ⋯ < 1/μ n and r 1 < ⋯ < 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.