范佳靜 曹玉華 曹 敏

1.浙江科技學(xué)院經(jīng)濟(jì)與管理學(xué)院，杭州，3100232.浙江科技學(xué)院機(jī)械與汽車工程學(xué)院，杭州，310023

基于改進(jìn)分散搜索算法的多資源跨單元調(diào)度問題研究

范佳靜1曹玉華1曹 敏2

1.浙江科技學(xué)院經(jīng)濟(jì)與管理學(xué)院，杭州，3100232.浙江科技學(xué)院機(jī)械與汽車工程學(xué)院，杭州，310023

針對單元制造系統(tǒng)中不同設(shè)備、操作人員和自動(dòng)導(dǎo)引小車的特點(diǎn)以及對制造系統(tǒng)的作用，提出了多資源約束下的跨單元調(diào)度問題。以零件延期交貨、員工工作人數(shù)及跨單元移動(dòng)次數(shù)、自動(dòng)導(dǎo)引小車數(shù)量最少為目標(biāo)，構(gòu)建目標(biāo)規(guī)劃模型。針對模型的特殊性，提出了改進(jìn)分散搜索算法，算法中應(yīng)用遺傳算法獲得新解，應(yīng)用模式搜索法改進(jìn)新解，進(jìn)一步提高了算法的收斂速度。最后將此模型及算法應(yīng)用于不同規(guī)模的8個(gè)算例，證明了模型和算法的有效性，針對算例進(jìn)行詳細(xì)分析，說明設(shè)備、人員和自動(dòng)導(dǎo)引小車在調(diào)度過程中的相互作用。

跨單元；調(diào)度；多資源；改進(jìn)分散搜索算法

0 引言

單元制造(cellular manufacturing，CM)既能結(jié)合工作車間方式的靈活性和流水線方式的高效率，又能以近似剛性流水線的成本來生產(chǎn)多品種小批量商品，滿足市場在時(shí)間、質(zhì)量、成本、柔性等多方面的要求，代表著生產(chǎn)方式的新方向。單元制造主要包括單元構(gòu)建、單元設(shè)計(jì)和單元調(diào)度，三方面既相互獨(dú)立又交互影響[1]。單元調(diào)度是實(shí)現(xiàn)企業(yè)資源優(yōu)化配置、提高準(zhǔn)時(shí)交貨率的關(guān)鍵因素。在現(xiàn)代制造企業(yè)中，多技能員工技術(shù)能力的提高、全自動(dòng)化設(shè)備的廣泛應(yīng)用以及AGV小車等自動(dòng)運(yùn)輸工具的推廣使得制造單元間的關(guān)系變得更加復(fù)雜和緊密，特別是跨單元調(diào)度問題中如果僅涉及設(shè)備單元調(diào)度，而忽略其他要素對生產(chǎn)進(jìn)度的影響，將導(dǎo)致整個(gè)調(diào)度方案在實(shí)施過程中與計(jì)劃產(chǎn)生較大偏差，出現(xiàn)延期交貨等問題，因此，需對制造單元進(jìn)行多資源跨單元調(diào)度，從而滿足調(diào)度系統(tǒng)多方面的要求。

目前學(xué)者已從不同角度對單元調(diào)度問題進(jìn)行了研究。王躍崗等[2]研究了一類帶有時(shí)間窗口的自動(dòng)化制造單元調(diào)度問題，即工件在工作站上的加工時(shí)間必須在給定的上下限時(shí)間范圍內(nèi)，并采用混合量子算法求解調(diào)度模型。韓文民等[3]提出在單元制造中，零件可以被分為不同批量，并采用不同的加工方式，從而提高設(shè)備效率。在單元調(diào)度問題中，部分零件不僅需要在所屬單元內(nèi)的設(shè)備上加工，還可能需要跨單元操作，相對于被忽略的單元內(nèi)物料之間的移動(dòng)時(shí)間，單元間的物料移動(dòng)時(shí)間則必須加以考慮，由此產(chǎn)生了跨單元調(diào)度問題。KARTHIKEYAN等[4]在單元構(gòu)建的基礎(chǔ)上提出采用啟發(fā)式方法進(jìn)行跨單元調(diào)度研究。李冬妮等[5]針對單元制造系統(tǒng)中需要多個(gè)單元協(xié)作完成的特殊件，提出柔性路徑下跨作業(yè)單元的特殊工件調(diào)度方法——基于信息素的方法 (pheromone-based approach，PBA)，并建立了Agent模型。賈凌云等[6]在文獻(xiàn)[5]的基礎(chǔ)上，提出了運(yùn)輸能力有限條件下的跨單元調(diào)度模型，并采用混合蛙跳和遺傳算法求解模型。SOLIMANPUR等[7]以流程時(shí)間為標(biāo)準(zhǔn)，結(jié)合單元間物料移動(dòng)時(shí)間約束構(gòu)建了跨單元調(diào)度模型，并提出了模型求解的禁忌搜索算法。季少梅[8]、MENG等[9]、PAJOUTAN等[10]均考慮了跨單元調(diào)度問題。目前隨著AGV小車在單元制造系統(tǒng)中的廣泛應(yīng)用，不少學(xué)者針對AGV小車調(diào)度問題進(jìn)行了相關(guān)研究。馬帥[11]針對帶AGV約束的作業(yè)車間調(diào)度問題工程實(shí)例，提出了雙系統(tǒng)優(yōu)化算法與混合編碼方式，對約束車間作業(yè)問題進(jìn)行了優(yōu)化調(diào)度。劉旭等[12]解決了混流作業(yè)車間中物料配送多自動(dòng)導(dǎo)引車的調(diào)度優(yōu)化問題，以AGV配送物料行駛時(shí)間最短為目標(biāo)建立數(shù)學(xué)優(yōu)化模型，并提出改進(jìn)遺傳算法進(jìn)行AGV任務(wù)分配和配送路徑優(yōu)化。NISHI等[13]針對制造系統(tǒng)中多AGV 路徑規(guī)劃問題，建立了多AGV調(diào)度模型，提出分解算法進(jìn)行求解。從目前AGV小車的調(diào)度來看，更多的是將其作為單一資源進(jìn)行研究，沒有同時(shí)考慮它對設(shè)備調(diào)度的影響，有時(shí)AGV小車的就近任務(wù)分配會導(dǎo)致一些設(shè)備上已加工完零件的等待，造成設(shè)備堵塞，從而延長整個(gè)加工周期，因此需要將AGV小車任務(wù)分配與設(shè)備調(diào)度統(tǒng)一規(guī)劃。

