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

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

0 引言

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

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

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

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

1 問(wèn)題描述

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

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

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

1.2 約束描述

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

表1 約束描述表

2 約束規(guī)劃模型

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

多品種小批量冰箱發(fā)泡生產(chǎn)調(diào)度是以班次為單位調(diào)度的，并且各型號(hào)需求量波動(dòng)較大，在多維約束下通常無(wú)法將一個(gè)型號(hào)排產(chǎn)作為一個(gè)任務(wù)進(jìn)行調(diào)度，且建模困難；因此本文不使用CP Optimizer 中的區(qū)間變量構(gòu)建決策變量，而是采用常規(guī)的離散型整型變量作為決策變量，能夠更容易表達(dá)本問(wèn)題中的特定約束，更符合問(wèn)題的特點(diǎn)。本問(wèn)題具有多層決策變量且決策變量之間具有映射關(guān)系，A 策變量相應(yīng)的約束也會(huì)映射到B 決策變量上，從這個(gè)問(wèn)題特征出發(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)度以班次為時(shí)間單位進(jìn)行調(diào)度，產(chǎn)品的生產(chǎn)效率與關(guān)鍵資源箱體模具一致，箱體模具的班次產(chǎn)能由箱體模具生產(chǎn)效率與班次工時(shí)決定，為方便建模，定義產(chǎn)品或者箱體模具的排產(chǎn)計(jì)算基數(shù)，產(chǎn)品b的產(chǎn)能計(jì)算基數(shù)即為在某個(gè)班次排產(chǎn)了產(chǎn)品b的幾個(gè)班次產(chǎn)能，箱體模具x的排產(chǎn)計(jì)算基數(shù)即為某個(gè)班次排產(chǎn)了幾個(gè)模具x的班次產(chǎn)能，以此計(jì)算產(chǎn)品或者箱體模具的總班次產(chǎn)能，用式（1）表示使用排產(chǎn)計(jì)算基數(shù)計(jì)算產(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 約束表達(dá)式

函數(shù)if(Expr1)then(Expr2)作用是如果Expr1 為真，則Expr2 生效且為真。(Expr1)And(Expr2)函數(shù)表示Expr1與Expr2 同時(shí)成立。則約束（3）的含義為：任意班次如果產(chǎn)品b1與產(chǎn)品b2存在互斥約束，則如果b1大于0 時(shí)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%的富裕是工廠實(shí)際可接受的。

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

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

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

2.2.3 目標(biāo)函數(shù)

Abs(Expr)函數(shù)的作用是對(duì)Expr 取絕對(duì)值，目標(biāo)函數(shù)式（8）的計(jì)算邏輯是，從第二個(gè)班次開始，計(jì)算當(dāng)前班次v的箱體模具x的排產(chǎn)計(jì)算基數(shù)count(mmodvk=1…k,x)與上一班次的排產(chǎn)計(jì)算基數(shù)count(mmodv-1,k=1…k,x)，將兩個(gè)值相減后取絕對(duì)值，即為箱體模具x在班次v和v- 1之間的絕對(duì)差值，假如模具從x1換到x2，那么x1的減少與x2的增加是重復(fù)計(jì)算的，所以將從第一班次開始的各箱體模具的差值變化相加，再除以2，就是實(shí)際的換模次數(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ā)泡機(jī)器k上排產(chǎn)的箱體模具供應(yīng)的產(chǎn)品型號(hào)編號(hào)，其取值范圍是：0 ≤Fvk≤b；0為虛擬產(chǎn)品編號(hào)，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ò)映射關(guān)系關(guān)聯(lián)，Expri與Exprj均是單個(gè)決策變量，Arry 是一個(gè)數(shù)組，數(shù)組的索引與Exprj的取值范圍對(duì)應(yīng)，Element(Expri,Exprj,Arry)的作用是建立約束：Expri的取值等于Arry 中索引為Exprj的值；建立式（9）：

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

2.3.2 約束表達(dá)式

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

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

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

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

2.3.3 目標(biāo)函數(shù)

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

3 調(diào)度案例

本文使用IBM ILOG CPLEX Optimization Studio 12.10優(yōu)化軟件，在.Net 平臺(tái)中使用C#編程語(yǔ)言編碼，調(diào)用求解器為CP Optimizer 優(yōu)化引擎，相對(duì)最優(yōu)容差值設(shè)置為0，求解時(shí)間設(shè)置為1 800 s，其余設(shè)置按照默認(rèn)設(shè)置執(zhí)行。實(shí)驗(yàn)環(huán)境為臺(tái)式計(jì)算機(jī)，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ù)使用兩個(gè)模型進(jìn)行對(duì)比求解實(shí)驗(yàn)，所選取數(shù)據(jù)的基本特征如表4所示。

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

3.2 求解結(jié)果分析

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

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

從表5 的求解結(jié)果可以看出，模型1 與模型2 在不同的輸入數(shù)據(jù)下均存在模型1更優(yōu)或模型2更優(yōu)的情況，說(shuō)明兩個(gè)模型各有優(yōu)勢(shì)。根據(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可知，對(duì)于產(chǎn)能需求低且產(chǎn)品種類小于等于10、箱體模具種類小于10的輸入數(shù)據(jù)，基于數(shù)量約束關(guān)聯(lián)多層決策變量的CP模型有更大的概率獲得更優(yōu)的求解結(jié)果，此時(shí)應(yīng)選擇模型1；對(duì)于產(chǎn)能需求高、且產(chǎn)品種類大于10、箱體模具種類大于10的輸入數(shù)據(jù)，基于映射關(guān)系關(guān)聯(lián)多層決策變量的CP模型則有更大的概率獲得更好的求解結(jié)果，此時(shí)應(yīng)選擇模型2。這是因?yàn)椋Ｐ? 在產(chǎn)能需求、產(chǎn)品種類與模具種類較少的時(shí)候解空間割裂度低、決策變量數(shù)量較少，決策變量的取值范圍較小，相比于模型2，同一數(shù)據(jù)的求解規(guī)模較小，故更容易在相同時(shí)間內(nèi)求得更好的結(jié)果；而當(dāng)產(chǎn)能需求較大、產(chǎn)品種類與模具種類較多時(shí)，解空間割裂度明顯變高，且模型2 的決策變量數(shù)量不變，其以映射關(guān)系關(guān)聯(lián)決策模型能高效利用CP 的約束傳播優(yōu)勢(shì)，有更高的搜索效率，所以此時(shí)模型2能求得更好的結(jié)果。

4 結(jié)束語(yǔ)

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