雷兆明，佟靜翠 ，花季偉，郭子超

（1.河北工業(yè)大學(xué) 控制科學(xué)與工程學(xué)院，天津 300130；2.天津師范大學(xué) 計算機(jī)與信息工程學(xué)院，天津 300387）

企業(yè)的生產(chǎn)管理系統(tǒng)越來越受到企業(yè)的廣泛關(guān)注，而合理的生產(chǎn)調(diào)度系統(tǒng)是保證企業(yè)長期規(guī)劃順利、順暢實施的關(guān)鍵所在[1]。因鋼結(jié)構(gòu)產(chǎn)品的很多優(yōu)點而在各方面得到廣泛使用，從而帶動鋼構(gòu)企業(yè)迅速發(fā)展。如何提高企業(yè)生產(chǎn)效率、減少勞力和機(jī)械損耗已成為現(xiàn)代鋼構(gòu)企業(yè)追尋的目標(biāo)。

Job-Shop調(diào)度是一種復(fù)雜的組合優(yōu)化問題和典型的NP難題[2]。文獻(xiàn)[3-4]等都提出過關(guān)于柔性Job-Shop調(diào)度問題的求解方法。本文結(jié)合鋼結(jié)構(gòu)的實際生產(chǎn)特點與約束條件，在生產(chǎn)計劃調(diào)度系統(tǒng)中建立了多目標(biāo)生產(chǎn)數(shù)學(xué)模型，用基于蟻群遺傳混合算法進(jìn)行求解，并通過方案對比得出了該生產(chǎn)調(diào)度系統(tǒng)的高效性、可執(zhí)行性。

1 系統(tǒng)功能設(shè)計

對鋼構(gòu)企業(yè)而言，如何面向多品種小批量的大量訂貨合同而組織生產(chǎn)是生產(chǎn)管理系統(tǒng)面臨的最大困難。因為生產(chǎn)計劃指導(dǎo)著關(guān)鍵生產(chǎn)環(huán)節(jié)的進(jìn)行，它必須考慮到生產(chǎn)過程中的實際因素，如不同鋼種、規(guī)格和交貨期需求，多班組工序分配等。

生產(chǎn)調(diào)度是將生產(chǎn)基于訂單合同的生產(chǎn)順序計劃解析成為設(shè)備、原料等生產(chǎn)資源的分配依據(jù)，以客戶需求為目標(biāo)，結(jié)合企業(yè)產(chǎn)能和工藝流程約束，對企業(yè)的生產(chǎn)資源進(jìn)行調(diào)度分配，以節(jié)約生產(chǎn)時間、提高企業(yè)利潤為目標(biāo)，指導(dǎo)生產(chǎn)活動有序進(jìn)行[5]。生產(chǎn)計劃與調(diào)度在生產(chǎn)系統(tǒng)中的位置關(guān)系及信息流動如圖1所示。

2 關(guān)鍵算法

鋼構(gòu)企業(yè)的工序多班組選擇調(diào)度問題屬于柔性作業(yè)車間調(diào)度問題。針對該問題，本文提出了通過蟻群遺傳混合算法來實現(xiàn)生產(chǎn)調(diào)度的優(yōu)化選擇，最終使企業(yè)生產(chǎn)系統(tǒng)相關(guān)性能指標(biāo)最優(yōu)，如總完工時間、生產(chǎn)能力與負(fù)荷均衡。

2.1 問題描述與建模

工序多班組選擇調(diào)度問題可描述為N個工件在M個班組上加工，每個工件至少含一道工序，預(yù)先給出工件工序的加工順序，每道工序可由至少一個班組加工，且同一道工序在不同班組上加工工時不同，該作業(yè)調(diào)度的目標(biāo)是為工件的每道工序確定合適的班組，完成所有工序的先后加工時間，使各班組的生產(chǎn)能力與負(fù)荷均衡，使生產(chǎn)系統(tǒng)完成總?cè)蝿?wù)的時間最短。

根據(jù)調(diào)度模型需對生產(chǎn)過程做如下假設(shè)：

1）工序一旦開始就不能中斷；

2）大型公共設(shè)備運(yùn)輸工序的時間考慮在加工時間范圍內(nèi)；

3）同一種工件的工序間加工優(yōu)先級不同，不同工件間的工序加工順序優(yōu)先級相同；

4）工序在班組上的加工時間是預(yù)先給定的；

5）同一工件的工序在同一時刻只能在一個班組上加工，同一時刻一個班組只能加工一個工件。

以下是數(shù)學(xué)模型中參數(shù)和變量的說明：N為工件總數(shù)；m為班組總數(shù)；Ω為總的班組集；i為班組序號，i=1，2，3…m； j，k 為工件序號， j，k=1，2，3…n；TOj為工件j的總工序數(shù)；Ojx為工件j的第x道工序；Xijx為工件j的第x道工序在i上加工；tijx為工件j的第x道工序在i上加工時間；Sjx為工件j的第x道工序加工開始時間；Ejx為工件j的第x道工序加工結(jié)束時間；Cmax為最大完成時間。

