章佳媛 張干 梁心語 葉佳林 史彬

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

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

中圖分類號：TP319.9? ? ?文獻標識碼：A

文章編號：2096-1472（2022）-01-18-04

Abstract： Aiming at the difficulties in the production scheduling process of the vulcanization workshop， such as multiple product models and large processing capacity， this paper proposes to establish a mixed integer linear programming （MILP） mathematical model for the parallel production scheduling of poly-vulcanizers with the minimum vulcanization time as the goal. Variables from 0 to 1 are used to represent the production sequence of different types of tires; a variety of constraints are proposed to reduce the difficulty of model solving. In order to verify the effectiveness of the model， three typical small-scale vulcanization scheduling examples in the literature are solved， and a better scheduling scheme than the literature is obtained. On this basis， taking the actual production of the vulcanization workshop into consideration， six large-scale scheduling examples close to reality are designed to further examine the effectiveness of the method proposed in this paper. The proposed method provides guidance for the optimization of actual vulcanization workshop scheduling.

Keywords： vulcanization workshop scheduling; large-scale; completion time; MILP

1? ?引言（Introduction）

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

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

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

2? 硫化車間調度問題建模（Modeling of vulcanization workshop scheduling problem）

2.1? ?問題描述

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

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

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

式（1）為每臺硫化機硫化時間，式（2）中為總生產時間，即所有硫化機中硫化時間最長的硫化機耗時。

2.2? ?約束條件

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

（1）輪胎生產種類與換模約束

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

（2）生產順序約束

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

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

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

（3）生產數(shù)量約束

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

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

3? 計算結果對比與分析（Comparison and analysis of calculation results）

3.1? ?文獻算例對比

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

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

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

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

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

4? ?結論（Conclusion）

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

參考文獻（References）

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

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

[3] 耿佳燦，顧幸生.不確定條件下中間存儲時間有限多產品間歇生產過程調度[J].化工學報，2015，66（01）：357-365.

[4] HE Y H， LIANG Y Z， LIU Z M， et al. Improved exact and meta-heuristic methods for minimizing makespan of large-size SMSP[J]. Chemical Engineering Science， 2017， 158：356-359.

[5] 李作成，錢斌，胡蓉，等.遺傳-分布估計算法求解化工生產中一類帶多工序的異構并行機調度問題[J].化工學報，2014，65（03）：981-992.

[6] 張守剛，吳龍成，王艷，等.基于分布估計算法的硫化車間調度[J].系統(tǒng)仿真學報，2017，29（09）：2182-2188，2197.

[7] 吳龍成，黃松，王艷，等.改進和聲搜索算法在硫化車間調度中的應用[J].系統(tǒng)仿真學報，2017，29（03）：630-638.

[8] 王輝，張亞妮.基于多種群協(xié)同進化的改進粒子群算法在輪胎硫化車間調度中的應用[J].橡膠工業(yè)，2010，57（06）：354-358.

[9] 潘明，錢宇，李秀喜.一種改進的順序型多目的間歇工廠生產調度的MILP模型[J].化工學報，2006，57（04）：861-866.

[10] CHEN X Y， REINELT G， DAI G M， et al. A mixed integer linear programming model for multi-satellite scheduling[J]. European Journal of Operational Research， 2018， 275（2）：694-707.

[11] 史彬，鄢烈祥.有并行設備的多目的間歇生產調度[J].化工學報，2010，61（11）：2875-2880.

[12] 史彬.流程工業(yè)間歇生產調度中并行列隊競爭算法的應用研究[D].武漢：武漢理工大學，2010.

[13] 閆獻國.GAMS——求解數(shù)學規(guī)劃的強大軟件[J].計算機世界，1995（11）：91-92.

[14] SELLE B， KNORR K H， LISGHEID G. Mobilisation and transport of dissolved organic carbon and iron in peat catchments-insights from the lehstenbach stream in Germany using generalised additive models[J]. Hydrological Processes， 2019， 33（25）：3213-3225.

[15] JAIN R， KINGSLY I， CHAND R， et al. Methodology for region level optimum crop plan[J]. International Journal of Information Technology， 2019， 11（4）：619-624.

作者簡介：

章佳媛（2000-），女，本科生.研究領域：化學工程與工藝.

張? ?干（1996-），男，碩士生.研究領域：過程系統(tǒng)工程.

梁心語（2000-），女，本科生.研究領域：工業(yè)工程.

葉佳林（1998-），男，本科生.研究領域：化學工程與工藝.

史? 彬（1982-），男，博士，副教授.研究領域：過程系統(tǒng)工程.本文通訊作者.