單元制造系統(tǒng)是一個(gè)復(fù)雜系統(tǒng)，除機(jī)器設(shè)備外，人力資源對系統(tǒng)柔性、高效的運(yùn)行也起著重要作用，隨著設(shè)備操作技術(shù)水平的不段提升，人與設(shè)備技術(shù)的融合問題顯得尤為突出。人們針對雙資源單元調(diào)度問題進(jìn)行了研究，如FAN等[14]不僅考慮了人員對單元調(diào)度的影響，同時(shí)還在制造單元構(gòu)建和調(diào)度中引入了員工學(xué)習(xí)能力因素，使得模型更加符合實(shí)際生產(chǎn)需求。但是在跨單元調(diào)度問題中涉及人員調(diào)度的研究相對較少。由于多技能員工可以操作不同單元的不同設(shè)備，故不僅需要考慮物料在單元間的移動(dòng)，還需考慮操作人員在單元間的移動(dòng)。零件的加工順序和工人工作內(nèi)容的安排具有很強(qiáng)的關(guān)聯(lián)性，為了縮短零件加工周期，調(diào)度方案可能會要求部分技能水平高的人員操作較多的設(shè)備，而增加了員工在單元間來回走動(dòng)的次數(shù)；也有可能會為了避免員工在單元間的走動(dòng)時(shí)間，而調(diào)整不同零件的加工順序，在不延期交貨的情況下，略微增加零件的整個(gè)流程時(shí)間。這就需要研究者在跨單元調(diào)度中不僅考慮零件在單元間的移動(dòng)，同時(shí)要關(guān)注員工的任務(wù)分配以及員工的跨單元操作的情況。

本文在多資源跨單元調(diào)度問題中同時(shí)分析設(shè)備、人員和AGV小車等多個(gè)資源對零件跨單元操作的影響，進(jìn)行合理的多資源任務(wù)分配，從而獲得整體效果的最優(yōu)，同時(shí)也對拓展單元調(diào)度問題的內(nèi)涵和研究方向提供一定的借鑒作用。

1 問題的描述及數(shù)學(xué)模型的構(gòu)建

本文提出的多資源約束下的跨單元調(diào)度問題認(rèn)為制造系統(tǒng)中包括K個(gè)單元，M臺設(shè)備(包括一定量的半自動(dòng)設(shè)備和全自動(dòng)設(shè)備，其中全自動(dòng)設(shè)備不需要員工進(jìn)行配合操作)及需要加工的P種零件，根據(jù)零件加工工藝順序以及設(shè)備單元?dú)w屬情況，零件需要依靠制造系統(tǒng)中的J輛AGV小車實(shí)現(xiàn)單元間移動(dòng)并進(jìn)行跨單元操作，同時(shí)結(jié)合無儲存條件，當(dāng)物料被送至指定設(shè)備時(shí)，如設(shè)備上仍有零件在加工，則物料需暫存在AGV小車上，直到設(shè)備上的零件加工完為止。在單元制造系統(tǒng)中共有H個(gè)多技能員工加工制造系統(tǒng)中的半自動(dòng)設(shè)備，不同員工的技能水平不同，不同員工操作相同設(shè)備上的同種零件所需時(shí)間不同，為了節(jié)約人力資源成本，允許員工操作不同單元內(nèi)的不同設(shè)備。

1.1模型假設(shè)及變量設(shè)定

