約束優化求解作業車間調度問題研究

楊宏安 孫啟峰 郭 杰

西北工業大學，西安，710072

0 引言

作業車間調度問題（job shop scheduling pr oblems，JSSP）實質是調度優化問題，而調度優化問題又屬于一類典型的約束優化問題。近年來，近似調度方法（如遺傳算法、禁忌搜索、模擬退火和免疫算法等）是國內JSSP研究領域的主流方法，其調度模型基本上都可以視為在滿足工藝路線、機床能力和交貨期等約束條件下的單／多目標優化問題，而求解方法均屬于啟發式搜索。由于JSSP屬于典型的NP困難問題，且實際生產車間具有大規模、多任務、多資源、多約束和動態隨機性等特點，近似調度方法真正應用于指導企業生產實踐的成功案例較少。

約束優化問題（constrained opti mization problems，COP）是在約束滿足問題（constraint satisfaction proble ms，CSP）基礎上發展而來的。CSP方法以滿足實際問題的所有約束條件為出發點，在其模型中不包含目標函數；而COP和CSP的本質區別是在模型中引入了目標函數，從而使之更貼近調度優化問題，同時也使得該類問題的求解復雜度顯著提高。作為人工智能中相當活躍的研究領域，CSP／COP能很好地描述智能領域的組合、調度和規劃等復雜問題，尤其適合于描述和求解大規模的組合優化問題。

確定型JSSP和COP都是在事先已知變量和約束的前提下，尋求變量的合理取值，并在滿足所有約束的前提下優化特定的目標函數，因此，作業車間調度問題和約束優化問題的相似性和吻合度較高。Fox［1］首次將CSP方法引入車間調度問題研究之中，并在此基礎上開發出基于啟發搜索技術的ISIS調度系統［2］。Smith等［3］于20世紀90年代初開發完成基于Macro－Opport unistic的OPIS調度系統。Sadeh在變量／值排序啟發算法［4］和 回 溯 處 理［5］等 方 面 進 行 了 深 入 研 究。Barták等［6］近年來在基于約束規劃的計劃和調度方面開展了大量研究工作。

國內將CSP方法應用于求解JSSP的相關文獻較少。文獻［7－9］對基于約束滿足的車間調度進行了綜述。文獻［10］針對Job Shop調度問題，采用形式化的約束一致性實施、操作選擇策略、開始時間選擇策略和不完全回跳策略來提高約束滿足調度算法的求解效率。文獻［11］針對作業車間排序重調度問題，提出了一種可分布求解的分級模型，并對分級模型采用改進的修復約束滿足算法進行求解。

目前，國內已開始將CSP方法引入到JSSP的研究中，但CSP方法僅以求得調度問題的滿意解為出發點，而沒有涉及調度目標函數的優化問題。本文以CSP方法為基礎，將提前／拖期優化指標引入CSP中，使約束滿足問題升級為約束優化問題；基于COP和JSSP的吻合度考慮，將作業車間調度問題轉化為約束優化問題，綜合運用COP的四元組建模方法和回溯搜索方法對JSSP進行模型描述和算法求解，旨在構建從模型描述、調度策略設計、調度算法設計和仿真試驗在內的約束優化技術求解JSSP的完整研究框架，并為后續進一步深入研究約束優化調度引擎搭建基礎性支撐平臺。

1 約束優化問題

定義1 約束優化問題由一個變量集、變量值域、約束集和目標函數組成，可視為一個四元組P ＝ （V，D，C，O）。其中，V 為變量集，V ＝ ｛V1，V2，…，Vn｝；D為各變量的候選值域集，D ＝ ｛D1，D2，…，Dn｝，C 為變量之間的約束集，C ＝ ｛c1，c2，…，cm｝，O 為目標函數。

定義2 約束優化問題的解是在滿足全部約束集C的條件下，在變量集V內尋求一組變量賦值｛a1，a2，…，an｝并使得目標函數O取得最優，其中ai∈Di。

2 約束優化調度模型

2．1 相關變量說明

對于調度任務池內的任意零件Ji，假設Ji的任一加工工序為Oli，其中，i＝1，2，…，n；l＝1，2，…，m；n為零件數量，m為零件Ji內的工序數量。表1、表2分別為零件Ji和工序Oli的相關加工參數定義。

表1 零件J i相關參數定義

表2 工序Oli相關參數定義

2．2 約束優化調度模型

根據定義1，采用COP的四元組分析方法來構建約束優化調度模型。

2．2．1 變量集

