流水線調度

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

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

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

目標函數

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

1. （平均）流程時間$\sum (w_{i})F_{i}$
2. 加工周期_max
3. （平均）延遲$\sum (w_{i})T_{i}$

時間及空間複雜度

加雷等人在1976年的研究成果表明，絕大部分的流水線調度問題均屬於NP困難問題，但是也存在少部分流水線調度問題能在$O(nlogn)$時間裡解決,比如說$F2|prmu|C_{max}$問題就是其中之一，可以通過詹森法則來實現。