单机调度

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

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

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

变体

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

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