同機調度

同機調度是計算機科學和運籌學中的一個優化問題。在這一問題中，我們有從$J_{1}$到$J_{n}$這n個不同執行時間的工作需要完成。除此之外，我們有m個完全相同的機器。在這一問題中，我們需要對特定的目標函數（如加工周期）進行優化。

同機調度是統一機器調度的一種特殊情況，而統一機器調度本身也是最優作業調度的一種特殊情況。兩者的區別在於同機調度中所有的機器完全一樣，而在統一機器調度中不同的機器執行相同的任務所需時間可能會有所不同。單機調度也可以視為一種特殊的同機調度。在最優作業調度問題的標準三字段表示法中，同機變量在第一個字段中用字母P表示。例如$P||C_{m}ax$可以用於表示無約束條件的同機調度問題，其目標是最小化最大完工時間。

算法

最小化平均和加權平均完工時間

最小化平均完成時間（$P||\sum C_{j}$）可以在多項式時間內完成。可以採用最短完工時間優先算法，先對所有工作的按完工時間從小到大進行排序，然後再將這些工作按此順序分配給目前結束時間最早的機器。該算法的時間複雜度為$O(nlogn)$。

• 尋找最小完工時間問題屬於NP困難問題。

即使在完全相同的機器上，最小化加權平均完成時間也屬於NP困難問題，因為這類問題可以轉化為背包問題。即使將機器數量限定在兩台，該類問題也屬於NP困難問題，因為此類問題相當於分區問題。

最小化最大完成時間

最小化最大完成時間問題（$P||C_{max}$）屬於NP困難問題，因為這類問題等同於分區問題。對於這類問題，目前已經有人給出了多種精確以及近似算法。

葛立恆所給證明如下：

• 任何列表調度算法（一種以任意固定順序處理工作的算法，並將每個作業調度到第一個可用的機器上）都在同機調度問題上具有$2-1/m$的近似。對於任何的m，該上界都存在嚴格約束，該算法所需時間為$O(n)$。
• 最長處理時間優先算法是一種特殊的列表調度算法，這些工作按作業時長的降序進行排序，對於相同的機器而言，具有$4/3-1/3m$的近似。

科夫曼、格里和約翰遜提出了multifit算法，該算法使用了集裝優化中所使用的方法，其近似因子為13/11≈1.182。