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

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

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

中圖分類號：TP319.9? ? ?文獻標(biāo)識碼：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）

在輪胎生產(chǎn)過程中，硫化工序[1]耗時最長，其科學(xué)排產(chǎn)是提高輪胎生產(chǎn)率的關(guā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)力和競爭力的關(guān)鍵。本文以最小硫化時間為目標(biāo)，對硫化車間的調(diào)度進行優(yōu)化。

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

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

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)化目標(biāo)為最大完工時間最小化，可用式（1）和式（2）表示：

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

2.2? ?約束條件

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

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

其中，代表輪胎種類，表示硫化機，表示第臺硫化機上是否生產(chǎn)輪胎，為0—1變量。式（3）—式（5）表示輪胎換模種類與換模次數(shù)之間的關(guān)系，在同一臺硫化機上換模次數(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)系。假設(shè)在第臺硫化機上的硫化順序為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)系，當(dāng)取1時，此時取值不受該約束限制;當(dāng)取0時，此時只可以取0。

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

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

3.1? ?文獻算例對比

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

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

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

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

為了驗證本文所提出模型求解實際硫化車間生產(chǎn)問題的有效性，共設(shè)計六個算例，不固定換模時間為200—300 min，固定換模時間為210 min。任意硫化一條輪胎的時間均是18—50 min的隨機數(shù)，每種型號的輪胎需求數(shù)量均為400—1000 條，詳情如表2、表3所示。從求解結(jié)果中不難發(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? ?結(jié)論（Conclusion）

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

參考文獻（References）

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

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

[3] 耿佳燦，顧幸生.不確定條件下中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度[J].化工學(xué)報，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] 李作成，錢斌，胡蓉，等.遺傳-分布估計算法求解化工生產(chǎn)中一類帶多工序的異構(gòu)并行機調(diào)度問題[J].化工學(xué)報，2014，65（03）：981-992.

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

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

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

[9] 潘明，錢宇，李秀喜.一種改進的順序型多目的間歇工廠生產(chǎn)調(diào)度的MILP模型[J].化工學(xué)報，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] 史彬，鄢烈祥.有并行設(shè)備的多目的間歇生產(chǎn)調(diào)度[J].化工學(xué)報，2010，61（11）：2875-2880.

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

[13] 閆獻國.GAMS——求解數(shù)學(xué)規(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-），女，本科生.研究領(lǐng)域：化學(xué)工程與工藝.

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

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

葉佳林（1998-），男，本科生.研究領(lǐng)域：化學(xué)工程與工藝.

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