单机调度问题自1954年首次被研究以来，已成为运筹学和算法设计领域的一个重要分支。本文旨在系统回顾该领域的标准设置、基本性质、多项式可解情形、复杂性以及近似算法研究进展。
基本符号与术语
在单机调度问题中，给定一组作业（Jobs），每个作业j具有处理时间pj 、释放时间rj （作业可开始处理的最早时间）和交付时间qj 或截止日期dj 。调度方案S为每个作业分配一个开始时间sj S ，其完成时间为cj S = sj S + pj 。若考虑交付时间，则作业的完全完成时间 为Cj S = cj S + qj 。关键目标函数包括最小化最大延迟 Lmax = maxj (cj S - dj )或最小化最大完全完成时间 （或称交付时间）Dmax = maxj Dj ，其中Dj = cj S + qj 。值得注意的是，问题1|rj |Lmax 和1|rj |Dmax 通过简单的参数变换（如qj = -dj ）是等价的。调度问题通常使用Graham等人提出的三字段表示法来描述，例如1|rj |Lmax 表示具有释放时间和最大延迟目标的单机问题。
一些基本概念与性质
当所有作业同时释放（即rj 相同）时，最小化完工时间（Makespan）是平凡的，只需按任意顺序无空闲时间地调度作业。然而，当作业具有不同的释放时间和截止日期时，问题变得复杂。著名的最早截止日期优先（Earliest Due Date, ED） 启发式算法（由Jackson提出）对于问题1||Lmax （即所有作业在时间0释放）是最优的。Schrage将其扩展到处理释放时间的情况（1|rj |Lmax ），该算法总是调度当前已释放作业中截止日期最小（或交付时间最大）的作业。虽然Schrage算法对于一般情况并非总是最优，但它提供了一个性能比为2的近似解，即Dmax (S) ≤ 2OPT。
调度结构分析中，溢出作业（Overflow Job） 是指在调度块（Block）中导致最大延迟的作业。与之相关的新兴作业（Emerging Job） 是指截止日期大于溢出作业但被调度在溢出作业之前的作业，其中最后一个这样的作业称为延迟新兴作业（Delaying Emerging Job） 。一个内核（Kernel） 则由延迟新兴作业和溢出作业及其之间的作业组成。一个重要最优性条件 是：如果在一个ED调度中，某个溢出作业没有关联的延迟新兴作业，则该调度是最优的。
通过人为增加延迟新兴作业的释放时间，可以构造互补调度（C-Schedule） ，这为改进解提供了途径，也是许多隐式枚举算法（如分支定界法）的基础。此外，一个有效的下界（Lower Bound） 可以通过公式LB ≥ Dmax (S) - pl(K) 来计算，其中pl(K) 是内核K的延迟新兴作业的处理时间。
研究概述
精确算法与复杂性
问题1|rj |Lmax （或等价的1|rj |Dmax ）是强NP难的。早期的精确算法包括McMahon和Florian以及Carlier提出的分支定界算法。近年来，Pan和Shi改进了Carlier的算法框架，通过生成互补调度和利用修剪（Trimming）技术来减少搜索空间。Della Croce和T'kindt提出了一种基于预emptive ED调度（PED）的替代下界计算方法，通过分析作业在最优调度中可能出现的不同位置来得到更紧的下界。Gharbi和Labidi则引入了半预emptive调度 的概念来获得更强的下界，其中作业被分为固定部分（不可抢占）和自由部分（可抢占）。Vakhania提出了一种基于变参数分析（Variable Parameter Analysis, VPA） 的隐式枚举算法，其时间复杂度依赖于新兴作业的数量ν这个变量参数，在某些情况下（当ν远小于总作业数n时）非常高效。
多项式时间近似算法
由于问题的NP难度，多项式时间近似算法备受关注。如前所述，Schrage算法是一个2-近似算法。Potts通过多次迭代应用Schrage算法，将性能比改进到3/2，但时间复杂度增加到O(n² log n)。Nowicki和Smutnicki提出了另一个3/2-近似算法，时间复杂度为O(n log n)。Hall和Shmoys通过结合原始问题和反向问题的调度，将性能比进一步提升到4/3。
此外，还存在多项式时间近似方案（Polynomial-Time Approximation Scheme, PTAS） ，对于任意常数k，可以找到(1+1/k)-近似解。Hall和Shmoys提出了两个PTAS，其时间复杂度分别与(16k (nk)3+4k )和O(n log n + n(4k)8k²+8k+2 )相关。Mastrolilli为更一般的并行机设置设计了PTAS。Vakhania基于VPA提出了另一个PTAS，其时间复杂度与新兴作业的参数κ有关，为O(κ! κ1.1 n² log n)，对于固定k，κ是一个较小的常数。
多项式可解的特殊情况
在某些限制条件下，问题是多项式可解的。若所有作业同时释放（rj 相同），则按截止日期非递减顺序（EDD规则）调度是最优的。若所有作业具有相同的处理时间p，则问题1|rj , pj =p|Lmax 可以在O(n log n)时间内求解（Garey等人）。若作业处理时间满足整除性质 （例如，是2的幂次），即每个较大的处理时间都能被每个较小的处理时间整除，则问题1|div, rj |Dmax 可以在O(n² log n log pmax )时间内求解，这是具有受限处理时间的问题中最大的多项式可解特殊情况。对于只有两个允许的释放时间和截止日期的问题（1|rj ∈{r₁, r₂}, dj ∈{d₁, d₂}|Lmax ），尽管是弱NP难的，但Reynoso和Vakhania发现了其结构性质，并给出了在大多数实际情况下能快速找到最优解的条件和启发式方法。
其他目标函数与扩展问题
文章还综述了其他重要目标函数。对于最小化迟作业数量（∑Uj ） 的问题，在非抢占情况下，Vakhania为等处理时间作业（1|rj , pj =p|∑Uj ）提出了O(n³ log n)算法。在抢占情况下（1|rj , pmtn|∑Uj ），Lawler、Baptiste和Vakhania相继提出了动态规划算法，将时间复杂度从O(n⁵)优化到O(n³)。对于带权重的抢占调度问题（1|rj , pj =p, pmtn|∑wj Uj ），Baptiste等人给出了O(n⁴)的动态规划算法。
关于总 tardiness（∑Tj ） 目标，即使处理时间和截止日期相反排序（pj 递减，dj 递增）的特殊情况也是NP难的。Lazarev和Werner提出的图形化算法（Graphical Algorithm） 能有效减少动态规划的状态数，用于设计完全多项式时间近似方案（FPTAS）或解决最大化总 tardiness 等特殊问题，将伪多项式复杂度O(n∑pj )转化为多项式复杂度O(n²)。
在线调度与资源约束调度
在在线调度 环境中，作业随时间到达。对于最小化Dmax ，非抢占的LDT启发式算法在线性能比为2。Hoogeveen和Vestjens通过引入等待策略，将最佳可能竞争比提高到(√5+1)/2 ≈ 1.618。若允许作业重启（Restarts） （即中断后需重新开始），van den Akker等人给出了竞争比为1.5的算法。
在非可再生资源（Non-Renewable Resource） 调度中（如资金、能源），作业在开始时消耗资源，而资源在特定时间点补充。Gafarov等人证明了即使是最小化Makespan或总完成时间等简单目标，在存在非可再生资源约束时也是强NP难的。Ramirez等人研究了作业需要消耗能量的单机调度问题（1|rj , ej |Lmax ），并对单位处理时间作业给出了O(n log n)算法。
结论
单机调度问题作为更复杂的多机或车间调度问题的基础，其理论研究成果（如高效算法、下界技术、结构性质）对于解决实际应用中的资源优化问题至关重要。本文系统梳理了该领域的关键理论进展，指出了多项式可解与NP难问题之间的边界，并总结了有效的精确、近似和在线算法。这些成果不仅为运筹学与算法设计提供了重要工具，也为未来研究（如考虑更复杂约束、多目标优化、随机环境等）指明了方向。
打赏
