花季偉　佟靜翠　雷兆明

1(天津師范大學計算機與信息工程學院　天津 300387)2(河北工業(yè)大學控制科學與工程學院　天津 300401)

?

鋼構企業(yè)生產調度系統(tǒng)的研究與應用

花季偉1佟靜翠2雷兆明2

1(天津師范大學計算機與信息工程學院天津 300387)2(河北工業(yè)大學控制科學與工程學院天津 300401)

一個好的生產調度系統(tǒng)可以給鋼結構企業(yè)的生產帶來巨大的收益，但鋼構企業(yè)的生產調度約束復雜、尋優(yōu)困難。針對該調度問題提出基于蟻群遺傳混合算法的生產調度模型，并解決動態(tài)調度情況下的緊急工件插入問題。以河北省某鋼結構企業(yè)為依托，對該生產調度系統(tǒng)執(zhí)行情況進行研究，實驗結果表明，該蟻群遺傳混合算法在鋼構企業(yè)生產調度中的應用可以提高生產效率。

鋼結構生產調度蟻群遺傳混合算法動態(tài)調度

0　引　言

在信息化飛速發(fā)展的今天，企業(yè)越來越開始關注合理而高效的生產管理系統(tǒng)。這是因為合理而高效的生產管理系統(tǒng)可以保障企業(yè)的生產調度合理順暢的實施[1]。由于鋼結構產品具有強度高、塑性和韌性好，材質均勻等特點，因此在人們的生產生活中得到了廣泛使用，隨之而來的就是鋼結構企業(yè)的迅速發(fā)展。這就需要鋼結構企業(yè)在進行生產時配以行之有效的生產調度系統(tǒng)，從而達到提高生產效率，減少勞力和機械損耗等的目的。本文以某鋼構企業(yè)實際生產調度為基礎，以提高企業(yè)利潤、優(yōu)化生產方案為目標，研究基于蟻群遺傳的混合算法的生產調度系統(tǒng)。

Job-Shop調度是許多學科研究的熱點，同時也是典型的NP難題[2]。非人工智能的調度方法有基于運籌學的方法、啟發(fā)式調度方法、基于仿真的方法，這些方法都對實際情況進行了理想處理，使計劃與生產調度脫節(jié)，結果難以實用化[3]。人工智能調度方法是基于人工智能技術和人類調度專家經(jīng)驗對調度問題進行建模并求解的方法總稱。目前國內已有很多該方面的研究，王?，嶽4]等建立基于雙層規(guī)則組合的Job Shop多目標柔性調度方法；姜樺[5]等以旅行商問題說明了蟻群算法的模型結構。本文結合鋼結構的實際生產，建立了多目標生產數(shù)學模型，較好地解決了鋼構企業(yè)的生產調度難題。

1　功能簡介

對鋼結構企業(yè)而言，生產管理系統(tǒng)面臨的最大困難是如何面向多構件生產進行有效的組織生產。鋼構件在生產過程中會受到眾多條件因素的影響，如不同品種、構件的工序數(shù)、工序的班組分配、緊急件的動態(tài)插入等，所以設計一個高效的生產調度系統(tǒng)是企業(yè)生產環(huán)節(jié)的關鍵所在。

生產調度是將產品的生產順序解析成為設備、原料等生產資源的分配順序，以客戶的訂單需求為目標，結合企業(yè)的生產能力和其他各方面的實際約束，對生產資源進行合理分配，以達到提高生產效率、增加企業(yè)利潤的目標，從而指導企業(yè)生產的各個環(huán)節(jié)有序進行。所以生產計劃與生產調度系統(tǒng)的功能模塊如圖1所示。

圖1　生產計劃與調度系統(tǒng)圖

以下是對生產計劃與調度系統(tǒng)中主要模塊的簡介：1) 工序拆分模塊負責將要生產的鋼構件進行拆分，生成不同的生產工序，以便班組對其進行加工；2) 生產計劃模塊負責將同一批次的鋼構件工序進行排產，生成工序的生產時間及負責生產的班組，該模塊的工序的排產方案由本文提出的混合算法來實現(xiàn)；3) 計劃進度模塊，各班組負責人可以通過查詢該模塊來了解各自班組的近期生產計劃；4) 計劃調整模塊，當有緊急鋼構件需要加工處理時，可以通過計劃調整模塊來實現(xiàn)對現(xiàn)有生產計劃的調整，也就是動態(tài)調度的過程。