為了簡化模型的復(fù)雜程度，本文提出的目標(biāo)規(guī)劃模型基于以下假設(shè)：①系統(tǒng)最初所有的設(shè)備、AGV小車和員工都處于等待工作狀態(tài)；②零件只能按一條加工路線進(jìn)行加工，且加工順序?yàn)橐阎?；③零件在設(shè)備上加工的時(shí)間、零件設(shè)備單元?jiǎng)澐?、零件的交貨時(shí)間等基本信息是已知的；④每臺設(shè)備和AGV小車加工或運(yùn)輸工件都是非中斷非搶占式的；⑤每種設(shè)備均只有一臺，但是AGV小車有若干臺；⑥員工操作設(shè)備的基本信息為已知；⑦零件需要在不同單元操作時(shí)，需考慮零件的搬運(yùn)時(shí)間，但單元內(nèi)的搬運(yùn)時(shí)間忽略不計(jì)；⑧需要考慮操作人員在單元間的走動(dòng)時(shí)間，但單元內(nèi)的走動(dòng)時(shí)間忽略不計(jì)；⑨零件在半自動(dòng)設(shè)備上操作需要員工的輔助配合；⑩不考慮設(shè)備的故障問題。

1.2數(shù)學(xué)模型

1.2.1目標(biāo)函數(shù)分析

結(jié)合調(diào)度問題的一般要求以及多資源調(diào)度問題的特點(diǎn)，本文問題包含四部分目標(biāo)。

第一部分為調(diào)度的基本目標(biāo)，總延期時(shí)間最小，即

(1)

式中，w1為第一個(gè)目標(biāo)函數(shù);Fp為零件p的完工時(shí)間；Dp為零件p的交貨時(shí)間；P為零件總數(shù)。

第二部分為人員目標(biāo)，所需的加工人員最少，即

(2)

式中，w2為第二個(gè)目標(biāo)函數(shù);H為目前員工總數(shù);zh表示第h個(gè)員工是否有生產(chǎn)任務(wù)，zh=1表示員工h有生產(chǎn)任務(wù)，否則zh=0。

加工人員越少，則企業(yè)投入的成本越小。

第三部分同為人員目標(biāo)，員工在單元間移動(dòng)次數(shù)最少，即

(3)

從人的因素考慮，員工在單元間移動(dòng)次數(shù)越少，對跨單元調(diào)度的影響就越小，員工的勞動(dòng)強(qiáng)度也隨之下降。

第四部分為AGV小車的使用量最小，即

(4)

式中，w4為第四個(gè)目標(biāo)函數(shù);sj為AGV小車j是否有運(yùn)輸任務(wù)，sj=1表示AGV小車j有生產(chǎn)任務(wù)，否則sj=0;J為AGV小車的總數(shù)。

1.2.2約束條件分析

結(jié)合調(diào)度一般約束及多資源調(diào)度的特點(diǎn)，本文從以下5個(gè)方面設(shè)定相應(yīng)的約束條件。

(1)選擇約束(操作人員及運(yùn)輸設(shè)備的選擇約束)。任何零件的任何工序都必須選擇一個(gè)人來進(jìn)行操作，對于全自動(dòng)設(shè)備而言，不需要員工的輔助操作，在此雖然安排了人員操作，但是其操作時(shí)間為0，故對員工的調(diào)度沒有任何影響，因此有

(5)

如果某個(gè)零件前后所需設(shè)備不在同一單元，則必須選擇一臺AGV小車對該零件進(jìn)行單元間的移動(dòng)，因此有

(6)

?p,o=1,2,…,Op-1

式中，xpoh、ypoj、zpom均為0-1變量，xpoh=1表示零件p的工序o由工人h操作，否則為0；ypoj=1表示零件p的工序o完成后由AGV小車j來進(jìn)行單元間的運(yùn)輸，否則為0；zpom=1表示零件p的工序o需要在設(shè)備m上加工，否則為0；Op為零件p的工序數(shù)。

(2)操作時(shí)間的約束(零件不同時(shí)間的確定)員工開始操作具體零件工序的時(shí)間

(7)

零件某道工序結(jié)束的時(shí)間

(8)

?p，o，m

零件所有工序加工完成的時(shí)間

(9)

(3)操作順序約束(零件前后工序操作及運(yùn)輸順序的約束)。零件后一道工序開始加工的時(shí)間必須大于等于前一道工序開始加工的時(shí)間與設(shè)備加工時(shí)間、員工加工時(shí)間以及零件移動(dòng)時(shí)間之和,因此有

(10)

?p,o,m,m′

如果零件的某道工序結(jié)束后需要應(yīng)用AGV小車運(yùn)輸，則其開始運(yùn)輸?shù)臅r(shí)間必須大于等于該零件的該道工序結(jié)束時(shí)間才能進(jìn)行，因此有

(11)

?p,o,m,m′,j

當(dāng)AGV小車將零件運(yùn)至指定設(shè)備后，需要該設(shè)備上前一零件加工完才算運(yùn)輸結(jié)束，此約束考慮設(shè)備堵塞對AGV小車運(yùn)輸?shù)挠绊?，因此?/p>

(12)

?p,o,p′,o′,m,j

(4)能力約束(設(shè)備、人員及AGV小車的能力約束)。在同一時(shí)間任何一臺設(shè)備、人員和AGV小車只能操作或運(yùn)輸一個(gè)零件，因此有

(13)

?p,o,p′,o′,m

(14)

?p,o,p′,o′,m

(15)

?p,o,p′,o′,j

式中，ypop′o′h=1表示員工h先操作零件p的工序o，再操作p′的工序o′，否則為0；zpop′o′j=1表示AGV小車j在零件p的工序o操作完后先運(yùn)輸零件p，然后在p′的工序o′操作完后運(yùn)輸零件p′，否則為0；tHT為人員在單元間的移動(dòng)時(shí)間；B為無窮大的數(shù)。

