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

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

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

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

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

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

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

2 關(guān)鍵算法

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

2.1 問(wèn)題描述與建模

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

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

1）工序一旦開(kāi)始就不能中斷；

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

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

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

5）同一工件的工序在同一時(shí)刻只能在一個(gè)班組上加工，同一時(shí)刻一個(gè)班組只能加工一個(gè)工件。

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

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

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

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

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

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

其中：g為q維向量函數(shù)；h為p維向量函數(shù)；設(shè)有t個(gè)相互沖突的優(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)化問(wèn)題的統(tǒng)一表達(dá)形式為

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

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

1）工件最大完工時(shí)間最小

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

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

所以建立多目標(biāo)調(diào)度問(wèn)題的數(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中工藝路線問(wèn)題，首先將該問(wèn)題表示成易求解的解構(gòu)造圖模型，即建立工件各工序可選加工班組析取圖模型，然后將其進(jìn)一步描述為有向圖G=（V，C∪D）（V為所有節(jié)點(diǎn)的集合，C為有向圖G中所有有向弧的集合，D為有向圖G屮所有析取邊的集合）。假設(shè)工件數(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è)計(jì)螞蟻的解構(gòu)造圖G=（V，C∪D，τ），τ為信息素分布， 代表弧對(duì)解質(zhì)量的影響。根據(jù)圖3中析取圖模型，可做出工件J1的解構(gòu)造圖，如圖4所示。為了便于螞蟻游歷，解構(gòu)造圖中還標(biāo)注出了局部啟發(fā)式信息，啟發(fā)式信息將在后續(xù)中介紹。

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

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

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

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

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

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

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

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

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

其它情況 Pijm（t）=0。

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

3 軟件實(shí)現(xiàn)

工序多設(shè)備選擇調(diào)度屬于柔性作業(yè)調(diào)度，本文采用封閉式蟻群-遺傳混合算法進(jìn)行求解。首先采用蟻群算法解決工序班組選擇問(wèn)題，從而確定待加工工件相關(guān)工序的優(yōu)選班組；然后采用遺傳算法求解基本班組調(diào)度問(wèn)題。其工作流程如圖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)用于其中，通過(guò)編程進(jìn)行實(shí)現(xiàn)。經(jīng)過(guò)優(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)甘特圖對(duì)比可知，通過(guò)蟻群遺傳混合算法優(yōu)化得到的排產(chǎn)方案要優(yōu)于不用此方法的排產(chǎn)方案，可提前3個(gè)工作日完成工作任務(wù)。

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

5 結(jié)語(yǔ)

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

[1]黃肖玲，柴天佑.復(fù)雜生產(chǎn)過(guò)程計(jì)劃調(diào)度級(jí)聯(lián)模型在選礦MES中的應(yīng)用研究[J].自動(dòng)化學(xué)報(bào)，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)度問(wèn)題[J].計(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.