流水線調度

流水線調度(英語:Flow-shop scheduling)是計算機科學運籌學中的一個最佳化問題,是最優作業調度的一個變體。在一般的作業調度問題中,我們有從這n個工作,每項工作都具有不同的完成時間。我們需要做的是最小化加工周期,也就是完成所有工作所用的時間。而在流水線調度的問題中,每項工作都需要經過m道工序,且第i道工序必須在第i台機器上完成,每台機器在同一時間最多去完成一項任務。

流水線調度是一種特殊的作業車間調度,所有的工作都必須按照嚴格的時間順序進行。該調度模式不僅適用於生產規劃,同時也適用於計算設計。排列流水線調度問題是流水線調度問題的一種特殊類型,在排列流水線調度問題中,所有工作在每道工序上的完成順序是相同的。

在最優作業調度問題的標準三字段表示法中,流水線調度在第一個字段中用F表示。例如用於表示三機流水線調度問題,每項工作在每道工序都有自己的加工時間,目標是最小化使最大完成時間。

目標函數

在流水線調度問題中,我們通常會去對所有工序上的工作進行排序,從而對一個或多個目標函數進行優化。通常會用到的目標函數如下:[1]

  1. (平均)流程時間 
  2. 加工周期max
  3. (平均)延遲 

時間及空間複雜度

加雷等人[2]在1976年的研究成果表明,絕大部分的流水線調度問題均屬於NP困難問題,但是也存在少部分流水線調度問題能在 時間裏解決,比如說 問題就是其中之一,可以通過詹森法則來實現。[3]

參考文獻

  1. ^ Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. ISBN 978-1-118-58537-5.
  2. ^ Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. 頁面存檔備份,存於互聯網檔案館) Mathematics of operations research, 1(2), 117–129.
  3. ^ Johnson, S. M. (1954). Optimal two-and three-stage production schedules with setup times included. 頁面存檔備份,存於互聯網檔案館) Naval research logistics quarterly, 1(1), 61–68.