同机调度

同机调度是计算机科学和运筹学中的一个优化问题。在这一问题中，我们有从${\displaystyle J_{1}}$到${\displaystyle J_{n}}$这n个不同执行时间的工作需要完成。除此之外，我们有m个完全相同的机器。在这一问题中，我们需要对特定的目标函数（如加工周期）进行优化。

同机调度是统一机器调度的一种特殊情况，而统一机器调度本身也是最优作业调度的一种特殊情况。两者的区别在于同机调度中所有的机器完全一样，而在统一机器调度中不同的机器执行相同的任务所需时间可能会有所不同。单机调度也可以视为一种特殊的同机调度。在最优作业调度问题的标准三字段表示法中，同机变量在第一个字段中用字母P表示。例如${\displaystyle P||C_{m}ax}$可以用于表示无约束条件的同机调度问题，其目标是最小化最大完工时间。

算法

最小化平均和加权平均完工时间

最小化平均完成时间（${\displaystyle P||\sum C_{j}}$）可以在多项式时间内完成。可以采用最短完工时间优先算法，先对所有工作的按完工时间从小到大进行排序，然后再将这些工作按此顺序分配给目前结束时间最早的机器。该算法的时间复杂度为${\displaystyle O(nlogn)}$。[1]

• 寻找最小完工时间问题属于NP困难问题。

即使在完全相同的机器上，最小化加权平均完成时间也属于NP困难问题，因为这类问题可以转化为背包问题。[1]即使将机器数量限定在两台，该类问题也属于NP困难问题，因为此类问题相当于分区问题。

最小化最大完成时间

最小化最大完成时间问题（${\displaystyle P||C_{max}}$）属于NP困难问题，因为这类问题等同于分区问题。对于这类问题，目前已经有人给出了多种精确以及近似算法。

葛立恒所给证明如下：

• 任何列表调度算法（一种以任意固定顺序处理工作的算法，并将每个作业调度到第一个可用的机器上）都在同机调度问题上具有${\displaystyle 2-1/m}$的近似。[2]对于任何的m，该上界都存在严格约束，该算法所需时间为${\displaystyle O(n)}$。
• 最长处理时间优先算法是一种特殊的列表调度算法，这些工作按作业时长的降序进行排序，对于相同的机器而言，具有${\displaystyle 4/3-1/3m}$的近似。[3]:sec.5

科夫曼、格里和约翰逊提出了multifit算法，该算法使用了集装优化中所使用的方法，其近似因子为13/11≈1.182。

参考文献

1. Horowitz, Ellis; Sahni, Sartaj. Exact and Approximate Algorithms for Scheduling Nonidentical Processors. Journal of the ACM. 1976-04-01, 23 (2): 317–327. ISSN 0004-5411. S2CID 18693114. doi:10.1145/321941.321951. 
2. Graham, Ron L. Bounds for Certain Multiprocessing Anomalies. Bell System Technical Journal. 1966, 45 (9): 1563–1581 [2022-03-15]. ISSN 1538-7305. doi:10.1002/j.1538-7305.1966.tb01709.x. （原始内容存档于2022-03-15） （英语）. 
3. Graham, Ron L. Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics. 1969-03-01, 17 (2): 416–429 [2022-03-15]. ISSN 0036-1399. doi:10.1137/0117039. （原始内容存档于2021-10-28）.