(5)變量的邏輯及取值約束如下：

(16)

(17)

1.2.3目標(biāo)規(guī)劃模型

在企業(yè)實(shí)際調(diào)度中，有時(shí)并不需要所有目標(biāo)達(dá)到最優(yōu)效果，而是根據(jù)實(shí)際能力來確定具體的要求，故上述模型可以轉(zhuǎn)化為目標(biāo)規(guī)劃模型，假設(shè)零件超期交貨的總時(shí)間不得超過G1，員工人數(shù)不得超過G2，員工在單元間的移動(dòng)次數(shù)不得超過G3，AGV小車數(shù)量不得超過G4，則上述的目標(biāo)函數(shù)可以轉(zhuǎn)化為目標(biāo)約束：

(18)

(19)

(20)

(21)

在上述目標(biāo)中，第一部分與零件的生產(chǎn)時(shí)間有關(guān)；第二部分和第三部分與員工有關(guān)；第四部分與AGV小車的運(yùn)作有關(guān)，則目標(biāo)規(guī)劃模型可以轉(zhuǎn)換為

(22)

其中，p1、p2、p3為不同目標(biāo)的權(quán)重值。假設(shè)p1?p2?p3，即表示首先要求滿足零件交貨目標(biāo)，在滿足該目標(biāo)的基礎(chǔ)上再求解滿足目標(biāo)人員目標(biāo)，最后考慮AGV小車數(shù)量目標(biāo)。

2 基于改進(jìn)分散搜索法的多目標(biāo)規(guī)劃模型求解

分散搜索(scatter search, SS)法[15]是一種求解整數(shù)規(guī)劃的啟發(fā)式算法，后來其應(yīng)用范圍逐步擴(kuò)展到求解組合優(yōu)化、非線性優(yōu)化及排列等問題，并收到了較好的效果。分散搜索算法是一種基于種群進(jìn)化的算法，其主要步驟包括：產(chǎn)生多樣性的初始解、參考解集的更新、子集的產(chǎn)生以及子集合并和解的改進(jìn)。

針對上文建立的數(shù)學(xué)模型，本文采用改進(jìn)分散搜索(advanced scatter search，ASS)法進(jìn)行問題的求解，與傳統(tǒng)分散搜索法的區(qū)別主要在于：①運(yùn)用遺傳算法來代替以往的子集生成和合并，直接對參考集中的解進(jìn)行交叉和變異，產(chǎn)生新解；②在解的改進(jìn)中，通過采用模式搜索算法，對產(chǎn)生的新解進(jìn)行局部搜索，加快收斂的速度。改進(jìn)后的算法流程如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flow chart

為了更好地說明算法的具體過程，本文首先提出一個(gè)簡單的多資源跨單元調(diào)度問題，假設(shè)有5種零件需要在2個(gè)單元的6種設(shè)備上加工，部分零件需要在2個(gè)單元間來回加工，需用3輛AGV小車來運(yùn)輸，具體相關(guān)的數(shù)據(jù)關(guān)系見表1和表2。

表1 設(shè)備單元?jiǎng)澐旨傲慵に囘^程表

注：M表示設(shè)備， P表示零件。表中數(shù)字表示零件某道工序所需的設(shè)備時(shí)間，如P1行M2列所對應(yīng)的數(shù)據(jù)1(15)表示零件1的第一道工序需要設(shè)備M2，所需的時(shí)間為15 min。K1和K2表示兩個(gè)不同的制造單元。

表2 員工操作設(shè)備技能一覽表

注： H表示員工，表內(nèi)數(shù)據(jù)表示員工操作設(shè)備的時(shí)間，min。因?yàn)槿詣?dòng)設(shè)備不需要員工的輔助工作，所以員工操作機(jī)器手的時(shí)間為0。

圖2 編碼Fig.2 Coding

第一層中的2-3-1-3-4-5-1-4-3-5-2-4-2-

3-1-4-5-1-3表示零件在設(shè)備上的排序，從P2零件的第一道工序開始加工，最后加工的是P3零件的第5道工序。第二層的人員和第三層的AGV小車分配與第一層的零件工序相對應(yīng)，第二層h箭頭指向的數(shù)字為4，表示零件P3的第1道工序由第4個(gè)員工操作。如果該工序是由全自動(dòng)設(shè)備操作的，則可以設(shè)定該工人操作此工序的時(shí)間為0，從而符合調(diào)度模型的基本假定。第三層j箭頭所指向的數(shù)字1表示P3零件的第一道工序完成后，如果需要單元間移動(dòng)則選擇1號AGV小車 ，如果不需要單元間轉(zhuǎn)移，雖然選擇了AGV小車，但由式(10)可知，其運(yùn)輸時(shí)間不計(jì)入零件的整個(gè)運(yùn)作時(shí)間內(nèi)。

(2)產(chǎn)生多樣性解。多樣性解是指解集分布的均勻性和廣泛性，可以采取隨機(jī)的方式產(chǎn)生多樣性解，但是本文為了提高多樣性的程度，通過設(shè)置閾值來控制多樣性，從而避免產(chǎn)生的解過于集中。本文通過計(jì)算新入個(gè)體與已有群體內(nèi)個(gè)體的歐氏距離是否超過閾值來判斷該個(gè)體是否能夠加入種群，從而使得種群中的個(gè)體始終保持一定的距離。歐氏距離

