編者按

本文對于單一工序、單一資源，單一工序、多資源，多工序、單一資源(較少)，多工序、多資源這四種常見的生產計劃類型進行逐一分析，著重于計劃的優化，而非硬性規則的確保。其中，針對多工序、多資源生產計劃類型具體描述了基于Optaplanner設計APS（進階生產規劃及排程系統）排產引擎時遇到的棘手問題，包括：計劃類型的識別，由任務組成的工序鏈與機臺鏈，任務與機臺之間的匹配，工序鏈與機鏈之間的存在膠著可能性，以及循環識別與處理的問題。

一  單一工序，單一資源種類

對單一工序、單一資源種類的情況，是最簡單的一種排產場景。即一個產品的生產過程只需使用同一種資源，進行一次加工即完成了產品的整個生產過程。這種情況下，既然是單一工序，那也就沒有了工序的先后資源的限制；單一種類資源，即沒有了資源的選擇優化。

這里提到的資源，是指需要完成一個生產作業（或稱任務，生產任務）所需的生產條件，例如機臺、原料等，即廣義資源。生產實踐中，這類計劃通常是對產品眾多工序路線中的一個較重要的工序進行制定計劃時使用。需進行優化的主要目的是對資源的使用分配，比如各機之間實現負荷平衡等需求。

實現這類計劃時，需要通過設定機臺平衡的約束，讓引擎在為工序分配任務時，盡可能實現同一類機的負荷平衡。比如印刷生產中對排在最后的手工工序制定生產計劃時，需要根據各個產線的人力安排情況，按比例安排定額任務。

二  單一工序，多資源種類

對單一工序、多資源種類的情況，僅對產品一個工序進行排產，僅可用于這個工序的資源是多種多樣的，并且各種資源之間可以互換。此類計劃主要為了實現資源的優化分配，即按照一定原則對各個工序進行資源安排。各種資源使用成本各不相同，在制定計劃時，為了降低生產成本，應在確保其它更高優先級的約束或硬性約束的前提下，盡量使用低成本的資源進行生產。

例如，在印刷行業印刷印張的工序中，有些印張可以通過CMYK四色印制，也可通過調配特殊色通過專色印制，但前者成本相比后者更低，前后兩種印刷方式就表示兩種資源。在對印刷工序定制生產計劃時，就會優先使用CMYK印刷，但并非絕對，如果CMYK資源已經超出負荷，不動用專色印刷就無法實現按時交貨時，還是會放棄成本這個約束，來遷就交期這個更高優先級的約束。

三  多工序，單一資源種類

多個工序，單一種類資源的情況，則相對較少見。即計劃中需要制定整個產品工序路線中的所有工序資源和時間，其中資源要求只有一種可選。可以理解，這種情況對資源分配的要求較低，計劃著重于對工序的前后關系制約或工序自身其它因素的優化。即在資源分配上，如第一種情況“單一資源、單一任務”一致，基于資源利用的一些原則進行資源分配。而在安排工序的加工時間問題上，則需要根據產品的工序路線，實現對前后工序在時間上的次序關系，而這種次序又受到資源分配的限制。

例如：如果印刷的第二工序中（有些企業稱為印后加工），有過油、過膠、過UV三個工序，如果有一種機臺同時可以實現這三種工序，那就滿足“多個工序、單一資源種類”的場景。這時關于工序的資源分配，會有相應的資源使用約束。但更重要的約束是：一個產品多個工序的處理次序上，這個次序必然是根據產品的工序路線設定的資源來執行的，否則就違反了硬性約束。

所以，綜合上述的資源分配和工序資源兩種要求，我們需要面對的是互相矛盾的問題：其一，對于同一個產品需要確保其執行的工序與工序路線上設定的一致；其二，對于一個資源（例如機臺）上的生產效率而言，如何實現更多的同工序連接生產。

即使使用同一資源，通常在該資源上，不同工序的生產任務之間的切換會產生成本，可能是時間成本，也可能是具體的貨幣成本。所以，難點就在于如何平衡上述兩個問題，從而實現資源利用率最大化和工序資源不被違反。

四  多工序，多資源種類

多個工序，多資源種類的和產計劃，是目前最為常見，也最為復雜的生產計劃，是本文討論的重點。多工序與前一個問題一樣，是針對整個產品的工序路線進行排產，而且生產各個工序所用的資源屬于不同種類。

這種情況面對兩個相對零散也有交互的矛盾：其一，對于一個產品而言，其多個工序是依據工序路線形成生產資源的；其二，多種資源表示各個生產工序所使用的資源有可能不一樣，也有可能不同。

因工序前后次序的限制原因，當引擎對一個工序完成資源分配后，進一步進行生產時間的分配。但因為同一產品的工序執行次序，需要按照工序路線的先后次序來執行，也就是計劃中除了需要分配好的資源外，還要確保這個資源在指定的時間段內，沒有被其它產品的生產任務占用。那么當同時對多個產品進行排產時，各個產品的工序路線形成的工序生產序列和資源分配方案，很容易就形成膠著狀態，甚至在多個資源之間出現死鎖狀態。