2　算法分析

鋼結構企業(yè)生產屬于柔性、離散的生產過程，問題主要有：1) 工序多班組選擇問題；2) 動態(tài)調度問題。工序在加工時如果選擇加工班組不當或加工時間安排不合理就會使生產效率下降，導致企業(yè)利潤受損。當有緊急件需要處理時，如果安排不當不僅會影響緊急件的完工時間，甚至會導致其他構件不能按時完成。所以需要一個合理的算法來制定高效的生產計劃。針對以上情況本文采用分層法解決柔性調度問題。根據(jù)生產系統(tǒng)開發(fā)目標構建數(shù)學模型，首先利用蟻群算法避免大量冗余迭代的特點解決班組選擇問題。然后借鑒遺傳算法的良好的全局搜索性優(yōu)勢解決作業(yè)調度問題，以使生產系統(tǒng)相關性能指標最優(yōu)。如總完工時間，生產能力與負荷均衡；而對于動態(tài)調度問題主要是解決緊急件插入情況，具體解決辦法根據(jù)緊急構件插入時間點而定。

2.1問題描述

鋼構件工序的多班組選擇的問題描述：n個構件在g個不同班組上加工，每個構件x道工序(x>1)，提前給出各構件的工序加工順序。每道工序可以在若干個班組上加工，且不同的班組加工同一道工序所用的工時不同。該生產調度的目標是為每個鋼構件的每道工序找到合適的班組，并確定每個班組上的工序加工順序及加工時間，使各個班組的生產能力與負荷均衡且完成總任務時間最短這一性能指標最優(yōu)。

針對問題描述可對生產過程做出以下約束：

1) 工序在加工過程中不能中斷；

2) 同一種鋼構件的各工序間具有加工順序，不同鋼構件間的工序加工不具有加工順序；

3) 預先給定了工序在班組上的加工時長；

4) 同一時刻一個鋼構件只能在一個班組上加工，且班組不能同時加工多道工序。

以下是對數(shù)學模型中參數(shù)和變量進行的說明：

g:加工班組總數(shù)

n:鋼構件總數(shù)

i,j:鋼構件序號，i，j=1,2,…,n

k:設備序號，k=1,2,…,m

Tj:第j個鋼構件的工序總數(shù)

Ojx:第j個鋼構件第x道工序

Mkjx:第j個鋼構件第x道工序在班組i上加工

tkjx:第j個鋼構件第x道工序在班組i上加工時間

bjx:第j個鋼構件第x道工序加工開始時間

fjx:第j個鋼構件第x道工序加工結束時間

CMax:最大的完工時間

該問題的約束條件如下：

1) 同一個鋼構件的加工工序優(yōu)先級不同，如式(1)和式(2)：

bjx+(Mkjx×tkjx)≤fjx

(1)

fjx≤bj(x+1)

(2)

2) 同一時刻，班組k不能同時加工不同的鋼構件，如式(3)：

bkjx+ tkjx≤bki l×rkjxil

(3)

鋼構件j的第x道工序在班組k上加工時Mkjx為1，否則Mkjx為0。

鋼構件j的第x道工序在班組k上加工且鋼構件i的第l道工序在班組k上加工時rkjxil為1，否則rkjxil為0 。

多目標優(yōu)化數(shù)學模型：

已知決策向量X=(x1,x2，…,xz),約束條件為：

Gp(x)≥0(p=1,2,…,l)

(4)

Hq(X)=0(q=1,2,…,z)

(5)

設相互沖突的優(yōu)化目標有n個，則優(yōu)化目標為：

F(X)=(F1(X), F2(X),…,Fn(X))

(6)

根據(jù)上述約束條件，可以對模型中的鋼構件進行調度，以此來確定生產調度的最優(yōu)解。考慮到生產調度中會有多個目標函數(shù)的情況，所以有如下模型：

1) 瓶頸班組的負荷最?。?/p>

MinF1= Min(WM)= Min(Max(Wk))

