流水線調度是計算機科學和運籌學中的一個優化問題。它是最佳作業調度的一種變體。在一般的作業調度問題中，給定n個作業J1、J2、...、Jn，它們的處理時間各不相同，需要在具有不同處理能力的m臺機器上進行調度，同時盡量減少制造時間——總長度計劃的時間（即，當所有作業都完成處理時）。在稱為流水車間調度的特定變體中，每個作業恰好包含m個操作。作業的第i次操作必須在第i臺機器上執行。沒有一臺機器可以同時執行多個操作。對于每個作業的每個操作，都指定了執行時間。流水車間調度是作業車間調度的一種特殊情況，其中對所有作業執行的所有操作都有嚴格的順序。流水線調度也可以應用于生產設施和計算設計。一種特殊類型的流水車間調度問題是置換流水車間調度問題，其中作業在資源上的處理順序對于每個后續處理步驟都是相同的。在最優作業調度問題的標準三字段表示法中，流水車間變體在xxx個字段中用F表示。例如，F3|表示的問題p我j{displaystylep_{ij}}|Cxxx限度{displaystyleC_{max}}是一個具有單位處理時間的3機器流水車間問題，其目標是最小化xxx完成時間。

有n臺機器和m個工作。每個作業恰好包含m個操作。作業的第i次操作必須在第i臺機器上執行。沒有一臺機器可以同時執行多個操作。對于每個作業的每個操作，都指定了執行時間。一項作業中的操作必須按指定的順序執行。xxx個操作在xxx臺機器上執行，然后（當xxx個操作完成時）第二個操作在第二臺機器上執行，依此類推，直到第n次操作。但是，作業可以按任何順序執行。問題定義意味著每臺機器的作業順序完全相同。問題是確定最佳的這種安排，即總作業執行時間最短的安排。

測序問題可以描述為確定一個序列S，以便優化一個或幾個測序目標。

• （平均）流動時間，∑(w一世)F一世{displaystylesum(w_{i})F_{i}}
• 制造跨度，Cmax
• （平均）遲到，∑(w一世)噸一世{displaystylesum(w_{i})T_{i}}
• ……

Malakooti(2013)中可以找到有關性能測量的詳細討論。

正如Garey等人提出的。(1976)，流水車間調度問題的大多數擴展都是NP難的，很少有可以在O(nlogn)中最優解的；例如，F2|prmu|Cmax可以通過使用約翰遜法則得到最優解。Taillard為調度流水車間、開放車間和作業車間提供了大量的基準問題。

提出的解決流水車間調度問題的方法可以分為精確算法如分支定界和啟發式算法如遺傳算法。

F2|prmu|Cmax和F3|prmu|Cmax可以通過使用約翰遜規則得到最優解，但對于一般情況，沒有算法可以保證解的最優性。

流水車間包含n個在時間0時同時可用的作業，并由兩臺串聯排列的機器處理，它們之間有無限的存儲空間。所有工作的處理時間都是確定的。需要在機器上安排n個作業以最小化制造時間。下面給出了兩機流水車間作業調度的約翰遜規則。在最優調度中，如果min{p1i,p2j}<min{p1j,p2i}，則作業i在作業j之前。其中，p1i是作業i在機器1上的處理時間，p2i是作業i在機器2上的處理時間。類似地，p1j和p2j分別是作業j在機器1和機器2上的處理時間。對于約翰遜算法：設p1j為作業j在機器1上的處理時間，p2j為作業j在機器2上的處理時間約翰遜算法：

• 表格set1包含所有p1j<p2j的作業
• 表格set2包含所有p1j>p2j的作業，p1j=p2j的作業可以放在任一集中。
• 形成如下序列：(i)set1中的作業按順序排在最前面，它們按p1j(SPT)的升序排列(ii)set2中的作業按p2j(LPT)的降序排列。關系被任意打破。

這種類型的調度被稱為SPT(1)-LPT(2)調度。Malakooti(2013)提供了對可用解決方法的詳細討論。