作業車間調度的根本任務是確定各零件加工工序在機床上的開工時間，因此，變量集的構造直接以調度任務池內各零件的加工工序作為獨立決策節點，變量定義為任意零件Ji的任一工序Oli的開工時間stli。

2．2．2 約束集

對于離散加工型車間而言，一個可行調度方案的先決條件是滿足工藝路線和機床能力兩類硬約束，另外，零部件交貨期約束也是保證整機配套和成品交付的必備條件。

（1）工藝路線約束。該約束描述了同一零件內不同工序之間的時序關系。假設在零件Ji內，Oli是工序Oji的下游工序，則工藝路線約束為stji＋duji≤stli。

（2）機床獨占性約束。該約束描述了承制機床上加工工序隊列的時序關系。假設工序Oli和Okj由同一機床加工，則二者之間的機床獨占性約束為（stli＋duli≤stkj）∨ （stjk＋dujk≤stli）。

（3）時間約束。該約束描述了某一零件的釋放期（或投料期）和交貨期約束。對于零件Ji，其首道工序O1i和末道工序Omi的開工時間應滿足Ji的可接受最早釋放期和可接受最晚完工時間約束：（st1i≥er di）∧ （stmi＋dumi≤lcdi）。

2．2．3 目標函數

（1）提前／拖期調度成本。針對調度任務池內的任一零件Ji，存在以下拖期、庫存調度成本：①拖期成本，零件Ji的拖期成本Tar di＝tar di×max（0，Ci－ddi），其中，tar di為Ji的拖期懲罰系數。②庫存成本包括零件的在制品流動成本和成品庫存成本兩部份。其中，在制品流動成本定義為零件從投料開始至實際加工結束之間的現場在制品積壓成本。零件Ji的庫存總成本Invi＝ddi－Ci），其中，invli為工序Oli的在制品庫存成本系數。

（2）調度目標。在計算出任意零件Ji的拖期和提前成本后，整個調度任務集的調度總成本ScheduleCost調度目標則是在滿足上述所有約束集的前提下，在各工序開工時間值域內尋求一組合理取值，使得調度總成本ScheduleCost最小。

2．3 基于約束傳播的變量值域初始化方法

上述約束優化調度模型業已構造完成COP四元組中的變量集、約束集和目標函數，而變量值域即為各工序開工時間的候選取值時間窗口。初始搜索狀態下的工序開工時間值域依據約束傳播方法產生。

約束傳播方法：各工序最早開工時間根據零件的最早可接受釋放期沿工藝路線向下游工序依次順序傳播，而工序最晚開工時間則依據零件的最晚可接受完工時間沿工藝路線向上游工序依次倒序傳播，從而即可確定各工序的開工時間窗口。以工序Oli為例，其初始搜索狀態下的開工時間值域計算如下：

式中，estli＋1為Oli的下道工序的最早開工時間；lstil－1為Oli的上道工序的最晚開工時間。

3 約束優化調度策略設計

3．1 兩階段調度策略

JSSP屬于典型的NP困難問題，傳統調度優化方法很難滿足大規模調度對模型描述和計算效率的更高需求。因此，為降低大規模JSSP的求解復雜度和提高調度算法的實用性，遵循解決實際工程問題的思維模式和原則，將求解大規模JSSP劃分為“瓶頸機床識別”和“單機排序優化”兩個階段，即在各搜索空間內，首先計算和識別出當前狀態下的瓶頸機床，然后以該瓶頸機床為載體，對競爭該機床的多個工序采用單機排序優化方法進行處理。這種貼近生產實際的處理策略可以有效降低多機排序優化的復雜度，從而使得求解大規模JSSP的困難度顯著較低。

3．2 動態修訂搜索空間策略

因工藝路線和機床獨占性兩類硬約束的存在，已調度工序的賦值結果勢必影響剩余搜索空間內相關工序的開工時間值域，進而對下一搜索空間內的瓶頸機床識別、變量排序和值排序等環節產生連鎖影響。因此，引入動態修訂搜索空間的調度策略，根據已調度中間結果和約束集，調整和過濾剩余搜索空間各工序開工時間的值域，及時修訂搜索空間的概率計算，以保證啟發規則始終指向于當前搜索狀態下的瓶頸機床，從而為第二階段的單機排序優化提供計算依據。

4 “Thrashing”現象消減機制

