開放車間調度

開放車間調度（英語：Open-shop scheduling）也被稱為開放車間調度問題（英語：open-shop scheduling problem，OSSP），是計算機科學以及運籌學領域中的最佳化問題。這是最優作業調度的一種變體，在一般的最優作業調度問題中，首先給定$J_{1},J_{2},...,J_{n}$共$n$個作業，每項作業都具有不同的處理時間。我們需要做的就是將這n項作業安排到m台處理能力不同的機器上，並要求最小化加工周期。而在開放車間調度這一變體中，每項作業都存在一組操作$O_{1},...,O_{n}$，所有的操作都需要處理，但可以按照任意的順序進行。這一類型的問題最初是在1976年由特奧菲洛·F·岡薩雷斯與薩塔吉·薩尼進行研究的。

在最優作業調度問題的標準三欄位表示法中，開放車間變量在第一個欄位用O表示。例如，O3|$p_{ij}$|$C_{\max }$就可以表示為一個具有單元處理時間的3台機器作業車間問題，其目標是最小化最大完工時間。

定義

在開放車間調度問題中，我們需要輸入一組工作和一組工作站，以及一張二維的表格，該表格記錄了每項作業在每個工作站所花費時間。每項作業在同一時間只能在一個工作站上處理，同時每個工作站一次只能處理一項作業。然而與作業車間調度問題不同的是，這類問題每步操作的順序都可以自由變化。目標是為每個工作站要處理的每項作業分配一個時間，避免多項作業在同一時間分配到同一工作站以及一項作業在同一時間分配到多個工作站，並且每項作業在期望的時間內完成任務。通常衡量解決方案好壞的標準是它的加工周期，即從進度表的開始（第一個任務分配到第一個工作站）到結束（最後一個工作站完成最後一項任務）的時間量。

計算複雜度

如果只有兩項作業或兩個工作站，那麼開放車間調度問題可以在多項式時間內求解。如果說所有不等於0的解決時間都相等，那麼這種問題也可以在多項式時間內完成。因為在這種情況下，這個問題可以等效於給一個以作業和工作站為頂點的二分圖的邊上色，每條邊代表不為0的作業-工作站對，著色中邊的顏色對應於工作-工作站對被安排處理的時間段。由於二分圖的線圖是完美圖，所以二分圖可以在多項式時間內實現邊著色。

對於三個以上任務以及工作站並且處理時間不相同的問題，難度為NP困難。