(23)

其中，dT為新個(gè)體與種群中第j個(gè)個(gè)體的距離；N為新產(chǎn)生的個(gè)體；Qj為已有種群中第j個(gè)個(gè)體。

當(dāng)所有的dT≥Ta時(shí)，接受該新個(gè)體，其中Ta為閾值，可以是固定值，也可以是動(dòng)態(tài)值，但是根據(jù)文獻(xiàn)[16]的實(shí)驗(yàn)，動(dòng)態(tài)閾值并沒有獲得較好的效果，因此本文采用固定閾值。

(3)個(gè)體目標(biāo)函數(shù)值的計(jì)算。根據(jù)模型目標(biāo)函數(shù)計(jì)算個(gè)體的目標(biāo)函數(shù)：

(24)

(4)建立初始參考集。在分散搜索算法中，參考集由兩部分子集組成，第一部分為高質(zhì)量解集Set1，第二部分為多樣性解集Set2。對于高質(zhì)量解集，只要計(jì)算解集中個(gè)體的目標(biāo)函數(shù)，并根據(jù)目標(biāo)函數(shù)值的優(yōu)劣進(jìn)行排序，在T個(gè)個(gè)體中選擇a個(gè)最優(yōu)的進(jìn)入高質(zhì)量解集Set1。對于初始多樣性解子集，首先在剩余初始解T-a個(gè)個(gè)體中選擇與高質(zhì)量解集中個(gè)體歐氏距離之和最大的個(gè)體放入多樣性解集Set2中，然后在剩余的個(gè)體中選擇一個(gè)與現(xiàn)有Set1和Set2集合中個(gè)體歐氏距離之和最大的個(gè)體放入Set2中，重復(fù)此過程直到選擇b個(gè)個(gè)體填充Set2集為止。

(5)產(chǎn)生新解。在分散搜索法中，一般采用子集合并的方法來產(chǎn)生新解，本文采用遺傳算法產(chǎn)生新解，具體步驟如下：①根據(jù)輪盤賭選擇法分別在高質(zhì)量解集Set1和多樣性解集Set2中選擇一個(gè)體分別作為父代和母代；②根據(jù)一定的交叉率Pc對個(gè)體進(jìn)行交叉，產(chǎn)生新的染色體；③根據(jù)一定的交叉率Pm對個(gè)體進(jìn)行變異，產(chǎn)生新的染色體。

(6)解的改進(jìn)。解的改進(jìn)主要是對產(chǎn)生的多樣性解集采用局部搜索的方法進(jìn)行改進(jìn)，本文采用模式搜索(pattern search，PS)的方法改進(jìn)解，根據(jù)目標(biāo)函數(shù)進(jìn)行判斷，當(dāng)改進(jìn)解的目標(biāo)函數(shù)更優(yōu)時(shí)，則用新解代替原有解；反之，則仍使用原有解。

模式搜索作為動(dòng)態(tài)排序算法(dynamic sorted algorithm，DS)中的一種，主要是借助模式向量在當(dāng)前點(diǎn)周圍產(chǎn)生一組網(wǎng)格，如果在這些網(wǎng)格點(diǎn)中找到一個(gè)新點(diǎn)使目標(biāo)函數(shù)值得以改善，則下一步迭代將以新點(diǎn)作為當(dāng)前點(diǎn)。其基本算法步驟如下：①確定初始點(diǎn)并計(jì)算其目標(biāo)函數(shù)。②產(chǎn)生網(wǎng)格點(diǎn)。網(wǎng)格點(diǎn)產(chǎn)生的方法是在當(dāng)前點(diǎn)處加上m倍的模式向量，m為網(wǎng)格尺寸。③評價(jià)目標(biāo)函數(shù)，如果發(fā)現(xiàn)某一網(wǎng)格點(diǎn)的函數(shù)值優(yōu)于當(dāng)前點(diǎn)，則接受該網(wǎng)格點(diǎn)為新的當(dāng)前點(diǎn)，并將網(wǎng)格尺寸擴(kuò)大m倍，否則當(dāng)前點(diǎn)不變，并將網(wǎng)格尺寸收縮1/m，m可根據(jù)實(shí)際情況而定。④重復(fù)步驟②和③，直到滿足迭代終止條件。

本節(jié)僅通過模式搜索方法進(jìn)行解的優(yōu)化，因此其終止條件只需滿足迭代次數(shù)即可，為了減少算法的計(jì)算時(shí)間，迭代次數(shù)不宜過多，一般取2～3次。

(7)更新參考集。更新參考集是在現(xiàn)存參考集和改進(jìn)后的新解中選擇a個(gè)高質(zhì)量的解，而對于多樣性解的選擇，除考慮多樣性外，還需兼顧其目標(biāo)函數(shù)值。本文設(shè)置一個(gè)閾值Tc，在現(xiàn)存參考集和改進(jìn)后的解集中去除a個(gè)高質(zhì)量解后，計(jì)算剩余解的目標(biāo)函數(shù)值，將目標(biāo)函數(shù)值超過閾值Tc的解按照多樣性優(yōu)劣排列，選擇多樣性最好的b個(gè)解作為多樣性解集，從而將新解中優(yōu)質(zhì)和多樣性的解加入到參考集中，剔除現(xiàn)存參考集中質(zhì)量和多樣性最差的解。