“Thrashing”現象是指在回溯算法搜索過程中頻繁發生約束沖突的現象。“Thrashing”現象的存在嚴重制約回溯搜索的求解效率，并有可能導致回溯搜索進程陷入死循環。文獻［12］通過大量調度實例發現：采用CSP方法求解調度問題時，絕大多數問題屬于兩類情況：一類是無回溯求解調度問題，另一類則是搜索進程頻繁出現“Thrashing”現象。

大規模JSSP具有約束松馳度緊、約束內聯度高等特征，回溯發生不可避免。因此，關注“Thrashing”、減小“Thrashing”發生概率是設計回溯搜索算法時不可回避的重要環節。在約束優化調度算法設計時，可采用一致性預處理機制和回溯前移機制來減少“Thrashing”頻發。

（1）一致性預處理機制。隨著調度進程的推進，由于已調度工序開工時間的確定，受約束優化調度模型中兩類硬約束的影響，剩余調度空間中與已調度工序相關的變量值域勢必包含潛在沖突值，而這些潛在沖突值的存在可能導致后續搜索過程發生約束沖突。因此，通過采用一致性預處理機制，依據已調度中間結果對剩余搜索空間相關變量集的值域預先實施修剪和過濾，以剔除其值域內的潛在沖突值，從而減少剩余變量值域發生約束沖突的概率。

（2）回溯前移機制。約束集在回溯搜索過程中存在“前緊后松”的特點，即在搜索初期，工序變量之間的約束松弛度較緊，而隨著調度進程的推進，在前期滿足瓶頸機床和關鍵工序變量賦值后，后期的搜索過程則呈現約束相對較松的特點。因此，采用回溯前移機制，將搜索進程發生約束沖突的時間點前移，及早暴露、識別并滿足制約整個搜索過程中的瓶頸機床和關鍵工序賦值，以避免搜索后期出現約束沖突而導致已調度中間結果發生大面積回溯。

5 約束優化調度算法設計

遵循上述的兩階段調度和動態修訂搜索空間的調度策略，結合“Thrashing”現象消減機制，在深度優先搜索算法的基礎上，設計了圖1所示的約束優化調度算法（constrained opti mization schedule al gorit h m，COSA）框架。其中，Un Sched為待調度工序集；Sched為已調度結果集；Op為各搜索狀態下的變量排序啟發結果（即關鍵工序）；St為Op的開工時間賦值。該算法的步驟如下：

（1）初始化。系統啟動后，首先初始化待調度工序集Un Sched和已調度結果集Sched，并設置時間粒度、回溯閾值等系統參數。

（2）初始化工序開工時間窗。依據前述約束傳播方法產生初始搜索狀態下各工序開工時間的值域。

（3）搜索結束判定。檢測Un Sched內有無剩余待調度工序，如果UnSched＝?，則整個搜索進程結束，算法最終求得調度解或證明調度問題無解，否則，則進入下一步。

（4）一致性預處理。遵循一致性預處理機制，采用文獻［13］提出的動態一致性增強算法，依據上次搜索狀態下的關鍵工序賦值（Op，St），結合工序路線和機床獨占性2類硬約束對剩余搜索空間實施預修剪。

（5）約束沖突檢測。檢驗上次搜索狀態下的關鍵工序賦值（Op，St）與Sched內已調度中間結果有無約束沖突，若發生沖突，則進行順序回溯處理［5］，若無沖突，則進入下一步。

（6）瓶頸機床識別。根據回溯前移機制，采用文獻［14］提出的瓶頸機床動態識別方法：首先依據上述約束優化調度模型對剩余搜索空間的工序開工時間集進行提前／拖期成本計算，再進行當前搜索空間的概率計算，即依次計算各工序開工時間的主觀概率、工序對機床的獨立需求概率、機床累計需求概率之和，最后以累計需求概率之和最大的機床作為當前搜索狀態下的瓶頸機床。

（7）單機排序優化。以步驟（6）的輸出結果瓶頸機床作為輸入參數，采用文獻［14］提出的工序變量排序和賦值優化方法，輸出當前搜索狀態下的關鍵工序開工時間取值。① 工序變量優化排序：以競爭同一瓶頸機床的所有待調度工序作為排序對象，以工序對機床的獨立需求概率值作為排序準則，在競爭高峰時段選擇獨立需求概率值最大的工序作為當前搜索狀態下的變量排序輸出結果Op。②關鍵工序賦值優化：以工序變量優化排序輸出結果Op為輸入，在Op剩余值域內選擇調度成本最小的開工時間作為關鍵工序Op的最終賦值St。

（8）將關鍵工序賦值結果（Op，St）保存進Sched，同時從Un Sched中剔除工序Op，算法進入步驟（3），繼續以上循環處理。