柔性路徑選擇調(diào)度模型必須滿足的約束：

1）每一個工件工序的加工具有優(yōu)先級，則

2）任一確定時刻，班組i不能同時加工2個不同的工件，也不能同時加工2道不同的工序，則：

多目標(biāo)優(yōu)化問題數(shù)學(xué)模型描述：

給定決策向量 X=（x1，x2，…，xz），滿足的約束條件為

其中：g為q維向量函數(shù)；h為p維向量函數(shù)；設(shè)有t個相互沖突的優(yōu)化目標(biāo)，可表示為

則 f為 t維向量函數(shù)。 求 X*=（x1*，x2*，…，xz*），使f（X*）在滿足式（6）和式（7）條件下的目標(biāo)達(dá)到最優(yōu)。為便于求解，將所有優(yōu)化目標(biāo)表示為最小化函數(shù)，即：

因此目標(biāo)優(yōu)化問題的統(tǒng)一表達(dá)形式為

多目標(biāo)生產(chǎn)模型的建立：

在滿足上述條件的前提下，可對調(diào)度模型中的工件進(jìn)行調(diào)度，從而確定工件的加工設(shè)備，及在設(shè)備上的開工時間。考慮生產(chǎn)調(diào)度中涉及多個目標(biāo)函數(shù)，建立的調(diào)度模型：

1）工件最大完工時間最小

2）瓶頸設(shè)備負(fù)荷最小

3）設(shè)備總負(fù)荷最小

所以建立多目標(biāo)調(diào)度問題的數(shù)學(xué)模型可表達(dá)為

2.2 鋼構(gòu)件工序在多班組中調(diào)度的關(guān)鍵算法

圖2 混合算法結(jié)構(gòu)Fig.2 Hybrid algorithm structure

2.3 工序可選班組析取圖模型

采用蟻群優(yōu)化算法求解FJSP中工藝路線問題，首先將該問題表示成易求解的解構(gòu)造圖模型，即建立工件各工序可選加工班組析取圖模型，然后將其進(jìn)一步描述為有向圖G=（V，C∪D）（V為所有節(jié)點的集合，C為有向圖G中所有有向弧的集合，D為有向圖G屮所有析取邊的集合）。假設(shè)工件數(shù)、工序數(shù)及在各班組上的加工時間已知，則析取圖模型和有向圖分別如表1和圖3所示。

表1 析取圖模型Tab.1 Disjunctive graph model

圖3 析取圖模型Fig.3 Model of disjunctive

2.4 基于蟻群算法班組分配規(guī)則

由析取圖G=（V，C∪D）可設(shè)計螞蟻的解構(gòu)造圖G=（V，C∪D，τ），τ為信息素分布， 代表弧對解質(zhì)量的影響。根據(jù)圖3中析取圖模型，可做出工件J1的解構(gòu)造圖，如圖4所示。為了便于螞蟻游歷，解構(gòu)造圖中還標(biāo)注出了局部啟發(fā)式信息，啟發(fā)式信息將在后續(xù)中介紹。

圖4 工件J1的解構(gòu)造Fig.4 Construction of J1piece

為了能夠提高算法解的質(zhì)量和縮短搜索時間，本文將采取最短加工時長班組優(yōu)先被選中策略。并在班組選擇過程中將每個班組已負(fù)載的加工時間進(jìn)行累計，來使班組工作負(fù)荷達(dá)到平衡。設(shè)每個班組已負(fù)載的加工時間累計為CMsum，則班組的分配步驟為

1）設(shè)置班組負(fù)荷矩陣CMsum為1×3的矩陣。每一列分別為M1，M2，M3的總負(fù)荷。將該矩陣初始化為［0，0，0］。

2）首先選擇工件J1的工序O11，可選班組為M1，M2。選擇最短加工時長班組M1，則班組負(fù)荷矩陣變?yōu)?CMsum=［2，0，0］。

3）再選 J1的工序 O12，可選班組為 M1，M2，M3。選擇最短加工時長班組M1，則班組負(fù)荷矩陣變?yōu)镃Msum=［5，0，0］。

4）再選 J1的工序 O13，可選班組為 M1，M3。 選擇最短加工時長班組M3，則班組負(fù)荷矩陣變?yōu)镃Msum=［5，0，5］。

5）以此類推，再分別選擇工件J2的工序O21、O22、O23，則對應(yīng)的班組負(fù)荷矩陣分別為［8，0，5］［8，0，8］［8，3，8］。

2.5 蟻群算法啟發(fā)式信息設(shè)計

