流水線調度
流水線調度(英語:Flow-shop scheduling)是計算機科學及運籌學中的一個最佳化問題,是最優作業調度的一個變體。在一般的作業調度問題中,我們有從到這n個工作,每項工作都具有不同的完成時間。我們需要做的是最小化加工周期,也就是完成所有工作所用的時間。而在流水線調度的問題中,每項工作都需要經過m道工序,且第i道工序必須在第i台機器上完成,每台機器在同一時間最多去完成一項任務。
流水線調度是一種特殊的作業車間調度,所有的工作都必須按照嚴格的時間順序進行。該調度模式不僅適用於生產規劃,同時也適用於計算設計。排列流水線調度問題是流水線調度問題的一種特殊類型,在排列流水線調度問題中,所有工作在每道工序上的完成順序是相同的。
在最優作業調度問題的標準三欄位表示法中,流水線調度在第一個欄位中用F表示。例如用於表示三機流水線調度問題,每項工作在每道工序都有自己的加工時間,目標是最小化使最大完成時間。
目標函數
在流水線調度問題中,我們通常會去對所有工序上的工作進行排序,從而對一個或多個目標函數進行優化。通常會用到的目標函數如下:[1]
- (平均)流程時間
- 加工周期max
- (平均)延遲
時間及空間複雜度
加雷等人[2]在1976年的研究成果表明,絕大部分的流水線調度問題均屬於NP困難問題,但是也存在少部分流水線調度問題能在 時間裡解決,比如說 問題就是其中之一,可以通過詹森法則來實現。[3]
參考文獻
- ^ Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. ISBN 978-1-118-58537-5.
- ^ Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. (頁面存檔備份,存於網際網路檔案館) Mathematics of operations research, 1(2), 117–129.
- ^ Johnson, S. M. (1954). Optimal two-and three-stage production schedules with setup times included. (頁面存檔備份,存於網際網路檔案館) Naval research logistics quarterly, 1(1), 61–68.