基于約束規(guī)劃的資源受限并行機調(diào)度研究

陳偉嘉，劉建軍，鐘宏揚,2，曾創(chuàng)鋒

（1.廣東工業(yè)大學(xué)機電工程學(xué)院，廣州 510006；2.佛山職業(yè)技術(shù)學(xué)院，廣東 佛山 528137）

0 引言

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

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

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

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

1 問題描述

1.1 多品種小批量冰箱發(fā)泡生產(chǎn)調(diào)度問題背景

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

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

1.2 約束描述

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

表1 約束描述表

2 約束規(guī)劃模型

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

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

2.1 模型參數(shù)

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

表2 模型基礎(chǔ)參數(shù)表

約束參數(shù)如表3所示。

表3 模型約束參數(shù)表

2.2 模型1：基于數(shù)量約束關(guān)聯(lián)多層決策變量的CP模型

2.2.1 決策變量

2.2.2 約束表達式

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

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

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

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

約束（7）表示，任意班次內(nèi)箱體發(fā)泡線所有發(fā)泡機器排產(chǎn)的箱體模具種類數(shù)量小于等于全線體種類數(shù)量上限值。

2.2.3 目標函數(shù)

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

2.3 模型2：基于映射關(guān)系關(guān)聯(lián)多層決策變量的CP模型

基于映射關(guān)系與基于數(shù)量約束關(guān)聯(lián)多層決策變量的CP 模型的主要區(qū)別是產(chǎn)品排產(chǎn)基數(shù)決策變量的形式不同，以及產(chǎn)品排產(chǎn)決策變量與箱體模具排產(chǎn)決策變量的關(guān)聯(lián)方式不一樣。

2.3.1 決策變量

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

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

2.3.2 約束表達式

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

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

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

因為本模型與模型1 的箱體模具排產(chǎn)決策變量一致，故有關(guān)mmodvk的約束也與模型1一致，不再重復(fù)描述。

2.3.3 目標函數(shù)

目標函數(shù)與模型1一致，此處不再重復(fù)。

3 調(diào)度案例

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

3.1 數(shù)據(jù)描述

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

表4 實驗數(shù)據(jù)基礎(chǔ)特征表

3.2 求解結(jié)果分析

表5是兩個模型在同一參數(shù)設(shè)置下的求解結(jié)果。

表5 模型求解結(jié)果

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

表6 模型1更優(yōu)結(jié)果表

表7 模型2更優(yōu)結(jié)果表

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

4 結(jié)束語

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