基于約束規劃的資源受限并行機調度研究

陳偉嘉，劉建軍，鐘宏揚,2，曾創鋒

（1.廣東工業大學機電工程學院，廣州 510006；2.佛山職業技術學院，廣東 佛山 528137）

0 引言

并行機調度（Parallel Machine Scheduling，PMS）是指作為稀缺資源的若干臺并行機器加工一組給定的不同工件，要求確定每一臺機器所加工的工件序列，其已被證明是NP-hard 問題[1]。然而，傳統的PMS 研究都假設機器是唯一受到限制的資源，但在現實制造系統中，除機器以外的機器操作員、工具、模具等副資源總是受到限制的[2]。為了更符合制造系統的現實場景，已有學者考慮將副資源數量受限這一特征納入到PMS 中，即資源受限并行機調度（Resource-Constrained Parallel Machine Scheduling，RCPMS）。由于需要在傳統PMS 問題的基礎之上，同時考慮副資源層面的限制，RCPMS 問題的求解難度更大，顯然是一個NP問題。RCPMS問題廣泛存在于注塑[3]與發泡成型、刀具調度[4]、半導體制造等眾多行業，因此，對其進行研究具有較高的學術意義與應用價值。

近年來開始有學者針對RCPMS 問題展開了研究，RCPMS 問題實質在于需要同時將并行機器和有限副資源以最優成組形式分配給任務進行生產，是經典PMS 問題的現實化擴展。從問題特征上來看，當前可將RCPMS問題分為經典RCPMS 問題與拓展RCPMS 問題。綜合現有經典RCPMS研究來看，它們基本都以最大完工時間為優化目標，如文獻[5]和文獻[6]，少數以交貨期相關的指標為優化目標的研究[7]。近年來，為了更加真實地模擬現實制造系統，部分學者開始研究經典RCPMS 的擴展問題。文獻[8]研究了一類按訂單生產RCPMS中訂單接收和調度問題。文獻[9]則是研究了以最大完工時間最小化為目標的帶有預防性維修（PM）的RCPMS 問題。文獻[10]研究了一類來源于塑料注射系統的帶批量決策RCPMS問題。文獻[4]則針對帶批量決策的刀具資源受限RCPMS問題進行了研究。此外，考慮能耗相關的RCPMS綠色調度問題近年來也吸引了一些學者的注意。文獻[11]研究了瓶頸工序光刻過程中考慮能源消耗的RCPMS問題。文獻[12]則研究了考慮綠色制造需求的RCPMS優化問題。

從求解方法來看，按照能否獲得最優解可將RCPMS問題求解算法分為啟發式方法、數學規劃方法兩類。當前，大多數RCPMS問題都是通過啟發式方法來進行求解的。啟發式方法包括問題特定啟發式算法和元啟發式算法兩類。問題特定啟發式算法可以在相對較小的時間成本下尋找到接近最優解的可行解，通過構造不同的啟發式算法可以解決各類不同的實際問題[13]。然而，啟發式算法只能生成有限的不同解，或者容易終止于較差的局部最優上，而且通常只針對特定問題才有效，不同問題則往往需要重新構造啟發式算法。近年來，以獲得近似最優解為目標的元啟發式算法開始應用于RCPMS 問題中。如迭代貪婪算法[14]，遺傳算法[2]和禁忌搜索算法[15]等。此外，也有學者通過將群體進化算法與定制的局部搜索程序混合來加強算法的搜索性能[16]。在實際生產中，往往需要依據決策者的偏好或企業不同時期的生產特點，同時在多個目標之間進行折衷平衡，因此，多目標進化算法也得到了重視[11]。此外，也有使用數學規劃方法對RCPMS 問題研究，數學規劃方法如整數線性規劃[17]將問題表示和解決策略分開，因此一般可通過許多不同的求解器求解。然而，在大規模工業調度問題上使用MIP 方法進行求解往往在求解效率方面難以滿足現實需要。