圖1 約束優化調度算法

6 仿真試驗

6．1 調度用例設計

隨機生成80個調度問題，通過調整拖期系數τ、交貨期分布R和瓶頸機床數量Nbtnk三個參數的不同組合產生8組調度問題（表3），每組調度問題包括10個調度子問題，每個調度子問題包含20個零件和5臺機床，各零件均包含5道工序，且根據線性工藝路線依次經過5臺機床，各工件經過機床的順序隨機產生。

表3 調度參數設置表

（1）拖期系數τ：用以調整各零件交貨期的平均松弛度。各零件的平均交貨期設定為（1－τ）M，其中，M ＝為 零件數量，Rbtnk為瓶頸機床為競爭機床Ri的所有工序的平均加工周期。

（2）交貨期分布R：用以調節不同零件交貨期的集中程度，各零件的交貨期依據（1－τ）×M×U（1－R／2，1＋R／2）隨機產生。R 值越小，表示各零件交貨期分布越集中，調度難度更大。

（3）瓶頸機床數量Nbtnk：用來調節初始狀態下調度任務集內的瓶頸機床數量。

6．2 參數設置和評價指標設計

6．2．1 加工參數設置

（1）零件批量Si依據U（1，7）等概率隨機生成。

（2）工序加工周期duli按Si×U（0．5，1．5）等概率隨機生成。

（3）零件拖期懲罰系數tar di按5U（1，2Si）等概率隨機產生。

（4）庫存成本系數invli：考慮到庫存成本與零件批量、原材料價格等因素相關，在該試驗中，將invli設置為零件批量Si，暫未考慮材料價格因素的影響。

（5）最早可接受釋放期er di和最晚可接受的完工時間lcdi：為增加調度問題的復雜度，上述8組調度子問題內所有零件均設置為相同的最早可接受釋放期er di＝0和最晚可接受完工時間lcdi＝2 M。

6．2．2 評價指標設計

選擇包括上述約束優化調度模型中的調度總成本在內的4個評價指標來評估算法性能。其中，平均加權拖期用來評測調度拖期性能好壞；平均加權流動時間用以評測零件加工過程中的在制品庫存成本；平均加權系統時間用來評測零件的成品庫存成本和在制品庫存成本。

（1）平均加權拖期成本。該評價指標是指各零件拖期成本的加權平均值，即

（2）平均加權流動時間。該評價指標是指各零件從開始加工至加工結束所需時間的加權平均值，用以評價在制品的流動庫存成本，其表達式為

（3）平均加權系統時間。該評價指標包括零件因提前完工而產生的成品庫存成本和在制品庫存成本兩部分，該指標綜合反映了各零件庫存成本和在制品庫存成本，表達式為

6．3 仿真結果分析

文獻［15］針對提前／拖期調度問題，提出了兩種有效的Tardy／Early排序規則，即線性E／T排序（LIN－ET）規則和指數E／T排序（EXP－ET）規則，并通過試驗證明這兩種排序規則在降低提前／拖期成本方面具有優勢。仿真試驗環境為：CPU為Intel 2．4GHz，內存為1．98GB；仿真軟件采用MATLAB 7．0。該試驗以上述調度用例為測試對象，將本文提出的約束優化調度算法COSA和LIN－ET、EXP－ET兩種規則進行比較。圖2～圖5分別表示COSA和LIN－ET、EXP－ET在平均調度總成本、平均加權拖期、平均加權流動時間和平均加權系統時間4個評價指標下的試驗結果。

圖2 平均調度總成本仿真結果

在仿真試驗中，COSA在總共80次試驗中，平均搜索效率（定義為待調度工序總數和求得調度解所產生的搜索狀態數的比值）為85．6%，平均計算時間為35s。說明COSA能夠有效降低“Thrashing”頻發現象，從而保證搜索算法以較高的搜素效率和較小的計算成本求得E／T調度問題的優化解。

圖3 平均加權拖期成本仿真結果

圖4 平均加權流動時間仿真結果

圖5 平均加權系統時間仿真結果

從圖2可以看出：COSA在總共8組試驗中，除第7組試驗外，其余7組試驗得到的平均調度總成本均小于LIN－ET和EXP－ET。從圖3可以看出：對于拖期成本指標而言，COSA和EXP－ET的性能基本相當，但要優于LIN－ET在拖期成本方面的表現。