局部啟發(fā)式信息η的作用是指引螞蟻選擇加工時間最短的班組，從而有利于總負(fù)荷和調(diào)度方法的最優(yōu)化，同時還指引螞蟻選擇已承載負(fù)荷少的班組，來使班組間負(fù)荷均勻分配。根據(jù)分配規(guī)則，確定路徑啟發(fā)式信息：ηij=1/（CM（1+CMsum）），CM為選擇 M班組的負(fù)載，CMsum為選擇M班組時累計負(fù)載。啟發(fā)式信息數(shù)值可見圖4的解構(gòu)造圖。工件工序間轉(zhuǎn)移規(guī)則為

其它情況 Pijm（t）=0。

式中：Pijm（t）為 t時刻螞蟻 m 選擇（i， j）路徑的概率；τij（t）為 t時刻選擇（i， j）路徑的信息素數(shù)量；a 為螞蟻游歷下一道工序時的班組集。

3 軟件實現(xiàn)

工序多設(shè)備選擇調(diào)度屬于柔性作業(yè)調(diào)度，本文采用封閉式蟻群-遺傳混合算法進(jìn)行求解。首先采用蟻群算法解決工序班組選擇問題，從而確定待加工工件相關(guān)工序的優(yōu)選班組；然后采用遺傳算法求解基本班組調(diào)度問題。其工作流程如圖5、圖6所示。相關(guān)參數(shù)設(shè)置：蟻群算法參數(shù)借鑒文獻(xiàn)[6]，迭代數(shù)Nc=50、螞蟻數(shù)m=8、啟發(fā)式因子重要程度參數(shù)β=5、信息重要程度參數(shù)α=1、信息素?fù)]發(fā)率ρ=0.3、信息素增強(qiáng)度系數(shù)Q=6，遺傳算法參數(shù)借鑒文獻(xiàn)[7]，群體大小50、迭代次數(shù)maxGen=40、交叉因子pxover=0.85、選擇算子psel=0.1、變異因子pmutation=0.2。

圖5 遺傳算法流程圖Fig.5 Flow chart of genetic algorithm

圖6 蟻群遺傳算法流程圖Fig.6 Flow chart of ant colony genetic algorithm

4 應(yīng)用與結(jié)果分析

以表1中工件工序的可加工分布情況為例，將本文提出的蟻群遺傳混合優(yōu)化算法應(yīng)用于其中，通過編程進(jìn)行實現(xiàn)。經(jīng)過優(yōu)化排序得到工件工序最終加工順序，如表2所示。

表2 工件工序加工順序Tab.2 Order of workpiece machining processes

由加工順序生成的甘特圖如圖7所示。

圖7 排產(chǎn)甘特圖Fig.7 Scheduling Gantt

若不使用該方法進(jìn)行排產(chǎn)，得到工件工序加工順序如表3所示。

表3 工件工序加工順序Tab.3 Order of workpiece machining processes

生成相應(yīng)的排產(chǎn)甘特圖如圖8所示。

由圖7和圖8的排產(chǎn)甘特圖對比可知，通過蟻群遺傳混合算法優(yōu)化得到的排產(chǎn)方案要優(yōu)于不用此方法的排產(chǎn)方案，可提前3個工作日完成工作任務(wù)。

圖8 排產(chǎn)甘特圖Fig.8 Scheduling Gantt

5 結(jié)語

本論文討論的是工序多設(shè)備選擇調(diào)度的柔性作業(yè)問題，建立柔性作業(yè)的工序約束和生產(chǎn)調(diào)度模型。在算法中著重討論了班組分配問題，并提出通過蟻群遺傳混合算法來解決該問題。應(yīng)用結(jié)果表明該方法是有效的。下一步將優(yōu)化算法中的相關(guān)參數(shù)，以進(jìn)一步提高分配效率。

[1]黃肖玲，柴天佑.復(fù)雜生產(chǎn)過程計劃調(diào)度級聯(lián)模型在選礦MES中的應(yīng)用研究[J].自動化學(xué)報，2011，37（9）：1130-1139.

[2]Kacem I，Hammadi S，Borne S，et al.Pareto-optimality approach for flexible Job-Shop scheduling problems：hybridization of evolutionary algorithms and fuzzy logic[J].M Athematics and Computers in Simulation，2002，60（3-5）：245-276.

[3]張維存，鄭丕諤，吳曉丹.基于蟻群粒子群算法求解多目標(biāo)柔性調(diào)度問題[J].計算機(jī)應(yīng)用，2007，27（4）：936-938，941.

[4]夏蔚軍，吳智銘.基于混合微粒群優(yōu)化的多目標(biāo)柔性Job-Shop調(diào)度[J].控制與決策，2005，20（2）：137-141.

[5]鄧宇巍.熱軋帶鋼生產(chǎn)調(diào)度模型與算法研究[D].上海：上海交通大學(xué)，2007.

[6]CARLIER J，PINSON E.Adjustment heads and tails for the job shop scheduling problem[J].European Journal of Operational Research，1994，78（3）：146-161.