摘 要：針對硫化車間生產(chǎn)調(diào)度過程中產(chǎn)品型號多、處理量大等難點，建立了以最小硫化時間為目標、多硫化機并行生產(chǎn)調(diào)度的混合整數(shù)線性規(guī)劃(MILP)數(shù)學模型。采用0—1變量表示不同型號輪胎生產(chǎn)順序，提出了多種約束以減少模型求解難度。為了驗證模型的有效性，對文獻中三個典型的小規(guī)模硫化調(diào)度算例求解，得到了比文獻更優(yōu)的調(diào)度方案。在此基礎之上，考慮硫化車間生產(chǎn)實際，設計了六個貼近實際的大規(guī)模調(diào)度算例，進一步考察本文所提出方法的有效性，為實際硫化車間調(diào)度優(yōu)化提供了指導。

　　關鍵詞：硫化車間調(diào)度;大規(guī)模;完工時間;MILP

　　引言(Introduction)

　　在輪胎生產(chǎn)過程中，硫化工序[1]耗時最長，其科學排產(chǎn)是提高輪胎生產(chǎn)率的關鍵。近年來，國內(nèi)外輪胎廠生產(chǎn)已經(jīng)基本實現(xiàn)了自動化，但輪胎硫化排產(chǎn)依然需要依靠調(diào)度人員的經(jīng)驗來安排，這種靠基本經(jīng)驗的人工方式很難使機器的利用率達到最大。充分利用有限的硫化機，合理排產(chǎn)，在最短的時間內(nèi)完成輪胎的生產(chǎn)，是提高企業(yè)生產(chǎn)力和競爭力的關鍵。本文以最小硫化時間為目標，對硫化車間的調(diào)度進行優(yōu)化。

　　近年來，調(diào)度優(yōu)化問題引起了廣泛的關注[2-5]：鄭必鳴等人[2]提出了一種基于混合整數(shù)線性規(guī)劃(MILP)的魯棒優(yōu)化模型，來優(yōu)化不確定條件下的生產(chǎn)調(diào)度決策;耿佳燦等[3]建立了以最小化模糊最大完工時間的值及不確定度作為調(diào)度目標的數(shù)學模型，使用基于改進粒子群和分布估計的混合算法求解該調(diào)度問題;HE等人[4]建立混合整數(shù)線性規(guī)劃模型求解并行設備的調(diào)度優(yōu)化問題;李作成等人[5]使用遺傳分布估計算法求解化工生產(chǎn)中的并行機調(diào)度問題。

　　硫化車間調(diào)度優(yōu)化問題是一種典型的調(diào)度優(yōu)化問題，近年來不少學者都對此做過研究[6-8]：張守剛等人[6]使用分布估算算法對硫化車間調(diào)度問題進行求解，結果顯示該算法可以較好地求解小規(guī)模硫化車間調(diào)度算例;吳龍成等人[7]采用改進和聲算法對該類調(diào)度問題進行求解，經(jīng)過改進的和聲優(yōu)化算法有較好的求解性能，能較快地求解小規(guī)模調(diào)度算例，并且每次運行程序得到的最優(yōu)解在小范圍內(nèi)波動;王輝等人[8]使用改進粒子群算法對該類調(diào)度問題進行求解，結果顯示該算法在求解過程中可以較好地避免過早陷入局部最優(yōu)解。上述求解方法為小規(guī)模硫化車間調(diào)度問題的求解提供了思路。由于實際硫化車間調(diào)度問題規(guī)模較大，因此本文建立包含0—1變量的混合整數(shù)線性規(guī)劃數(shù)學模型[9-10]，將生產(chǎn)順序用多組線性約束表示，使用GAMS求解相關算例，得到了較為滿意的結果。

　　2 硫化車間調(diào)度問題建模(Modeling of vulcanization workshop scheduling problem)

　　2.1 問題描述

　　輪胎廠的硫化車間共有臺硫化機，共需生產(chǎn)種規(guī)格的輪胎，訂單中每種規(guī)格輪胎的需求數(shù)為(=1，2，3，…，)。

　　每臺硫化機可以硫化訂單中所有規(guī)格的輪胎，由于各臺硫化機的硫化能力不同，其硫化不同種類輪胎的時間也不盡相同。每臺硫化機上每次僅可硫化一條輪胎，并且同一條輪胎只能在一臺硫化機上硫化。同一臺硫化機硫化不同種類的輪胎需要進行換模，換模時間取決于硫化機的性能以及輪胎模具的型號和更換順序，每臺硫化機上最初生產(chǎn)的輪胎不需要更換模具。由于硫化車間的生產(chǎn)是多臺機器同時運行，因此硫化車間的調(diào)度問題是一個多機器并行生產(chǎn)的調(diào)度問題[11-12]，如圖1所示。

　　已知每種規(guī)格輪胎的需求數(shù)量，不同硫化機上硫化不同輪胎的時間和不同硫化機上各種輪胎之間的換模時間，第臺硫化機上輪胎是否緊接著輪胎生產(chǎn)，第臺硫化機上生產(chǎn)輪胎的數(shù)量，硫化機上總硫化時間，調(diào)度優(yōu)化目標為最大完工時間最小化，可用式(1)和式(2)表示：

　　式(1)為每臺硫化機硫化時間，式(2)中為總生產(chǎn)時間，即所有硫化機中硫化時間最長的硫化機耗時。

　　2.2 約束條件

　　根據(jù)確定的調(diào)度優(yōu)化目標，結合輪胎硫化實際情況，需要考慮如下約束條件。

　　(1)輪胎生產(chǎn)種類與換模約束

