鋼構(gòu)企業(yè)生產(chǎn)調(diào)度系統(tǒng)的研究與應(yīng)用

花季偉　佟靜翠　雷兆明

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

?

鋼構(gòu)企業(yè)生產(chǎn)調(diào)度系統(tǒng)的研究與應(yīng)用

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

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

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

鋼結(jié)構(gòu)生產(chǎn)調(diào)度蟻群遺傳混合算法動態(tài)調(diào)度

0　引　言

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

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

1　功能簡介

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

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

圖1　生產(chǎn)計劃與調(diào)度系統(tǒng)圖

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

2　算法分析

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

2.1問題描述

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

針對問題描述可對生產(chǎn)過程做出以下約束：

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

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

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

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

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

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

n:鋼構(gòu)件總數(shù)

i,j:鋼構(gòu)件序號，i，j=1,2,…,n

k:設(shè)備序號，k=1,2,…,m

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

Ojx:第j個鋼構(gòu)件第x道工序

Mkjx:第j個鋼構(gòu)件第x道工序在班組i上加工

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

bjx:第j個鋼構(gòu)件第x道工序加工開始時間

fjx:第j個鋼構(gòu)件第x道工序加工結(jié)束時間

CMax:最大的完工時間

該問題的約束條件如下：

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

bjx+(Mkjx×tkjx)≤fjx

(1)

fjx≤bj(x+1)

(2)

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

bkjx+ tkjx≤bki l×rkjxil

(3)

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

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

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

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

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

(4)

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

(5)

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

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

(6)

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

1) 瓶頸班組的負(fù)荷最小：

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

(7)

其中，Wk表示班組k的負(fù)荷。

2) 班組的總負(fù)荷最小：

(8)

其中，Wk表示班組k負(fù)荷。

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

MinF3= Min(Max(Cj))

(9)

其中，Cj表示鋼構(gòu)件j的最終完工時間。

所以Min(F1,F2,F3)即為多目標(biāo)調(diào)度問題的數(shù)學(xué)模型。

2.2鋼構(gòu)件的多班組調(diào)度

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

2.3已知工序的析取圖模型

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

表1　析取圖模型

2.4班組分配規(guī)則

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

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

(10)

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

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

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

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

2) 適應(yīng)度函數(shù)選擇：由生產(chǎn)調(diào)度的模型約束知本文遺傳算法的目標(biāo)函數(shù)就是求鋼構(gòu)件最大完工時間最小，即式(9)。遺傳算法的適應(yīng)度函數(shù):

(11)

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

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

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

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

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

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

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

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

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

通過對緊急件的處理，對計劃進度進行調(diào)整，生成調(diào)整后的進度。通過計劃進度模塊與計劃調(diào)整模塊相結(jié)合即可確保各鋼構(gòu)件按時完成。

3　算法實現(xiàn)

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

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

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

圖2　遺傳算法流程圖

圖3　蟻群遺傳算法流程圖

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

4　實驗及結(jié)果分析

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

表4　生產(chǎn)調(diào)度結(jié)果表

圖5　兩種算法仿真結(jié)果圖

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

5　結(jié)　語

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

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

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

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

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

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

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

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

[8] 宋毅.基于遺傳算法的生產(chǎn)調(diào)度方法及其軟件實現(xiàn)[D].浙江工業(yè)大學(xué),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。天津市高等學(xué)?？萍及l(fā)展基金計劃項目(20120814)；河北省科技支撐計劃項目(13210307D)?；緜ィv師，主研領(lǐng)域：工業(yè)物聯(lián)網(wǎng)應(yīng)用。佟靜翠，碩士生。雷兆明，講師。

TP3

A

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