下面，我們以多個不同種類的機臺，處理工序路線上多個工序的案例，來計劃“多工序、多資源種類”的情況，并分析需要實現這種計劃，所需的技巧、技術難點和可能出現的情況，及其應對方法。

1、多工序與多機臺的場景描述

規劃過程中用到的概念。為了便于描述規劃過程中的各種情況，現先定義以下概念：

(1) 任務或生產任務：一個產品的一個工序的生產作業稱作一個任務，例如印刷后加工有：過膠 -> 燙金 -> 絲印，則表示這個產品的后加工中有三個任務，分別是過膠任務， 燙金任務和絲印任務。

(2) 工序路線任務鏈：一個產品中的不同工序對應的生產作業，其次序是由其工序路線確定的，一個產品的所有生產作業序列，即任務序列，稱為工序路線任務鏈。

(3) 機臺任務鏈：多個任務被分配在一個機臺上時，同一時間只能處理一個產品，即同一時間只能進行一個任務，這些同在一機臺上形成的任務序列，稱為機臺任務鏈接。

(4) 前置任務，后置任務：同一產品上多個任務，根據工序路線的規定形成與工序次序一次的生產任務次序（即工序路線任務鏈）。在鏈中兩個相鄰的任務，前者稱作后者的前置任務；后者稱作前者的后置任務。

(5) 前一任務，后一任務：分布于同一機臺上的多個工序任務（即機臺任務鏈），在機臺任務鏈中相個相鄰的任務；前者稱為后者的前一任務，后者稱作前者的前一任務。

2、多工序、多機臺排程里的限制

下面我們來針對實用性最強，制造業面對最多的場景 ：多工序、多臺機臺場景展開討論。處理這類生產計劃，以下兩個因素最為麻煩。

(1) 多任務與多機臺的匹配

在待排的計劃要素中，任務與機臺的種類都存在多樣性，且可能存一種任務可分配到多種機臺，一種機臺可以做多種任務的情況，因此，任務與機臺的匹配問題會相對其它三種生產計劃復雜一些，但往往這也是體現出Optaplanner價值的一個要點。

(2) 工序路線任務鏈與機臺任務鏈之間存在互相制約關系

 一個產品的工序中先確定的任務序列，與分配于同一機臺上的任務序列，在加工次序上互相制約。加工次序體現在加工的時間先后，即一個產品的任務序列，必然按其工序路線，存在一定的先后次序。而單個產品被分配到各個機臺上進行生產作業時，因生產路線上存在時間先后次序，會令到一個機臺上多個任務需要按次序生產的時候，每個任務的作業時間段可能并不緊密連接。

當準備在機臺上啟動一個任務時，這個任務的前置工序可能尚未完成，從而令到該任務所在的機臺已就緒（其前一任務已完成，機臺已為該任務準備就緒），但因為它的前置工序還沒完成，導致它無法開始，一旦開始就違反了工序路線約束，令該機臺上排在后面的其它后任務都要推遲，而這些任務被推遲，又可能導致它們自身的后置任務需要推遲，從而會出現機臺任務鏈和工序路線任務鏈互相影響。這種情況稱為“連鎖反應”，解決好這種連鎖反應是解決排程的關鍵。

上述描述的連鎖反應的情況出現，有可能出現環狀影響的情況。因為一個正常的生產計劃存在時間與空間兩個主要維度，其中空間維度本文的場景就是機臺，表示一個任務被分配到了指定機臺。時間維度則體現為任務的開始和結束時間（事實上結束時間可以通過開始時間推導出來），即確定一個任務的計劃開始時刻。那么就需要有一個邏輯，對各個已分配空間（即機臺）的任務進行時間推導。

任務的時間推導我們需要通過Optaplanner的afterEntityChanged事件來進行（這個事件僅出現于Chained Through Time模式，以后將會有專門的文章講述Optaplanner的時間分配模式，其中Chained Through Time模式是重點），而推導的起源（就是從哪個任務開始推）通常以當前Move（Optaplanner的最小作業單位）所處理的任務開始，這個任務稱為震動源。

經過它的工序路線任務鏈傳遞到機臺任務鏈，再由機臺任務鏈的影響回工序路線任務鏈，當這種環狀的影響線路，經過一系列連鎖反應，正好返回來對震動源進行推導時候，就相當于又開始了與上一輪一樣的推導路線，便會無限推導下去，死循環就產生了。

我們需要準確識別這種連鎖反應會否產生死循環，并當確實產生死循環時，就要將當前的move標識的不合法，在開啟時間推導之前，通過Optaplanner的Move Selection Filter將當前的move取消，從而避免產生程序溢出，令系統崩潰。下面會舉實際的死循環例子說明這種情況。

下面我們先明確多任務多機臺生產計劃的基礎約束，再討論死循環的具體產生經過。

3、計劃約束

每個工序只能分配到指定的機臺。

(1) 除產品的首個工序外，所有任務都有一個前置任務，它的開始條件是前置任務已結束，即同一產品的工序根據工序路線存在FS關系。

(2) 同一機臺同一時間只能處理同一任務。即分配到機臺上的工序生產任務，而生產時間不能重疊。

4、排程過程中產生的死循環