從圖4、圖5可以得知：COSA在壓縮在制品庫存和成品庫存兩項指標上明顯優于LIN－ET和EXP－ET。尤其在調度環境最為苛刻的第8組試驗（瓶頸機床數量多，交貨期松弛度緊，且各零件交貨期分布較集中）中，當LIN－ET和EXP－ET的在制品庫存成本和成品庫存成本大幅攀升（達到峰值）的情況下，而COSA則維持在一個相對較低的庫存水平。

與EXP－ET規則（該方法性能優于LINET）相比較而言，在共8組仿真試驗中，COSA降低在制品流動庫存成本15%～35%，降低成品和在制品庫存總成本10%～30%，壓縮平均調度總成本8%以上。

7 結束語

本文在滿足工藝路線、機床能力和交貨期約束條件的前提下，將提前／拖期成本指標引入調度問題，從而將約束滿足求解JSSP的傳統方式轉化為約束優化求解；遵循解決實際工程問題的思維模式和原則，將復雜的調度優化問題劃分為瓶頸機床優先識別和單機排序優化兩個階段，以降低大規模JSSP的計算復雜度和提高調度方法的實用性；為了降低回溯搜索中的“Thrashing”現象發生概率，引入一致性預處理機制以事先修剪和過濾剩余搜索空間的潛在沖突源，回溯前移機制可以有效避免搜索后期出現約束沖突而導致已調度中間結果發生大面積回溯的弊端。

為綜合測試COSA算法性能，設計了一組交貨期的松弛度和集中度可組合調整、加工參數隨機產生的80個調度問題，并將COSA與在提前／拖期調度方面具有優勢的LIN－ET、EXP－ET排序規則進行比較，結果表明：COSA與EXPET在拖期成本指標方面結果相近，但在減少在制品庫存成本和成品庫存成本兩方面具有明顯優勢，從而保證了調度總成本相對較低。

［1］ Fox M S．Constraint－directed Search：A Case Study of Job－shop Scheduling［D］．Pittsbur gh：Car negie－Mellon University，1983．

［2］ Fox M S，Smith S F．ISIS－ a Knowledge－based System for Factor y Scheduling［J］．Expert Systems，1984，1（1）：25－49．

［3］ Smith S F，Peng Si Ow，Jean－Yves Porvin．OPIS：an Opportunistic Factory Scheduling System［C］／／Proceedings of the 3rd International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems．Charleston，1990：268－274．

［4］ Sadeh N，Fox M S．Variable and Value Ordering Heuristics f or t he Job Shop Scheduling Constraint Satisfaction Problem ［J］．Artificial Intelligence，1996，86（1）：1－41．

［5］ Sadeh N，Sycara K，Xiong Y．Backtracking Techniques for the Job Shop Scheduling Constraint Satisfaction Problem［J］．Artificial Intelligence，1995，76（1／2）：455－480．

［6］ Barták R，Skalicky T．A Local Approach to Automated Correction of Violated Precedence and Resource Constraints in Manually Altered Schedules［C］／／Proceedins of MISTA 2009：Fourth Multidisciplinary International Scheduling Conference：Theory and Applications．Dublin，Ireland，2009：507－517．

［7］ Barták R．Constraint Satisfaction Techniques in Planning and Scheduling：An Introduction［J］．In Archives of Control Sciences，2008，18（2）：141－158．

［8］ 郭冬芬，李鐵克．基于約束滿足的車間調度算法綜述［J］，計算機集成制造系統，2007，13（1）：117－125．

［9］ 段黎明，陳進，劉飛．基于約束分析的Job Shop調度算法的綜述［J］．重慶大學學報，1998，21（1）：133－138．

［10］ 陳恩紅，薛瀚宏．基于約束滿足的Job Shop調度問題求解方法研究［J］．軟件學報，1998，9（12）：946－948．

［11］ 上官春霞，周泓，師瑞峰，等．作業車間排序重調度問題及其改進修復約束滿足算法［J］．計算機集成制造系統，2008，14（9）：1742－1751．

［12］ Dechter R，Meiri I．Experimental Evaluation of Preprocessing Techniques in Constraint Satisfaction Problems［C］／／Proceedings of the Eleventh International Joint Conference on Artificial Intelligence．Detroit，1989：271－277．

［13］ 楊宏安，孫樹棟，司書賓．基于動態一致性增強技術的Job Shop調度算法研究［J］，西北工業大學學報，2007，25（4）：523－527．

［14］ 楊宏安．基于COP的作業車間調度問題研究［D］．西安：西北工業大學，2007．

［15］ Peng S O，Morton T．The Single Machine Early／Tardy Problem［J］．Management Science，1989，35（2）：177－191．