大規(guī)模硫化車間調(diào)度問題研究

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

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

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

中圖分類號(hào)：TP319.9? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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]耗時(shí)最長，其科學(xué)排產(chǎn)是提高輪胎生產(chǎn)率的關(guān)鍵。近年來，國內(nèi)外輪胎廠生產(chǎn)已經(jīng)基本實(shí)現(xiàn)了自動(dòng)化，但輪胎硫化排產(chǎn)依然需要依靠調(diào)度人員的經(jīng)驗(yàn)來安排，這種靠基本經(jīng)驗(yàn)的人工方式很難使機(jī)器的利用率達(dá)到最大。充分利用有限的硫化機(jī)，合理排產(chǎn)，在最短的時(shí)間內(nèi)完成輪胎的生產(chǎn)，是提高企業(yè)生產(chǎn)力和競爭力的關(guān)鍵。本文以最小硫化時(shí)間為目標(biāo)，對硫化車間的調(diào)度進(jìn)行優(yōu)化。

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

硫化車間調(diào)度優(yōu)化問題是一種典型的調(diào)度優(yōu)化問題，近年來不少學(xué)者都對此做過研究[6-8]：張守剛等人[6]使用分布估算算法對硫化車間調(diào)度問題進(jìn)行求解，結(jié)果顯示該算法可以較好地求解小規(guī)模硫化車間調(diào)度算例;吳龍成等人[7]采用改進(jìn)和聲算法對該類調(diào)度問題進(jìn)行求解，經(jīng)過改進(jìn)的和聲優(yōu)化算法有較好的求解性能，能較快地求解小規(guī)模調(diào)度算例，并且每次運(yùn)行程序得到的最優(yōu)解在小范圍內(nèi)波動(dòng);王輝等人[8]使用改進(jìn)粒子群算法對該類調(diào)度問題進(jìn)行求解，結(jié)果顯示該算法在求解過程中可以較好地避免過早陷入局部最優(yōu)解。上述求解方法為小規(guī)模硫化車間調(diào)度問題的求解提供了思路。由于實(shí)際硫化車間調(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? ?問題描述

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

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

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

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

2.2? ?約束條件

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

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

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

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

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

式（10）表示了同一臺(tái)硫化機(jī)上初始生產(chǎn)輪胎、最后生產(chǎn)輪胎和輪胎換模之間的內(nèi)在聯(lián)系。假設(shè)在第臺(tái)硫化機(jī)上的硫化順序?yàn)?—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）表示如果在某臺(tái)硫化機(jī)上輪胎是緊接著輪胎生產(chǎn)的，那么輪胎的初始加工時(shí)間一定大于輪胎的完工時(shí)間。其中為輪胎在硫化機(jī)上的初始生產(chǎn)時(shí)間，B為一個(gè)足夠大的數(shù)。

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

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

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

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

3.1? ?文獻(xiàn)算例對比

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

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

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

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

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

4? ?結(jié)論（Conclusion）

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

參考文獻(xiàn)（References）

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

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

[3] 耿佳燦，顧幸生.不確定條件下中間存儲(chǔ)時(shí)間有限多產(chǎn)品間歇生產(chǎn)過程調(diào)度[J].化工學(xué)報(bào)，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ì)算法求解化工生產(chǎn)中一類帶多工序的異構(gòu)并行機(jī)調(diào)度問題[J].化工學(xué)報(bào)，2014，65（03）：981-992.

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

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

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

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

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

[13] 閆獻(xiàn)國.GAMS——求解數(shù)學(xué)規(guī)劃的強(qiáng)大軟件[J].計(jì)算機(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)工程.本文通訊作者.