并行机调度

并行机调度（parallel-machine scheduling）把若干作业分配给多台同时工作的机器，并决定各机加工顺序。最基本的同型机器模型中，一件作业放在哪台机器上都需相同工时，作业从零时可用且不可拆分或中断，目标为最后完成时刻最小。速度不同的机器、与作业有关的加工时间或有释放时刻的模型，需要另外说明。

两台同型机器要加工四件工时为四、三、三、二小时的作业。总工时十二，平均到每台至少六小时；把四和二放第一台、两个三放第二台，恰好都为六，所以总工期六是最优。

负载下界与任务不可拆分

记 $m\ge 1$ 为机器数、工时 $p_i\ge 0$。令 $S_j$ 为分给机器 $j$ 的作业集合，同型、无先后关系时可连续加工，总工期就是 $$C_{max}=\underset{1\le j\le m}{max}\sum _{i\in S_j}{p}_i.$$ 集合 $S_1,\dots ,S_m$ 须构成作业全集的划分。任何方案都满足 $$C_{\ast }\ge max\{\underset{i}{max}{p}_i,\frac{\sum _i{p}_i}{m}\}.$$ 第一项来自一件作业不能被两台同时分担，第二项来自全体机器总加工能力。这两项即使都满足，也不总能构造恰好达到的整数分配，例如两机三件工时二的任务，平均下界三，却至少有一机要处理两件而需四。

列表调度与性能证明

按某个顺序依次处理作业，总把下一件放到当前累计负载最小的机器。机器负载表示它最早再次空闲的时刻，因此每次得到合法不重叠安排；它是快速启发式，不是一般精确算法。若先按工时递减排序，则称LPT。

设最终完成最晚的作业为 $k$，其开始时刻为 $s$，总工作量为 $P$。它被安排时，所选机器负载最小，且此前已安排工作量不超过 $P-p_k$，故 $$\begin{array}{cc}s& \le (P-p_k)/m,\\ C_{max}=s+p_k& \le P/m+(1-1/m)p_k\\ & \le (2-1/m)C_{\ast }.\end{array}$$ 最后一步分别使用平均负载下界与最大单件下界。这一完整保证适用于任意列表次序，也适用于LPT；LPT还有更紧的专门界，本篇不以此粗界冒充其最佳理论结果。

图给出一个LPT非最优实例。总工时12使最优工期至少6，下方方案达到6；上方7不能仅因列表规则稳定就称为最优。

反例为两机五件 $3,3,2,2,2$。LPT先让两机各三小时，再各加二，最后一个二只能使一机变七，总负载为七、五。改成三加三与二加二加二即六、六，达到平均下界。

最小堆实现

堆顶保存最小负载机器；并列按机器编号稳定处理。输出工期、每件作业的机器及开始结束时刻；这段函数只实现给定列表，是否LPT由调用者先排序决定。

Python 3

import heapq
import math

def list_schedule(processing, machines):
    p = tuple(processing)
    if type(machines) is not int or machines < 1:
        raise ValueError("positive integer machine count required")
    if any(not math.isfinite(v) or v < 0 for v in p):
        raise ValueError("finite nonnegative processing times required")
    heap = [(0,j) for j in range(machines)]
    heapq.heapify(heap)
    result = []
    for i,v in enumerate(p):
        start,j = heapq.heappop(heap)
        result.append((i,j,start,start+v))
        heapq.heappush(heap,(start+v,j))
    return max((t for t,j in heap),default=0), result

print(list_schedule([4,3,3,2],2)[0])
print(list_schedule([3,3,2,2,2],2)[0])
# 6
# 7

每次取最小负载保持列表规则，回插新完成时刻保持机器的下一次可用时间；有限列表处理完即停止。建堆时间为 $O(m)$，分配时间为 $O(n\log (m+1))$，空间为 $O(m+n)$；若要先执行LPT，排序另需 $O(n\log n)$。

变式。 只有一台机器时，工期必为工时总和十二，与次序无关；若机器数至少等于作业数，可一机一件，达到最大单件四小时。允许抢占后有另一套结构，不能把“把一件拆两半”作为非抢占模型中突破下界的技巧。