text: 流水線排程是計算機科學及運籌學中的一個最佳化問題，是最優作業排程的一個變體。在一般的作業排程問題中，我們有從formula_1到formula_2這n個工作，每項工作都具有不同的完成時間。我們需要做的是最小化加工週期，也就是完成所有工作所用的時間。而在流水線排程的問題中，每項工作都需要經過m道工序，且第i道工序必須在第i臺機器上完成，每臺機器在同一時間最多去完成一項任務。流水線排程是一種特殊的作業車間排程，所有的工作都必須按照嚴格的時間順序進行。該排程模式不僅適用於生產規劃，同時也適用於計算設計。排列流水線排程問題是流水線排程問題的一種特殊型別，在排列流水線排程問題中，所有工作在每道工序上的完成順序是相同的。在最優作業排程問題的標準三欄位表示法中，流水線排程在第一個欄位中用F表示。例如formula_3用於表示三機流水線排程問題，每項工作在每道工序都有自己的加工時間，目標是最小化使最大完成時間。目標函式.在流水線排程問題中，我們通常會去對所有工序上的工作進行排序，從而對一個或多個目標函式進行最佳化。通常會用到的目標函式如下：時間及空間複雜度.加雷等人在1976年的研究成果表明，絕大部分的流水線排程問題均屬於NP困難問題，但是也存在少部分流水線排程問題能在formula_6時間裡解決,比如說formula_7問題就是其中之一，可以透過詹森法則來實現。
metadata.dataset: erhwenkuo/wikipedia-zhtw
metadata.title: 流水線排程
metadata.url: https://zh.wikipedia.org/wiki?curid=7913959