　　其中，代表輪胎種類，表示硫化機，表示第臺硫化機上是否生產(chǎn)輪胎，為0—1變量。式(3)—式(5)表示輪胎換模種類與換模次數(shù)之間的關系，在同一臺硫化機上換模次數(shù)不大于硫化輪胎種類數(shù)，并且硫化輪胎種類數(shù)之和比換模次數(shù)恒少1。

　　(2)生產(chǎn)順序約束

　　在式(6)—式(9)中，為在第 臺硫化機上第一個生產(chǎn)的輪胎是否為，為在第臺硫化機上最后一個生產(chǎn)的輪胎是否為，與均為0—1變量。式(6)和式(7)表示硫化的每種輪胎最多只能有一個前相鄰生產(chǎn)輪胎和后相鄰生產(chǎn)輪胎。式(8)和式(9)表示每臺硫化機中有且僅有一種最初和最后生產(chǎn)的輪胎。

　　式(10)表示了同一臺硫化機上初始生產(chǎn)輪胎、最后生產(chǎn)輪胎和輪胎換模之間的內(nèi)在聯(lián)系。假設在第臺硫化機上的硫化順序為1—2—3—4—5，則的取值均為1。除了最初生產(chǎn)的輪胎1與最后生產(chǎn)的輪胎5，其他輪胎均出現(xiàn)了兩次(例如輪胎2在和中各出現(xiàn)了一次，和取值均為1)。約束9中引入最初生產(chǎn)輪胎和最后生產(chǎn)輪胎，使輪胎1和輪胎5共出現(xiàn)兩次(和取值為1，和取值為1)，然后建立輪胎生產(chǎn)順序約束。

　　式(11)表示如果在某臺硫化機上輪胎是緊接著輪胎生產(chǎn)的，那么輪胎的初始加工時間一定大于輪胎的完工時間。其中為輪胎在硫化機上的初始生產(chǎn)時間，B為一個足夠大的數(shù)。

　　(3)生產(chǎn)數(shù)量約束

　　在式(12)中，為訂單中需求量最大輪胎的需求數(shù)。該約束將0—1變量與整數(shù)變量通過線性不等式進行聯(lián)系，當取1時，此時取值不受該約束限制;當取0時，此時只可以取0。

　　在式(13)中，為硫化機訂單中各種輪胎所需硫化的數(shù)量，該式表示所有硫化機生產(chǎn)該種型號輪胎的總數(shù)需要滿足訂單需求。

　　3 計算結果對比與分析(Comparison and analysis of calculation results)

　　3.1 文獻算例對比

　　根據(jù)文獻[6]和文獻[7]提供的算例，實驗以最小化最大完工時間為調(diào)度的優(yōu)化目標，算例規(guī)模分別是3×4(3 臺硫化機硫化4 種型號輪胎)、4×3和7×10。下列計算結果采用本文所建立的數(shù)學模型，在GAMS平臺使用CPLEX的MIP求解器進行計算求解[13-15]，硬件配置為內(nèi)存12 GB、處理器i7-4710HQ，與相關文獻對比結果如表1所示，排產(chǎn)順序如圖2—圖4所示。

　　在圖2、圖3和圖4中，柱狀圖中的數(shù)字代表在該時間段內(nèi)硫化輪胎的型號，每一條柱狀圖下方的數(shù)字表示硫化該型號輪胎的數(shù)量，柱狀圖與柱狀圖之間的空缺代表硫化機進行了換模。

　　通過表1的結果對比可以看出，在求解同樣規(guī)模的硫化車間調(diào)度問題上，本文求解結果均好于文獻中多次使用智能優(yōu)化算法求得的最好結果。求解上述三種規(guī)模硫化車間調(diào)度問題時，求解時間均在1 s左右。

　　3.2 大規(guī)模調(diào)度優(yōu)化算例

　　為了驗證本文所提出模型求解實際硫化車間生產(chǎn)問題的有效性，共設計六個算例，不固定換模時間為200—300 min，固定換模時間為210 min。任意硫化一條輪胎的時間均是18—50 min的隨機數(shù)，每種型號的輪胎需求數(shù)量均為400—1000 條，詳情如表2、表3所示。從求解結果中不難發(fā)現(xiàn)，隨著算例規(guī)模的增大，變量數(shù)與不等式個數(shù)也隨之呈指數(shù)型增長，求解時間也隨之增長，但是即使求解100×100的大規(guī)模硫化調(diào)度問題，求解時間也僅在20 min內(nèi)。表2與表3中最大完工時差為每個算例的調(diào)度方案下耗時最長硫化機臺與耗時最短硫化機臺的完工時差，從中不難發(fā)現(xiàn)，相較于總完工時間，最大完工時差均在0.03%以內(nèi)，說明硫化機都得到了合理的安排。

　　4 結論(Conclusion)

　　本文根據(jù)硫化車間的調(diào)度問題，以最小硫化時間為目標，使用13 個約束組，并添加了啟發(fā)式約束，建立了MILP數(shù)學模型。為了驗證模型的準確性，使用該模型在GAMS平臺上求解相關典型文獻算例，每個典型算例求解時間在1 s左右，得到的調(diào)度方案相較于相關文獻均較為滿意。且為了進一步驗證該模型的有效性，本文設計了六個大規(guī)模調(diào)度算例，并使用該數(shù)學模型進行求解，求解結果均顯示硫化機利用率較高，為實際硫化車間的排產(chǎn)提供了一定的指導。

　　參考文獻(References)

　　[1] 劉明舉.硫化車間的系統(tǒng)化管理[J].輪胎工業(yè)，2017，37(10)：625-629.

　　[2] 鄭必鳴，史彬，鄢烈祥.多因素不確定條件下的間歇生產(chǎn)調(diào)度優(yōu)化[J].化工學報，2020，71(03)：1246-1253.