text: 同機排程是計算機科學和運籌學中的一個最佳化問題。在這一問題中，我們有從formula_1到formula_2這n個不同執行時間的工作需要完成。除此之外，我們有m個完全相同的機器。在這一問題中，我們需要對特定的目標函式進行最佳化。同機排程是統一機器排程的一種特殊情況，而統一機器排程本身也是最優作業排程的一種特殊情況。兩者的區別在於同機排程中所有的機器完全一樣，而在統一機器排程中不同的機器執行相同的任務所需時間可能會有所不同。單機排程也可以視為一種特殊的同機排程。在最優作業排程問題的標準三欄位表示法中，同機變數在第一個欄位中用字母P表示。例如formula_3可以用於表示無約束條件的同機排程問題，其目標是最小化最大完工時間。演算法.最小化平均和加權平均完工時間.最小化平均完成時間可以在多項式時間內完成。可以採用最短完工時間優先演算法，先對所有工作的按完工時間從小到大進行排序，然後再將這些工作按此順序分配給目前結束時間最早的機器。該演算法的時間複雜度為formula_5。即使在完全相同的機器上，最小化加權平均完成時間也屬於NP困難問題，因為這類問題可以轉化為揹包問題。即使將機器數量限定在兩臺，該類問題也屬於NP困難問題，因為此類問題相當於分割槽問題。最小化最大完成時間.最小化最大完成時間問題屬於NP困難問題，因為這類問題等同於分割槽問題。對於這類問題，目前已經有人給出了多種精確以及近似演算法。葛立恆所給證明如下：科夫曼、格里和約翰遜提出了multifit演算法，該演算法使用了集裝最佳化中所使用的方法，其近似因子為13/11≈1.182。
metadata.dataset: erhwenkuo/wikipedia-zhtw
metadata.title: 同機排程
metadata.url: https://zh.wikipedia.org/wiki?curid=7904311