本研究針對家電企業冰箱發泡車間的生產調度問題，其本質上可抽象為一類具有多層決策變量、多維約束的大規模RCPMS問題。前述研究大多數采用啟發式方法求解RCPMS問題，但是在面對如多品種小批量冰箱發泡生產調度這類帶復雜約束RCPMS問題時存在建模困難、實現難度高的缺點。約束規劃（Constraint Program，CP）[18]方法融合了計算機科學、人工智能、運籌學等技術[19]，在求解約束滿足問題（Constraint Satisfaction Problem，CSP） 或約束優化問題（Constraint Optimization Problem，COP）時，可系統地采用演繹推理來減少搜索空間，并具備強大高效的復雜邏輯約束表達能力，已被廣泛應用于求解焊接車間調度[20]、岸橋調度[19]、資源受限項目調度等組合優化問題。使用CP 方法求解RCPMS問題也已經成為當前的研究熱點[21]，而目前國內尚無應用CP 求解RCPMS 問題的相關研究，本文將針對多品種小批量冰箱發泡生產調度問題的特點，基于CP表達復雜邏輯約束的優勢，提出兩種CP模型求解此問題，并通過實驗對比兩種模型在不同規模和調度場景下的優劣。

1 問題描述

1.1 多品種小批量冰箱發泡生產調度問題背景

冰箱產品由一個箱體與多個相同或不同型號、數量的門體組成，冰箱的生產分為5 個部分：箱體預裝配、箱體發泡、門體預裝配、門體發泡、總體裝配。箱體發泡是指使用箱體發泡機器與箱體模具完成箱體保溫層的制造，箱體發泡機器為箱體模具的通用設備，箱體產品型號與箱體模具型號一一對應，門體與箱體同理。同一種箱體或門體均可能用于裝配一種或以上的產品。總裝配工序是指將箱體產品與門體產品組裝成冰箱成品。多品種小批量冰箱發泡生產調度時間長度為一個月，按照班次進行調度，將月度訂單按照產品匯總，需要求解出：（1）每一個班次各型號產品的排產數量；（2）同一箱體發泡生產線的發泡機器在線體內劃分為2個區域，箱體模具作為關鍵資源，在區域層面與線體層面均存在約束，需要精確求解到各班次的各區域的各發泡機器安排哪一個型號的箱體模具發泡；門體發泡過程僅考慮資源數量約束。

因此，多品種小批量冰箱發泡生產調度問題可描述為：有n種確定需求量的產品需要在k個班次內排產完成，需要使用x種有限的箱體模具與y種有限的門體模具資源，各產品的生產效率與其使用的箱體模具一致；箱體模具在有限的M臺相同機器上加工，門體模具在無限的P臺相同機器上加工；箱體與門體模具均以班次為單位進行排產，箱體與門體模具的排產共同組成各型號產品的排產；某發泡機器上相鄰班次之間排產的箱體模具型號若發生變化，即為換模，換模需要占用較長的生產時間，是影響產能的主要原因，在滿足約束的前提下減少換模，是本問題的優化目標，因為實際換模時間設計的因素較多（人工經驗、運輸距離），所以用換模次數來表示換模對生產時間的影響。由問題描述可知，本問題需要兩組決策變量，且兩組決策變量存在數量或者映射關系，決策變量具有多層次的特性。

1.2 約束描述

相關約束描述及意義如表1所示。由表1可知，各約束屬于不同生產階段，約束對于問題的求解存在不同維度的影響，凸顯了多維約束復雜性。

表1 約束描述表

2 約束規劃模型

本文所構建的CP 模型使用了IBM ILOG CPLEX Optimization Studio 12.10 中的CP Optimizer 優化引擎，在.Net平臺使用C#編程語言實現；CP模型的表達比MIP模型更靈活，基于特定優化引擎的函數庫，可以更簡潔明了地表達復雜的邏輯型約束；本文將使用CP Optimizer 優化引擎中的函數作為建模語言，這些建模語言的含義都是自明的，在描述約束時也會對建模語言加以解釋。

