单机调度

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

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

在最优作业调度问题的标准三字段表示法中，单机变量在第一个字段中用1表示。例如1||\sum C_j可以用来表示无约束的同机调度问题，其目标是最小化完成时间的总和。
变体
最小化加工周期问题1||\sum C_{\max}在多机调动中经常被当成目标函数，但在单机调度中意义不大。在单机调度中，我们经常选择一些其他的目标函数进行研究：
*1|| \sum C_j是最小化完工时间总和的问题，该问题可用最短处理时间优先（，SPT）原则来解决，即优先解决处理时间短的任务。
1|| \sum w_j C_j是最小化加权完工时间总和的问题，该问题可用加权最短处理时间优先（，WSPT**）原则来解决，即优先解决权重和处理时间之比（p_j/w_j）更大的任务。

参考文献