单机调度

单机调度也被称为单资源调度，是计算机科学和运筹学中的一个最佳化问题。在这一问题中，我们有从$J_{1}$到$J_{n}$这$n$个工作，每项工作所需处理时间都不尽相同。我们所需要做的便是将这些工作在机器上进行排程，使其目标函数（诸如吞吐量）实现最佳化。

单机调度问题是同机调度问题的特殊情况，而同机调度又是最优作业调度的特殊情况。许多常见的NP困难问题在单机调度问题中都可以在多项式时间内解决。

在最优作业调度问题的标准三字段表示法中，单机变量在第一个字段中用1表示。例如$1||\sum C_{j}$可以用来表示无约束的同机调度问题，其目标是最小化完成时间的总和。

变体

最小化加工周期问题$1||\sum C_{\max }$在多机调动中经常被当成目标函数，但在单机调度中意义不大。在单机调度中，我们经常选择一些其他的目标函数进行研究：

• $1||\sum C_{j}$是最小化完工时间总和的问题，该问题可用最短处理时间优先（英语：Shortest Processing Time First，SPT）原则来解决，即优先解决处理时间短的任务。
  • $1||\sum w_{j}C_{j}$是最小化加权完工时间总和的问题，该问题可用加权最短处理时间优先（英语：Weighted Shortest Processing Time First，WSPT）原则来解决，即优先解决权重和处理时间之比（$p_{j}/w_{j}$）更大的任务。
  • $1|chains|\sum w_{j}C_{j}$是在具有任务顺序限制的情况下最小化加权完工时间总和的问题，这类问题可以通过泛化的加权最短处理时间优先原则来解决。
• $1||L_{\max }$是最小化最大延迟时间的问题，在这类问题中，每个工作$j$都存在一个截止日期$d_{j}$，如果在截止日期之后才完成任务，那么就会产生一个延迟，延迟的定义是$L_{j}:=C_{j}-d_{j}$。这类问题可以用最早截止日期优先（英语：Earliest Due Date First，EDD）原则来解决，即优先解决$d_{j}$靠前的任务。
  • $1|prec|h_{\max }$问题是$1||L_{\max }$问题的泛化。这个问题允许对任务设定前后顺序，并且允许对每个任务的延迟都设定一个成本函数$h_{j}$。这一目标函数可以通过一种被称为劳勒算法的贪心算法进行最小化。
  • $1|r_{j}|L_{\max }$问题也是$1||L_{\max }$问题的泛化。这一问题允许对每一项任务设定推出时间$r_{j}$，每项任务都不得在推出时间之前进行，这就导致了机器可能处于闲置状态。这是一个NP难度的问题，但是可以采取分支定界算法进行优化。
• $1||\sum U_{j}$是最小化迟到任务数量的问题，但是不考虑每个迟到任务的延迟。这一问题可以使用霍奇森-摩尔算法进行优化。
  • $1||\sum w_{j}U_{j}$是最小化加权后迟到任务数量的问题。这是一个NP难度的问题，因为在每个任务的截止时间都相等（$1|d_{j}=d|\sum w_{j}U_{j}$）的特殊情况下，这一问题等价于背包问题。
• 现假定在截止时间之前完成任务就能得到$p_{j}$的收益，反之则无收益。问题的目标是最大化收益。这一问题属于NP困难的问题，计算机科学家萨尔塔伊·萨尼找出了指数时间的准确算法和多项式时间的近似算法。