多品種小批量冰箱發泡生產調度是以班次為單位調度的，并且各型號需求量波動較大，在多維約束下通常無法將一個型號排產作為一個任務進行調度，且建模困難；因此本文不使用CP Optimizer 中的區間變量構建決策變量，而是采用常規的離散型整型變量作為決策變量，能夠更容易表達本問題中的特定約束，更符合問題的特點。本問題具有多層決策變量且決策變量之間具有映射關系，A 策變量相應的約束也會映射到B 決策變量上，從這個問題特征出發，本文構建了基于映射關系關聯決策多層變量與基于數量約束關聯多層決策變量的CP 模型，具體模型如下。

2.1 模型參數

模型基礎參數如表2 所示。生產調度以班次為時間單位進行調度，產品的生產效率與關鍵資源箱體模具一致，箱體模具的班次產能由箱體模具生產效率與班次工時決定，為方便建模，定義產品或者箱體模具的排產計算基數，產品b的產能計算基數即為在某個班次排產了產品b的幾個班次產能，箱體模具x的排產計算基數即為某個班次排產了幾個模具x的班次產能，以此計算產品或者箱體模具的總班次產能，用式（1）表示使用排產計算基數計算產品或箱體模具的總班次產能：

表2 模型基礎參數表

約束參數如表3所示。

表3 模型約束參數表

2.2 模型1：基于數量約束關聯多層決策變量的CP模型

2.2.1 決策變量

2.2.2 約束表達式

函數if(Expr1)then(Expr2)作用是如果Expr1 為真，則Expr2 生效且為真。(Expr1)And(Expr2)函數表示Expr1與Expr2 同時成立。則約束（3）的含義為：任意班次如果產品b1與產品b2存在互斥約束，則如果b1大于0 時b2必等于0，如果b2大于0 則b1必等于0，即產品b1與產品b2不允許同班次排產。

約束（4）表示，產品b的所有班次排產量總和大于等于其需求量，且小于等于需求量的110%，10%的富裕排產空間是為了讓整數決策變量可以取整，且10%的富裕是工廠實際可接受的。

約束（5）表示，任意班次任一種產品其排產產能不可超過其所需的門體模具資源的班次生產能力。

countdifferent(Expr)函數的作用是，計算Expr中取到不同值的決策變量的數量；所以約束（6）表示，任意班次中，區域q內排產的箱體模具種類數量小于等于其區域種類數量上限值。

約束（7）表示，任意班次內箱體發泡線所有發泡機器排產的箱體模具種類數量小于等于全線體種類數量上限值。

2.2.3 目標函數

Abs(Expr)函數的作用是對Expr 取絕對值，目標函數式（8）的計算邏輯是，從第二個班次開始，計算當前班次v的箱體模具x的排產計算基數count(mmodvk=1…k,x)與上一班次的排產計算基數count(mmodv-1,k=1…k,x)，將兩個值相減后取絕對值，即為箱體模具x在班次v和v- 1之間的絕對差值，假如模具從x1換到x2，那么x1的減少與x2的增加是重復計算的，所以將從第一班次開始的各箱體模具的差值變化相加，再除以2，就是實際的換模次數。

2.3 模型2：基于映射關系關聯多層決策變量的CP模型

基于映射關系與基于數量約束關聯多層決策變量的CP 模型的主要區別是產品排產基數決策變量的形式不同，以及產品排產決策變量與箱體模具排產決策變量的關聯方式不一樣。

2.3.1 決策變量