(7)

其中，Wk表示班組k的負荷。

2) 班組的總負荷最小：

(8)

其中，Wk表示班組k負荷。

3) 所有鋼構件完工時間最?。?/p>

MinF3= Min(Max(Cj))

(9)

其中，Cj表示鋼構件j的最終完工時間。

所以Min(F1,F2,F3)即為多目標調度問題的數(shù)學模型。

2.2鋼構件的多班組調度

本設計采用蟻群算法來獲得多班組資源優(yōu)化分配可行解，并將其作為班組約束，然后用遺傳算法求解JSP問題。假設柔性作業(yè)調度模型參與的鋼構件集{J1,J2,…,Jn},鋼構件工序加工的班組集{ M1，M2，…,Mm}以及相應的時間集{T1,T2,…,Tt}。然后通過蟻群算法生成班組分配方案，再通過遺傳算法對各班組進行優(yōu)化，形成最終的排序方案，即最優(yōu)調度結果。本文采用的是蟻群—遺傳的開放式混合算法，即先用蟻群算法求出班組的最優(yōu)分配方案，再用遺傳算法求出各車間的工序排產方案，最終得到優(yōu)化結果。

2.3已知工序的析取圖模型

本文采用蟻群算法對FJSP的工藝路線問題進行求解，可將其看成是旅行商問題。將鋼構件工序可選加工班組看成是城市的結點，然后將其表示成解構造圖模型，有向弧代表當前工序加工完后可移向的班組方向。螞蟻的解構造圖為G=(V,CUD,τ) ( V表示所有節(jié)點的集合；C表示有向圖G中所有有向弧的集合；D表示有向圖G中所有析取邊的集合；τ表示信息素分布，與解構造圖上的弧相關聯(lián))?，F(xiàn)以鋼構件在車間6個班組的生產情況為例，6個班組分別為下料、組立、鉚對、焊接、除銹和噴漆班組，分別用M1、M2、M3、M4、M5、M6表示。已知鋼構件數(shù)、工序數(shù)及相應的加工工時，則析取圖模型如表1所示。

表1　析取圖模型

2.4班組分配規(guī)則

為了能夠提高解的質量和縮短搜索時間，提升效率，本文所采取的策略是優(yōu)先選中加工時長最短的班組。同時累計每個班組已負載的加工時間, 從而平衡各班組的工作負荷。設班組已負載的加工時間累計為CMsum(1×6矩陣)，該矩陣初始化為[0,0,0,0,0,0]，用于分別累計六個班組加工的工時。如當加工鋼構件 J1的工序O11時，需選取加工時長最短班組M1，所以將該工時2加到矩陣CMsum的第一列中。

η為局部啟發(fā)式信息，它的作用是指引螞蟻選擇加工時間最短的班組[7]。η的取值:ηij=1/(CM(1+CMsum)),CM表示選擇M班組時的當前負載。則轉移規(guī)則公式為：

(10)

2.5各班組中工序的優(yōu)化

由上述的蟻群算法可得班組的最優(yōu)分配方案，即確定出各鋼構件工序的優(yōu)選加工班組。這樣就可以將工序多班組選擇問題簡化成鋼構件工序在確定班組上的加工順序及時間問題。也就是說該最優(yōu)方案可作為設備約束條件，用于遺傳算法的約束，進而通過遺傳算法解決各車間的工序排產問題，并最終得到柔性作業(yè)車間調度的最優(yōu)解。

綜合考慮上述的約束條件，遺傳算法可以采用以下的編碼方式：每個染色體上的每一個基因代表工件的一道工序，該工序的加工班組已確定，染色體的長度為鋼構件數(shù)與工序數(shù)的乘積[8]。

1) 編碼：假設由蟻群算法求得的設備分配最優(yōu)解為：J1的三道工序選擇的班組分別為M1、M4、M1，J2的三道工序選擇的班組分別為M5、M1、M3，以及J3J4的班組分配情況。隨機生成的染色體[1 2 2 1 2 1 3 3 3 4 4 4],1表示鋼構件J1，2表示鋼構件J2，其中出現(xiàn)的三個1表示J1的三道工序，三個1在染色體中出現(xiàn)的位置表示三道工序的先后順序，同理工件J2J3J4也是如此。