(8)算法終止準(zhǔn)則。本文采用參考集收斂作為算法終止的標(biāo)準(zhǔn)，也就是當(dāng)參考集中的個(gè)體連續(xù)t代沒有發(fā)生變化時(shí)，算法終止，t≥2。

3 算法實(shí)驗(yàn)及算例分析

3.1算法比較

由于上述模型與前人研究具有一定差異，沒有相似的標(biāo)桿數(shù)據(jù)進(jìn)行對比分析，故將本文所提的改進(jìn)分散搜索算法(ASS)與遺傳算法(GA)、分散搜素算法(SS)對不同規(guī)模的8個(gè)算例進(jìn)行比較分析，應(yīng)用MATLAB語言編程實(shí)現(xiàn)，并在Thinkpad X250計(jì)算機(jī)(運(yùn)行內(nèi)存4G)上實(shí)現(xiàn)8個(gè)算例的求解，具體可見表3。

表3 算例求解信息

應(yīng)用改進(jìn)分散搜索算法、遺傳算法以及分散搜索算法對8個(gè)算例分別求解，最終結(jié)果如表4所示，三種算法在最優(yōu)解及運(yùn)行時(shí)間方面的比較可見圖3、圖4。從表4可以看出，對于規(guī)模較小的算例，如算例1～算例3，三種算法所得結(jié)果是相同的，但是運(yùn)行時(shí)間上，改進(jìn)搜索算法要優(yōu)于后兩種算法。隨著算例規(guī)模的不斷擴(kuò)大，改進(jìn)搜索算法的最優(yōu)解明顯優(yōu)于后兩種算法，而所需運(yùn)行時(shí)間的差距也逐步擴(kuò)大。由此可以證明，改進(jìn)搜索算法在最優(yōu)解獲取方面以及運(yùn)算時(shí)間方面都要優(yōu)于遺傳算法和分散搜索算法。

表4中，PD為零件延遲時(shí)間；NW為所需工人數(shù)量；NC為所需AGV小車數(shù)量；RT為運(yùn)行時(shí)間。算例1、算例2由于規(guī)模較小，故設(shè)置的個(gè)體集T和參考集的數(shù)量均較小，Set1和Set2均為10，而算例3～算例8的規(guī)模較大，故參考集的數(shù)量設(shè)置為25。

表4 三種不同算法結(jié)果比較

3.2算例分析

3.2.1算例1結(jié)果

本節(jié)根據(jù)算例1所得結(jié)果進(jìn)行詳細(xì)分析。算例1相關(guān)參數(shù)見表1、表2和表5，具體運(yùn)算結(jié)果的甘特圖見圖5，從中可知不同零件各工序在不同設(shè)備上的操作順序，以及不同設(shè)備具體操作人員的工作安排。

圖5中H1，H2，H3為員工；M1，M2，…，M6為設(shè)備，其中M3和M5是全自動(dòng)設(shè)備；P為零件，PX-Y則表示零件PX的第Y道工序。

3.2.2人員對調(diào)度的影響分析

根據(jù)算例1的結(jié)果可知，員工有5次跨單元操作，關(guān)鍵在于H1操作M1和M4的時(shí)間較短，從而能夠滿足零件的交貨時(shí)間。根據(jù)表2可知，如果由H3操作M1，則每次操作所需時(shí)間為10 min，遠(yuǎn)遠(yuǎn)超過了H1操作的5 min。這樣的安排雖然移動(dòng)次數(shù)減少了，但零件的完工時(shí)間會超過110 min的要求，如果讓H4操作M1，此安排不僅會延遲零件的完工時(shí)間，也增加了員工人數(shù)。這些都直接說明了工人跨單元操作及任務(wù)分配對零件加工周期的影響。

(a)PD

(b)NW

(c)NC圖3 三種算法不同算例計(jì)算結(jié)果比較Fig.3 The example results comparisonunder three algorithms

圖4 三種算法不同算例運(yùn)行時(shí)間比較Fig.4 The running time comparison under three algorithms

AGV單元間運(yùn)輸時(shí)間(min)3員工單元間移動(dòng)時(shí)間(min)5零件交貨時(shí)間(min)110G10G23G33G42

圖5 零件操作順序甘特圖Fig.5 The Gantt chart of operation sequence

AGV小車序號運(yùn)輸零件起始位置終點(diǎn)位置運(yùn)輸起始時(shí)間(min)運(yùn)輸終止時(shí)間(min)零件在小車上等待至(min)運(yùn)輸后所在單元1P5M6M3212430C11P2M1M4303346C21P4M4M1464953C12P5M3M5454876C21P2M4M26770C12P3M2M57679C21P1M3M66568C21P4M1M6778089C2

如果將目標(biāo)函數(shù)改為

即首先保證第二和第三部分目標(biāo)的要求，然后考慮第一和第四部分目標(biāo)，則整個(gè)調(diào)度方案就會有微小的變化。此時(shí)為了首先保證人員目標(biāo)，由H3操作M1和M2， H1操作M4，H2操作M6，員工人數(shù)仍然滿足既定要求，而員工跨單元操作數(shù)量為0，同樣滿足要求，但是零件完工的最晚時(shí)間變?yōu)?15 min，超過了既定要求。