本模型一共定義了2組整數類型決策變量：（1）Fvk，為產品排產基數決策變量，表示班次v發泡機器k上排產的箱體模具供應的產品型號編號，其取值范圍是：0 ≤Fvk≤b；0為虛擬產品編號，Fvk取到0即為不排產任何產品。（2）箱體模具排產決策變量與基于數量約束關聯多層決策變量的CP 模型一致，為mmodvk，其具體含義見上文。本模型中Fvk與mmodvk使用CP Optimizer優化引擎中的Element(Expri,Exprj,Arry)函數通過映射關系關聯，Expri與Exprj均是單個決策變量，Arry 是一個數組，數組的索引與Exprj的取值范圍對應，Element(Expri,Exprj,Arry)的作用是建立約束：Expri的取值等于Arry 中索引為Exprj的值；建立式（9）：

式（9）建立約束，對于任意的班次v中的發泡機器k，決策變量mmodvk的取值等于Ab中索引為Fvk的值，表達了mmodvk與Fvk之間的映射約束關系。

2.3.2 約束表達式

約束（10）與約束（3）含義一致。

約束（11）與約束（4）含義一致。

約束（12）與約束（5）含義一致。

因為本模型與模型1 的箱體模具排產決策變量一致，故有關mmodvk的約束也與模型1一致，不再重復描述。

2.3.3 目標函數

目標函數與模型1一致，此處不再重復。

3 調度案例

本文使用IBM ILOG CPLEX Optimization Studio 12.10優化軟件，在.Net 平臺中使用C#編程語言編碼，調用求解器為CP Optimizer 優化引擎，相對最優容差值設置為0，求解時間設置為1 800 s，其余設置按照默認設置執行。實驗環境為臺式計算機，CPU 為12th Gen Intel（R） Core （TM） i5-12490F 3.00 GHz，32GB 內存，Windows 10操作系統。

3.1 數據描述

選取某工廠的13 份歷史訂單數據使用兩個模型進行對比求解實驗，所選取數據的基本特征如表4所示。

表4 實驗數據基礎特征表

3.2 求解結果分析

表5是兩個模型在同一參數設置下的求解結果。

表5 模型求解結果

從表5 的求解結果可以看出，模型1 與模型2 在不同的輸入數據下均存在模型1更優或模型2更優的情況，說明兩個模型各有優勢。根據表5 的求解結果，結合輸入數據的基本特征，整理出模型1更優的數據及其求解結果如表6所示，模型2更優的數據及求解結果如表7所示。

表6 模型1更優結果表

表7 模型2更優結果表

由表6和表7可知，對于產能需求低且產品種類小于等于10、箱體模具種類小于10的輸入數據，基于數量約束關聯多層決策變量的CP模型有更大的概率獲得更優的求解結果，此時應選擇模型1；對于產能需求高、且產品種類大于10、箱體模具種類大于10的輸入數據，基于映射關系關聯多層決策變量的CP模型則有更大的概率獲得更好的求解結果，此時應選擇模型2。這是因為，模型1 在產能需求、產品種類與模具種類較少的時候解空間割裂度低、決策變量數量較少，決策變量的取值范圍較小，相比于模型2，同一數據的求解規模較小，故更容易在相同時間內求得更好的結果；而當產能需求較大、產品種類與模具種類較多時，解空間割裂度明顯變高，且模型2 的決策變量數量不變，其以映射關系關聯決策模型能高效利用CP 的約束傳播優勢，有更高的搜索效率，所以此時模型2能求得更好的結果。

4 結束語

本研究對RCPMS問題進行了描述，將約束規劃技術應用于求解一類具有多維約束的RCPMS問題，并結合實際制造系統中的調度場景，選擇多品種小批量冰箱發泡生產調度作為典型案例；根據此問題的特點，結合IBM ILOG Cplex Optimization Studio 12.10 中的CP Optimizer優化引擎的高效邏輯約束表達函數，建立了兩種CP模型。通過實驗求解，并對比了兩種模型求解結果的優劣，發現在產能需求較低且產品種類小于等于10、箱體模具種類小于10時模型1的求解結果更好，在產能需求較高、且產品種類大于10、箱體模具種類大于10 時模型2 的求解結果更好，驗證了CP求解RCPMS問題的可行性與CP模型的有效性。