2) 適應度函數(shù)選擇：由生產調度的模型約束知本文遺傳算法的目標函數(shù)就是求鋼構件最大完工時間最小，即式(9)。遺傳算法的適應度函數(shù):

(11)

其中F3是鋼構件的完工時間，cmax根據(jù)鋼構件加工時間經(jīng)驗而定，為常數(shù)。

3) 遺傳算子操作：可采用輪盤賭的方式隨機選取兩條染色體，采用單點的方式進行交叉。對選的兩條染色體依次從頭增加向量長度，當兩個向量含有相同的數(shù)字類別和長度時，便將該點作為交叉點進行交叉，保留最優(yōu)個體。操作如下：

根據(jù)前面染色體定義的規(guī)則對染色體進行初始化，隨機生成預知數(shù)量的染色體。規(guī)定迭代次數(shù)，再通過遺傳算法的適應度計算、基于POX交叉策略的設計、采用逆序變異規(guī)則進行變異，對其進行算法迭代，最終得到算法的最優(yōu)解。該最優(yōu)解即為鋼構件生產的最佳生產進度。

2.6動態(tài)調度問題的解決

車間生產過程是一個動態(tài)的調度過程，因此還需要在設計的基本調度方案(計劃進度模塊)上考慮緊急件插入的情況，對計劃進度進行調整，即動態(tài)調度的情況。根據(jù)緊急件插入的時間點不同，分為四種情況：1) 在工序加工之前插入；2) 在工序加工過程中插入；3) 在工序間插入；4) 在所有工序完成后插入。針對不同情況解決方案如下：

1) 若緊急工序的所需時長<(工序開始時間-插入緊急工序時間點)，則對整體調度無影響；否則，調度方案時間點右移(插入緊急工序時間點+插入緊急工序的所需時長-工序開始時間)。

2) 緊急工件緊接著其工序完成時間開始加工,若(下道工序開始時間-工序結束時間)>插入緊急工序的時長，則對整體調度無影響；否則，該工序后的所有工序后移(插入緊急工序的所需時長+工序結束時間-下道工序開始時間)。

3) 若插入緊急工序的時長<(下道工序開始時間-插入緊急工序時間點), 則對整體調度無影響；否則，調度方案時間點右移(插入緊急工序時間點+插入緊急工序的所需時長-下道工序開始時間)。

4) 若除當前設備外,在插入緊急工件時間點以后無工件工序處于加工或準備加工狀態(tài)，則對整體調度無影響；否則，若其他設備處于加工狀態(tài)，轉2)處理；若其他設備處于準備加工狀態(tài)，轉3)處理。

通過對緊急件的處理，對計劃進度進行調整，生成調整后的進度。通過計劃進度模塊與計劃調整模塊相結合即可確保各鋼構件按時完成。

3　算法實現(xiàn)

本文采用的是開放式蟻群—遺傳混合算法對作業(yè)調度問題求解。首先采用蟻群算法求解工序班組的優(yōu)選問題，目的是確定待加工鋼構件和該鋼構件相關工序的優(yōu)選班組；再采用遺傳算法求解班組中的各道工序加工順序和加工的起止時間?；镜膮?shù)設置如下：蟻群算法，螞蟻數(shù)m、迭代數(shù)Nc、信息重要程度α、啟發(fā)式因子重要程度β、信息素揮發(fā)系數(shù)ρ、信息素增強系數(shù)Q見表2所示；遺傳算法,迭代次數(shù)maxGen、種群大小pop、交叉因子crossover、變異因子mutation、選擇算子psel見表3所示。其工作流程如圖2、圖3所示。當考慮到緊急件插入情況時，其動態(tài)調度流程如圖4所示。

表2　蟻群算法參數(shù)

表3　遺傳算法參數(shù)

圖2　遺傳算法流程圖

圖3　蟻群遺傳算法流程圖

圖4　動態(tài)調度流程圖

4　實驗及結果分析