3.2.3 AGV小車對調(diào)度的影響分析

根據(jù)表6可知， AGV小車的任務(wù)分配滿足了零件加工在時(shí)間上的要求。根據(jù)模型要求考慮了設(shè)備堵塞的問題，如1號AGV小車在將P4零件從C2的M4運(yùn)至C1的M1的時(shí)間(49 min)，但是由于此時(shí)M1上還在加工零件P3，所以P4零件在小車上等待至P3加工完為止，也就是到53 min時(shí)，1號小車才可以使用，而在45 min時(shí)，M3上的P5必須運(yùn)走，否則會影響P1-2的操作，故此時(shí)采用2號AGV小車進(jìn)行運(yùn)輸。

假設(shè)目前企業(yè)只有1輛AGV小車，并改變目標(biāo)函數(shù):

而G4=1，則整個(gè)人員安排以及操作時(shí)間都將有所變化，具體可見表7及圖6所示?？梢钥闯?，此時(shí)由H1操作設(shè)備M1，H3操作設(shè)備M2，H2操作設(shè)備M6和M4，而H1只操作P3-5在M4上的加工，主要原因是只有1輛AGV小車進(jìn)行零件運(yùn)輸，導(dǎo)致設(shè)備堵塞，故讓H2操作M4設(shè)備，雖然操作時(shí)間增加，但是部分時(shí)間可與設(shè)備堵塞時(shí)間相抵消，另一方面也減少了員工的移動(dòng)次數(shù)，所以AGV的任務(wù)安排也在一定程度上影響了人員的安排。由H1操作P3-5主要是考慮人員在同一時(shí)刻只能加工一個(gè)產(chǎn)品，若由H2操作P3-5會導(dǎo)致P4-4的完工時(shí)間達(dá)到120 min，故該處增加了人員操作的一次移動(dòng)。按照該調(diào)度方案，除了P4的加工時(shí)間比規(guī)定的時(shí)間延遲了7 min外，其他情況都符合目標(biāo)規(guī)劃的要求。

表7 AGV小車運(yùn)輸過程(1輛AGV小車)

圖6 零件操作順序甘特圖(1輛AGV小車)Fig.6 The Gantt chart of operation sequence(1 AGV)

4 結(jié)語

本文基于各種資源的特點(diǎn)以及在制造系統(tǒng)中的作用，在以往研究基礎(chǔ)上，提出了多資源跨單元操作的調(diào)度問題，建立了相應(yīng)的數(shù)學(xué)模型，應(yīng)用改進(jìn)分散搜索法求解模型，并應(yīng)用于不同規(guī)模的8個(gè)案例中，在時(shí)間和求解結(jié)果方面都獲得了較好的效果。

本文為了多資源跨單元調(diào)度問題的簡化，假設(shè)每種零件只有一條加工工藝路徑，且每一種設(shè)備類型均只有一臺，這在一定程度上限制了模型在實(shí)際問題中的應(yīng)用范圍，因此在后續(xù)研究中，將進(jìn)一步研究多工藝路徑及員工流動(dòng)環(huán)境下的多資源跨單元調(diào)度問題，進(jìn)一步拓展單元調(diào)度問題的內(nèi)涵。

[1] 于洋, 查建中, 牟建斌. 單元制造技術(shù)及其實(shí)施方法[J]. 制造業(yè)自動(dòng)化, 2001, 13(4): 4-6.

YU Yang,ZHA Jianzhong, MOU Jianbin. Introduction and Implementation of Cellular Manufacturing [J]. Manufacturing Automation, 2001, 13(4): 4-6.

[2] 王躍崗，車阿大. 基于混合量子進(jìn)化算法的自動(dòng)化制造單元調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng), 2013,19(9): 2193-2201.

WANG Yuegang, CHE Ada. Robotic Cells Scheduling Based on Hybrid Quantum Evolutionary Algorithm [J]. Computer Integrated Manufacturing Systems, 2013,19(9): 2193-2201.

[3] 韓文民, 吳滿成, 王潔, 等.考慮批量分割的虛擬單元調(diào)度研究[J]. 制造業(yè)自動(dòng)化, 2015,37(8):14-20.

HAN Wenmin,WU Mancheng, WANG Jie, et al. Research on Lot-streaming in Virtual Manufacturing Cellular Scheduling [J]. Manufacturing Automation, 2015,37(8):14-20.

[4] KARTHIKEYAN S, SARAVANAN M, GANESH K. GT Machine Cell Formation Problem in Scheduling for Cellular Manufacturing System Using Meta-heuristic Method[J]. Procedia Engineering, 2012, 38(5):2537-2547.

[5] 李冬妮, 肖廣雪, 王妍, 等. 一種柔性路徑下的跨單元調(diào)度方法[J]. 自動(dòng)化學(xué)報(bào), 2012, 38(6): 969-975.

LI Dongni, XIAO Guangxue, WANG Yan, et al. An Intercell Scheduling Approach Considering Flexible Processing Routes [J]. Acta Automatica Sinica, 2012, 38(6): 969-975.