例如下圖：紅框的任務Task1, Task2, Task3表示了一個產品的工序路線上的3個工序對應的任務，表示這三個任務形成了工序路線任務鏈，它們分別分布于machine1, machine2, machine3三個機臺。

根據工序路線任務鏈的次序約束，其生產次序是Task1 -> Task2 -> Task3。藍色背景的兩個任務則是另外一個產品的工序路線任務鏈，根據該產品的工序路線，它的生產門外漢是TaskA -> TaskB, 可以看到這兩個工序的次序跟紅框工序中的Task2, Task3的次序是倒過來的。而從機臺machine2的機臺任務鏈上，可以看到，存在一個這樣的生產次序關系：Task B -> Task 2。

那么在Optaplanner通過一個Move來產生一個可能的方案，并對這個方案中各個任務的開始時間進行推導時，就有可能組合出如圖中的狀態，從而出現死循環，因為一個產品的工序需要按工序路線任務鏈的次序執行，而一個機臺上生產機臺任務鏈中的任務也是存在先后關系的，也即具有時序性，一個機臺在同一時間只能生產一個任務，也就有了一個機臺自身的生產任務也是一個次序鏈的。

從圖中可以看出，存在了這么一個環狀的生產任務次序：Task2 -> Task3 -> TaskA -> TaskB -> Task2，即當Task1, Task2, Task3, TaskA, TaskB中任意一個任務的開始時間被推導時，它都將成為上述死循環描述中的震動源，從而產生死循環。

5、實際多工序多機臺生產計劃中的約束

在實際生產制造場景中，除了上述討論的三個主要約束外，還會存在很多企業自身業務場景相關的限制因素，會更大程度上限制生產活動的執行。而此限制需要正確反映到生產計劃中，否則最終產生的計劃就無法執行。本文只列出對生成計劃的正確性有影響、各計劃均會存在的共性因素，那些與各個行業、企業的業務相關的個性化因素，則不在本文考慮范圍內。

例如：印刷行業中的印刷后加工工序，做完灑金粉工序，是需要等待一定時間，令金粉固化后，才能進入下一工序的，那么也就是說這個工序與下一個工序之間存在一個最短時間間隔的限制，否則是會產生質量事故的，因此是一個硬約束。

6、任務死循環的檢測

因為生產計劃的復雜性，造成工序任務鏈與機臺任務鏈之間存在異常復雜的制約，需要對Optaplanner產生的可能方案進行合法性判斷，識別任務的開始時間推導過程中，是否存在死循環的可能，則需要非常嚴謹的邏輯分析與正確的模型與算法設計。現舉例說明此類項目中在這方面遇到的問題。

當機臺任務鏈、工序路線任務鏈設計出來，并明確了模型中各實體的職責和關系后，如果發現了時間推導存在死循環的可能，就根據推導過程中可以出現的情況進行死循環檢測，檢測過程相當簡單。

當一個可能方案中任務的時空關系確定之后，所有任務便構成了一個有向圖（directed graph），那么我們檢查這個有向圖是否存在環即可。可以嘗試使用隊列結構對這個圖進行廣度優先遍歷，并識別環是否存在；也可以嘗試通過遞歸方式進行深度優先遍歷（遞歸使用的數據結構就是棧，即從WinAPI32編程中學過的函數調用機制，調用路徑實質就是一個棧)。

如果無論怎么嘗試，檢測結果就是無法完美、全面，可能原因是項目中需要考慮的因素更多，出現意想不到的可能性更大。此時解決辦法是：對Optaplanner在規劃過程中產生的每個可能方案，都進行模型上的抽象與簡化，去除一些不影響死循環判斷的因素，把它歸約成一個有向圖，并通過一些成熟的有向圖環檢測的算法對其進行判斷。

有向圖的思路是：把之前根據復雜的業務規則，實現不同的邏輯進行分支檢測的方法倒過來，將含有一些業務因素的有向圖歸約成數學算法能夠處理的規范的有向圖，再對其進行檢測。目前這個功能已經相當穩定，一般不會出現意想不到的意外情況。關于有向圖的環檢測算法，網上有很多，這里不在本文深究。

7、通過Selection Filter對不合法方案進行過濾

若只研究本文中提出的多任務多機臺生產任務的三個基本約束，上文提到的不合法方案就只剩下任務死循環方案了。現實項目開發中，一個方案不合法的定義會更多、更豐富，且更復雜。一旦通過各種手段檢測出一個方案是不合法的，可以通過Selection Filter，在Optaplanner對的VariableListener對象的afterEntityChanged事件處理方法之前，把move放棄掉。關于Selection FIlter的用法，可以從Optaplanner的開發手冊中查看，后面將會專門撰寫Selection Filter相關的文章對其進行說明。

本文描述了基于Optaplanner設計APS排產引擎時，遇到比較棘手的問題，包括：計劃類型的識別，由任務組成的工序鏈與機臺鏈，任務與機臺之間的匹配，工序鏈與機鏈之間的存在膠著可能性，及循環識別與處理。

本人也是初始研究APS排程引擎，還在不斷探索中，有不正確的地方，還請多多指正。