已知該鋼結構企業(yè)某車間共有6個班組，以表1給出的生產信息為例，對其進行仿真(算法參數(shù)參見表2和表3)，并將其仿真結果與蟻群算法的仿真結果進行對比。表4給出了四種構件各自的加工總時間、生產的總時間及成功的次數(shù)。圖5給出了結果仿真圖,橫坐標表示算法求解時迭代的次數(shù)，縱坐標表示加工所需的總工時(以天計算)。

表4　生產調度結果表

圖5　兩種算法仿真結果圖

由仿真結果可以看出，在車間班組、工件數(shù)量、工序等相同的情況下，雖然兩種算法最終收斂到的值差不多，但是蟻群遺傳混合算法收斂速度明顯優(yōu)于蟻群算法的收斂速度，成功次數(shù)更高，故可靠性更好?？梢娫撍惴ㄔ谝欢ǔ潭壬霞裙?jié)省了排產時間，又提高了生產效率。

5　結　語

本文首先對生產計劃與生產調度系統(tǒng)的主要模塊進行了簡單的介紹。針對生產計劃模塊和計劃調整模塊遇到的問題提出了解決方案：討論了柔性作業(yè)車間調度的問題，通過對柔性車間作業(yè)的工序約束建立了生產調度模型。在算法中著重討論了班組分配和工序加工順序問題，并提出了基于蟻群遺傳的混合算法對該問題進行求解。同時又考慮了動態(tài)調度情況下的緊急工件插入問題，并給出了相應的解決方案。實驗結果證明，該混合算法可以很好地解決該企業(yè)的生產調度問題，使企業(yè)產品能夠按時保質保量的完成。本文算法的不足之處就是沒有考慮大型公共設備的運輸時間，這也是以后需要改進的地方。

[1] 黃肖玲,柴天佑.復雜生產過程計劃調度級聯(lián)模型在選礦MES中的應用研究[J].自動化學報,2011,37(9):1130-1139.

[2] 王麗紅.基于混合蟻群算法Job-Shop調度問題的研究與實現(xiàn)[D].哈爾濱理工大學,2008.

[3] 張青.基于遺傳算法的車間調度問題研究[D].長春理工大學,2012.

[4] 王?，?蔣增強,葛茂根.基于規(guī)則組合的Job Shop多目標柔性調度方法[J].合肥工業(yè)大學學報:自然科學版,2010(1):14-18.

[5] 姜樺,李莉,喬非,等.蟻群算法在生產調度中的應用[J].計算機工程,2005(5):76-78.

[6] 鄧宇巍.熱軋帶鋼生產調度模型與算法研究[D].上海交通大學,2007.

[7] 黃麗韶,朱喜基.基于MATLAB的蟻群算法求解旅行商問題[J].無線互聯(lián)科技,2012(3):76-78.

[8] 宋毅.基于遺傳算法的生產調度方法及其軟件實現(xiàn)[D].浙江工業(yè)大學,2003.

RESEARCH AND APPLICATION OF PRODUCTION SCHEDULING SYSTEM IN STEEL STRUCTURE ENTERPRISES

Hua Jiwei1Tong Jingcui2Lei Zhaoming2

1(College of Computer and Information Engineering,Tianjin Normal University,Tianjin 300387,China)2(SchoolofControlScienceandEngineering,HebeiUniversityofTechnology,Tianjin300401,China)

A good production scheduling system can bring enormous benefits to the production of steel structure enterprises, however its production scheduling constraints are complex, and the optimisation are difficult too. For the scheduling problem, we proposed a hybrid ant-genetic algorithm-based production scheduling model. At the same time, we solved the problem of urgent workpieces insertion in dynamic scheduling case. Based on a certain steel structure enterprise in Hebei province, we studied the implementation of this production scheduling system. Experimental results showed that the application of hybrid ant-genetic algorithm in production scheduling of steel structure enterprise could improve production efficiency.

Steel structureProduction schedulingHybrid ant-genetic algorithmDynamic scheduling

2015-01-07。天津市高等學?？萍及l(fā)展基金計劃項目(20120814)；河北省科技支撐計劃項目(13210307D)。花季偉，講師，主研領域：工業(yè)物聯(lián)網(wǎng)應用。佟靜翠，碩士生。雷兆明，講師。

TP3

A

10.3969/j.issn.1000-386x.2016.09.016