open shop

在理論計算科學和操作研究中，開放車間調度算法（OSSP），是在一套所給定的工作站以及所給定的時間處理提供的一套工作的調度算法，順序隨意。目標是決定在任意一個工作站作業被加工的時間。Teofilo F. Gonzalez 和 Sartaj Sahni在1976年第一次研究了這個問題

基本介紹

• 中文名：開放車間調度
• 外文名：open shop scheduling

正式定義

更精確來說，開放車間調度的輸入為一組大小為n的工作，另一組大小為m的工作站，以及一個每個工作在任一工作站花費時間的二維數組（花費的時間有可能為0）。每個工作一次只能在一個工作站內執行，並且一個工作站一次只能執行一個工作，但是不像作業調度那樣，執行的順序可以隨意變化。目標是對每一個作業在每一個工作站上工作的時間進行分配，使得在同一時間內沒有兩個作業在相同的工作站內進行工作。並且每個工作在每個工作站上分配到理想的執行時間。一般用完工時間衡量一個解決方法的質量好壞（從調度開始直到調度結束）。

計算複雜度

開放車間調度可以在一個多項式時間內完成，例如只有兩個工作或者只有兩個工作站。當所有非零加工時間相同時也可以在一個多項式時間內完成：在這個情況下，問題相當於給一個把工作和工作站當成點、每個工作和工作站配對為非零加工時間的邊的圖的每個邊塗色。圖內每個邊的顏色相當於一個工作-工作站邊被調度加工的時間段。

對於三個以上的工作站，因為加工時間變化很多，開放車間調度複雜度很高。