A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
研究了两个处理器上独立任务按最大优先规则调度时的期望完工时间，给出了LF和RLF规则的期望完工时间上界与精确值，并推导了与最优规则的性能比界限。
We consider the scheduling of sets of n simultaneously available tasks on two identical processors. The task execution times are assumed to be independent samples from the uniform distribution on [0, 1]. We analyze the expected makespan (schedule-length) performance of two well-known largest-task-first, nonpreemptive approximation rules. With the largest-first (LF) rule, tasks are assigned in nonincreasing order of execution time to the processors as they become available. With the restricted largest first (RLF) rule, tasks are assigned in pairs, one to a processor. The larger task of a pair is the first to be scheduled. (If n is odd, the last task is simply assigned to the earner finishing processor in the schedule for the first n − 1 tasks.) We prove that the expected makespan for LF is bounded by [Formula: see text] and for RLF it is precisely [Formula: see text] From these results simple bounds are derived on the ratio of the expected performance of LF and RLF to the expected performance of an optimization rule. Finally, a lower bound on expected LF makespans is shown to be [Formula: see text]