調度問題（scheduling），又稱排序問題，指將若干工件（job）在一些機器上進行加工，合理安排機器和工件，以使目標函式最優的過程。
基本介紹
- 中文名：單機調度
- 外文名：scheduling
- 別名：排序問題
- 類型：調度
定義,調度專業名詞,三參表示法,問題發展歷程,
定義
“單機調度”問題所提到的調度，指的是作業和機器作業順序的調度。不包括車輛、人員、路徑和時間等方面的調度。
定義：將若干工件（job）在一些機器上進行加工，合理安排機器和工件，以使目標函式最優的過程。
習慣上，把需要完成的任務稱為工件（job），把完成任務所需資源稱為機器（machine）。
調度專業名詞
交貨期（Due date ）工件應該交貨的時刻；
完工時間（Completion time）最後一道工序加工結束的時間；
釋放時間（release time）或到達時間（arrival time）：工件可以開始加工的時間；
流程時間（flow time）：數值上等於完工時間-到達時間，還等於processing time+ waiting time；
延誤時間（tardiness）：=max{0，完工時間-交貨期}；
超前時間（earliness）：= max{0, 交貨期-完工時間}；
等待時間（waiting time）：工件第k-1個工序結束到第k個工序開始的時間差。
三參表示法
1967年Conway提出了調度問題的四參數表示法，後來Graham、Lawler等人（1979）提出了更好的三參數表示法（α|β|γ），如下：
單機調度
其中：
α用於描述機器的數、類型等機器環境信息；
β用於描述工件的加工約束和特定限制信息；
γ用於描述目標函式。
各參數具體表示（部分）
單機調度
單機調度
三參表示法舉例
該三參表示：單機調度、具有學習效應，目標函式為總加權完成時間最短。
單機調度
問題發展歷程
Chris N. Potts （University of Southampton）用幾個時間段粗略描述了排序問題的發展。
第一個階段：引入scheduling問題的新模型，發展基於組合最佳化方法的新算法。
第二階段：使用分支定界法解決scheduling問題。
第三階段：（scheduling領域發展極其重要的10年）：①Edmonds關於計算複雜度概念，為新算法的發展指明了方向；②1979年三參表示法的提出，為問題的分類工作做出極大貢獻。
第四階段：近似解（或滿意解），由於scheduling問題屬於NP問題，因此考慮到計算複雜度和時間複雜度，應該用approximation algorithms 和heuristic algorithms求得滿意解。
第五階段：更高級模型，包括線上問題和半線上問題、學習效應、供應鏈調度等等。
未來發展方向：問題界定和在多項式時間解決問題的研究已經幾乎都做過了，以後應該引入新的模型或者加入新的限定因素。
