并行机器调度

将作业分配到多台并行机器. 使用调度规则（SPT、LPT、EDD、FCFS、CR、WSPT）将作业分配到相同的并行机器。通过甘特图可视化调度并比较机器利用率。. 并行机调度把一组作业分配到多台同型机器上，以优化诸如最小化…

使用调度规则（SPT、LPT、EDD、FCFS、CR、WSPT）将作业分配到相同的并行机器。通过甘特图可视化调度并比较机器利用率。

什么是并行机器调度？

并行机调度把一组作业分配到多台同型机器上，以优化诸如最小化 makespan（最大完工时间）或总拖期等目标。它把单机调度扩展到制造、计算和物流中常见的多机环境。

LPT（最长加工时间优先）规则是并行机上最小化 makespan 的著名启发式规则：按加工时间由大到小排序作业，并把每个作业分配给最早可用的机器。对于同型机器，LPT 保证 makespan 不超过最优值的 4/3 倍。其他规则（SPT、EDD、WSPT）则针对不同目标进行优化。

机器利用率——每台机器处于忙碌状态的时间占比——反映了负载均衡的好坏。各机器利用率相近说明均衡良好。甘特图可视化展示了每台机器的调度时间轴，使空闲时间和负载不均一目了然。

Formula: Makespan = max(Completion Time of all machines) Utilization = Σ Processing Time / (Makespan x m) Tardiness = max(0, Completion - Due Date) LPT: Assign longest job to earliest available machine SPT: Assign shortest job to earliest available machine

计算示例

用 LPT 把 4 个作业（p=8,6,5,3）分配到 2 台机器：作业1(8)→M1，作业2(6)→M2，作业3(5)→M2（负载 6→11），作业4(3)→M1（负载 8→11）。makespan = 11。利用率：M1=11/11=100%，M2=11/11=100%，完全均衡。若不采用 LPT 而按先到先服务（FCFS）分配，可能得到 makespan=14，且负载严重不均。

何时使用此计算器

需要在多台相同机器上调度一批作业并最小化完工时间或总延迟时
在产能规划中评估增加一台机器是否能有意义地减少当前工作量的完工时间时
比较特定作业组合的调度规则时 — 不同规则优化不同目标，最佳选择取决于您的优先级
机器故障后快速将剩余作业重新调度到可用机器并评估交付影响时
平衡机器间负载以最小化空闲时间并确保所有机器对生产调度做出均等贡献时

常见错误

使用SPT最小化完工时间 — SPT最小化平均流程时间而非完工时间；并行机器的完工时间应使用先分配最长作业的LPT
假设更多机器总是按比例减少完工时间 — 改善遵循收益递减规律；作业大小非常不均时增加机器可能几乎不减少完工时间
作业在不同时间到达时不考虑释放时间 — 静态调度规则假设所有作业在时间零可用；到达时间不同时使用动态调度
忽略机器利用率平衡 — 最小完工时间调度可能使某些机器长时间空闲；检查所有机器的利用率以确保公平和磨损均衡

如何解读结果

所有机器利用率均等（各>90%） — 负载均衡良好；调度规则表现高效
一台机器100%利用率而其他显著较低 — 该机器是瓶颈；最长作业可能决定了完工时间
总延迟 = 0 — 所有作业在截止日期前完成；调度满足所有交付承诺
许多延迟作业和高总延迟 — 工作量超出截止期内的产能；考虑加班、增加机器或协商延长截止日期
LPT和SPT给出非常相似的完工时间 — 作业处理时间相对均匀；作业大小相似时规则选择不太重要

常见问题

在并行机上，哪种派工规则能最小化 makespan？

LPT（最长加工时间优先）是最小化 makespan 的最佳启发式规则。先分配最长的作业，可确保大作业不会在末尾形成瓶颈。LPT 保证所得解不超过最优值的 4/3 - 1/(3m) 倍，其中 m 为机器数量。对于 2 台机器，该界限为最优值的 7/6（约 17%）以内。

作业的投放时间或交货期各不相同时该如何处理？

存在投放时间时，作业只能在其投放时间之后开始——应采用动态派工，在每台机器空闲时重新评估优先级。存在交货期时，EDD 或 CR 规则有助于减少拖期。对于同时含这两类约束的复杂问题，可模拟多种规则并比较绩效指标。最优规则取决于具体的作业组合与目标。