摘 要：針對(duì)硫化車(chē)間生產(chǎn)調(diào)度過(guò)程中產(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)證模型的有效性，對(duì)文獻(xiàn)中三個(gè)典型的小規(guī)模硫化調(diào)度算例求解，得到了比文獻(xiàn)更優(yōu)的調(diào)度方案。在此基礎(chǔ)之上，考慮硫化車(chē)間生產(chǎn)實(shí)際，設(shè)計(jì)了六個(gè)貼近實(shí)際的大規(guī)模調(diào)度算例，進(jìn)一步考察本文所提出方法的有效性，為實(shí)際硫化車(chē)間調(diào)度優(yōu)化提供了指導(dǎo)。

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

　　引言(Introduction)

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

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

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

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

　　2.1 問(wèn)題描述

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

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

　　2.2 約束條件

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

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

　　其中，代表輪胎種類(lèi)，表示硫化機(jī)，表示第臺(tái)硫化機(jī)上是否生產(chǎn)輪胎，為0—1變量。式(3)—式(5)表示輪胎換模種類(lèi)與換模次數(shù)之間的關(guān)系，在同一臺(tái)硫化機(jī)上換模次數(shù)不大于硫化輪胎種類(lèi)數(shù)，并且硫化輪胎種類(lèi)數(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ù)變量通過(guò)線性不等式進(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é)果對(duì)比與分析(Comparison and analysis of calculation results)

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

　　根據(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)對(duì)比結(jié)果如表1所示，排產(chǎn)順序如圖2—圖4所示。

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

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

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

　　為了驗(yàn)證本文所提出模型求解實(shí)際硫化車(chē)間生產(chǎn)問(wè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ù)型增長(zhǎng)，求解時(shí)間也隨之增長(zhǎng)，但是即使求解100×100的大規(guī)模硫化調(diào)度問(wèn)題，求解時(shí)間也僅在20 min內(nèi)。表2與表3中最大完工時(shí)差為每個(gè)算例的調(diào)度方案下耗時(shí)最長(zhǎng)硫化機(jī)臺(tái)與耗時(shí)最短硫化機(jī)臺(tái)的完工時(shí)差，從中不難發(fā)現(xiàn)，相較于總完工時(shí)間，最大完工時(shí)差均在0.03%以內(nèi)，說(shuō)明硫化機(jī)都得到了合理的安排。

　　4 結(jié)論(Conclusion)

　　本文根據(jù)硫化車(chē)間的調(diào)度問(wèn)題，以最小硫化時(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ē)間的排產(chǎn)提供了一定的指導(dǎo)。

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

　　[1] 劉明舉.硫化車(chē)間的系統(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.