单机调度

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

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

在最优作业调度问题的标准三字段表示法中，单机变量在第一个字段中用1表示。例如可以用来表示无约束的同机调度问题，其目标是最小化完成时间的总和。
变体
最小化加工周期问题在多机调动中经常被当成目标函数，但在单机调度中意义不大。在单机调度中，我们经常选择一些其他的目标函数进行研究：
是最小化完工时间总和的问题，该问题可用最短处理时间优先（，SPT）原则来解决，即优先解决处理时间短的任务。
是最小化加权完工时间总和的问题，该问题可用加权最短处理时间优先（，WSPT）原则来解决，即优先解决权重和处理时间之比（）更大的任务。
是在具有任务顺序限制的情况下最小化加权完工时间总和的问题，这类问题可以通过泛化的加权最短处理时间优先原则来解决。
是最小化最大延迟时间的问题，在这类问题中，每个工作都存在一个截止日期，如果在截止日期之后才完成任务，那么就会产生一个延迟，延迟的定义是。这类问题可以用最早截止日期优先（，EDD）原则来解决，即优先解决靠前的任务。
问题是问题的泛化。这个问题允许对任务设定前后顺序，并且允许对每个任务的延迟都设定一个成本函数。这一目标函数可以通过一种被称为劳勒算法的贪心算法进行最小化。
问题也是问题的泛化。这一问题允许对每一项任务设定推出时间，每项任务都不得在推出时间之前进行，这就导致了机器可能处于闲置状态。这是一个NP难度的问题，但是可以采取分支定界算法进行优化。
是最小化迟到任务数量的问题，但是不考虑每个迟到任务的延迟。这一问题可以使用霍奇森-摩尔算法进行优化。
是最小化加权后迟到任务数量的问题。这是一个NP难度的问题，因为在每个任务的截止时间都相等（）的特殊情况下，这一问题等价于背包问题。
现假定在截止时间之前完成任务就能得到的收益，反之则无收益。问题的目标是最大化收益。这一问题属于NP困难的问题，计算机科学家薩爾塔伊·薩尼找出了指數時間的准确算法和多项式时间的近似算法。

参考文献

Category:最佳排程