[6] 賈凌云, 李冬妮, 田云娜. 基于混合蛙跳和遺傳規(guī)劃的跨單元調(diào)度方法[J]. 自動(dòng)化學(xué)報(bào), 2015, 41(5):936-948.

JIA Lingyun, LI Dongni, TIAN Yunna. An Intercell Scheduling Approach Using Shuffled Frog Leaping Algorithm and Genetic Programming [J]. Acta Automatica Sinica, 2015, 41(5):936-948.

[7] SOLIMANPUR M, ELMI A. A Tabu Search Approach for Cell Scheduling Problem with Makespan Criterion[J]. International Journal of Production Economics, 2013, 141(2): 639-645.

[8] 季少梅. 柔性路徑下基于混合粒子群算法的跨單元調(diào)度方法[D].北京：北京理工大學(xué), 2011.

JI Shaomei. Hybrid Particle Swarm Optimization Algorithm in Inter Cell Scheduling Problem with Flexible Routes [D]. Beijing: Beijing Institute of Technology, 2011.

[9] MENG X W, JU Y H, WANG X H, et al. An ACO-based Approach for Intercell Scheduling with Various Types of Machines[C]//Proceedings of the 25th Chinese Control and Decision Conference (CCDC). Guiyang, 2013:1812-1817.

[10] PAJOUTAN M, GOLMOHAMMADI A, SEIFARGHY M. CMS Scheduling Problem Considering Material Handling and Routing Flexibility[J]. The International Journal of Advanced Manufacturing Technology, 2014, 72(5/8): 881-893.

[11] 馬帥. 雙系統(tǒng)優(yōu)化及約束作業(yè)車間調(diào)度應(yīng)用研究[D]. 大連：大連理工大學(xué), 2013.

MA Shuai. A Dual-system Optimization Method for Constrained Job Shop Scheduling [D]. Dalian: Dalian University of Technology, 2013.

[12] 劉旭, 樓佩煌, 錢曉明, 等. 基于改進(jìn)遺傳算法的物料配送多AGV 調(diào)度優(yōu)化[J].機(jī)械設(shè)計(jì)與制造工程, 2015, 44(3):17-22.

LIU Xu, LOU Peihuang, QIAN Xiaoming, et al. Scheduling of Automated Guided Vehicles for Material Distribution Based on Improved Genetic Algorithm [J]. Machine Design and Manufacturing Engineering, 2015, 44(3):17-22.

[13] NISHI T, HIRANAKA Y, GROSSMANN I E. A Bi-level Decomposition Algorithm for Simultaneous Production Scheduling and Conflict-free Routing for Automated Guided Vehicles[J]. Computers and Operations Research, 2011, 38(5):876-888.

[14] FAN Jiajing, FENG Dingzhong. Design of Cellular Manufacturing System with Quasi Dynamic Dual Resource Using Multi-objective GA[J]. International Journal of Production Research, 2013, 51(14):4134-4154.

[15] GLOVER F. Heuristics for Integer Programming Using Surrogate Constraints [J]. Decision Science, 1977, 8: 156-166.

[16] 劉衍民, 趙慶禎, 邵增珍. 一種自適應(yīng)多樣性保持的多目標(biāo)粒子群算法[J]. 濟(jì)南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2011, 25(3): 296-300.

LIU Yanmin, ZHAO Qingzhen, SHAO Zengzhen. Multi-objective Particle Swarm Optimizer with Adaptive Diversity Maintenance [J]. Journal of University of Jinan (Science and Technology), 2011, 25(3): 296-300.

(編輯王旻玥)

StudyonMulti-resourceIntercellularSchedulingProblemBasedonASSAlgorithm

FAN Jiajing1CAO Yuhua1CAO Min2

1.School of Economics and Management,Hangzhou,Zhejiang University of Science and Technology,Hangzhou,310023 2.School of Mechanical amp; Automotive Engineering，Zhejiang University of Science and Technology,Hangzhou,310023

An intercellular scheduling problem based on multi-resource constraint was put forward considering the characteristics and important roles of equipment, human resources and AGVs in cellular manufacturing system. Aiming at minimum sum of part late delivery times, the numbers of employee and intercellular moving times and the numbers of AGV, a goal programming mathematical model was built. An ASS algorithm was presented to solve this model according to the model particularity. In the ASS algorithm, a genetic algorithm was used to get the new solution sets and the pattern search(PS) was used to improve the reference solution sets to enhance the rate of convergence. The mathematical model and algorithm were applied into 8 different size examples to prove validity of the model and algorithm. At last, the interactions of equipment, human resource and AGV were explained based on the analyses of the examples.

intercellular; scheduling; multi-resource; advanced scatter search(ASS) algorithm

TH166

10.3969/j.issn.1004-132X.2017.22.012

2016-10-17

范佳靜，女，1977年生。浙江科技學(xué)院經(jīng)濟(jì)與管理學(xué)院副教授、博士。主要研究方向?yàn)閱卧圃煜到y(tǒng)的構(gòu)建、調(diào)度。出版專著1部，發(fā)表論文10余篇。 E-mail：carole_cn@163.com。曹玉華，女，1976年生。浙江科技學(xué)院經(jīng)濟(jì)與管理學(xué)院講師。曹敏，女，1965年生。浙江科技學(xué)院機(jī)械與汽車工程學(xué)院教授。