楊江波，陳友玲，曹 楠

重慶大學 機械工程學院，重慶 400044

面向柔性作業(yè)分布式車間的分層調(diào)度模型研究

楊江波，陳友玲，曹 楠

重慶大學 機械工程學院，重慶 400044

1 引言

隨著當前市場環(huán)境的變化，制造業(yè)的生產(chǎn)模式已經(jīng)開始從少品種、大批量生產(chǎn)轉(zhuǎn)向多品種、小批量的生產(chǎn)，生產(chǎn)調(diào)度的優(yōu)化作為減少企業(yè)生產(chǎn)成本、提高資源利用率的重要手段，一直受到國內(nèi)外相關學者的廣泛關注。柔性分布式車間作業(yè)系統(tǒng)將過去集中式的生產(chǎn)準備、計劃和控制改為分布式，將權(quán)利下放給車間，以人為本，責權(quán)分明，使生產(chǎn)過程變得更加高效[1]。而隨之而來的則是生產(chǎn)系統(tǒng)的調(diào)度問題變得更加復雜，因此迫切需要研究新的調(diào)度方法來解決此類調(diào)度的優(yōu)化問題。

由于在實際的車間調(diào)度中，車間調(diào)度往往是分層進行的[2]，因此，如何將柔性分布式車間調(diào)度進行合理分層以求得最終決策目標的優(yōu)化，是進一步研究的關鍵。目前國內(nèi)外學者對分布式車間的調(diào)度問題研究得相對較少，Jia等[3]研究了分布式車間調(diào)度的特點，使用傳統(tǒng)遺傳算法進行求解；蘇生等[4]分析了遺傳算法在處理組合優(yōu)化問題的局限性，提出改進遺傳算法求解多車間調(diào)度問題；張曉東等[5]建立了生產(chǎn)計劃和調(diào)度的集成優(yōu)化模型，提出基于遺傳算法的啟發(fā)式算法進行求解；同時，已有相關學者將層次分析法應用于制造系統(tǒng)優(yōu)化過程中，并取得了一定的成果，姚錫凡等[6]以生產(chǎn)計劃、調(diào)度與控制集成為例，提出了基于目標級聯(lián)法和IPDI原則的集成制造系統(tǒng)多層次優(yōu)化模型；韓文民等[7]研究了單元生產(chǎn)環(huán)境中零部件生產(chǎn)工藝不相同的情況，采用分級調(diào)度算法對該問題進行研究；而黃英杰等[8]在分析了目標級聯(lián)法可并行優(yōu)化、級數(shù)不受限制等優(yōu)點的基礎上，建立了一種帶層次性的車間調(diào)度模型，證明了目標級聯(lián)法在處理可分層調(diào)度問題上的優(yōu)越性。

本文根據(jù)柔性作業(yè)制造系統(tǒng)資源以及設備等分布多個車間生產(chǎn)的特點，提出一種基于目標級聯(lián)法的分級調(diào)度模型，利用目標級聯(lián)法具有分解目標的特點，結(jié)合遺傳算法搜索全局最優(yōu)解的能力來解決柔性分布式車間調(diào)度問題，調(diào)度過程既實現(xiàn)了單車間的調(diào)度時間最小，同時實現(xiàn)多車間的協(xié)同調(diào)度達到總體最優(yōu)。

2 柔性分布式車間調(diào)度問題描述

柔性分布式車間作業(yè)系統(tǒng)是在成組技術基礎上發(fā)展起來的一個由多個功能獨立、地理位置分散的獨立制造島組成的新型生產(chǎn)形式[9]。柔性分布式車間系統(tǒng)的作業(yè)計劃是在滿足某些約束（如完工時間、工藝路線等）條件的基礎上對零件以及操作工序的排序，按照排序分配資源和時間，使得某個決策目標最優(yōu)。分布式車間作業(yè)系統(tǒng)的具體特點如下：

（1）每臺機器可完成若干個加工操作，不同機器可加工操作不完全相同，不同機器進行相同操作所用時間也不完全相同，各機器所在的地理位置不完全相同。

（2）零件按照一定的工藝路徑進行加工。

（3）每個工件的一個工序均可由一臺機器單獨加工完成，由于各道工序受技術上的約束，必須按某一特定順序進行。

（4）運輸成本等折合在加工成本中，運輸時間加在總時間內(nèi)。

（5）假設所有工件均可在調(diào)度前獲得。

3 目標層解法

目標級聯(lián)法簡稱TC法（Target Cascading），又稱為ATC法（Analytical Target Cascading），1999年由美國Michigan大學的Michelena、Kim和Papalambros等人提出，是一種用于解決非集中式、層次結(jié)構(gòu)協(xié)調(diào)問題的一種新方法[10]，它在消除了復雜的系統(tǒng)分析的同時，保證了各個子系統(tǒng)的并行優(yōu)化，因此常被應用于解決大規(guī)劃的系統(tǒng)優(yōu)化問題。它允許結(jié)構(gòu)中各層次元素自主決策，父代元素對子代元素的決策進行協(xié)調(diào)優(yōu)化而獲得整體最優(yōu)解[11]。ATC通常包含兩級：系統(tǒng)級和分析級；系統(tǒng)級負責元素目標的優(yōu)化，分析級負責計算元素的反映值。局部設計變量、子代元素的反映值和參數(shù)為其輸入，而傳遞給系統(tǒng)優(yōu)化級的反映值為其輸出。圖1所示為ATC優(yōu)化模型中元素Pij的原理圖，父代系統(tǒng)將Pij的優(yōu)化目標和協(xié)調(diào)變量傳遞下來，優(yōu)化過程結(jié)束后，把響應變量和聯(lián)系變量的值回傳給父代系統(tǒng)，同時將下傳給子代系統(tǒng)，并作為子代系統(tǒng)P(i+1)j的優(yōu)化目標和協(xié)調(diào)變量。為輸入，Rij為輸出，過程如圖1所示。

圖1 ATC優(yōu)化原理圖

規(guī)劃過程中，只要確定系統(tǒng)級的性能指標或目標值，其下層分析級的指標或目標值將由逐層轉(zhuǎn)換得到。目標值的轉(zhuǎn)換過程是一個由上至下層層分解的過程，該過程要求各層之間以及同層元素之間能夠在一定的范圍內(nèi)相互協(xié)調(diào)，如果所有目標值均達到要求，那么整個系統(tǒng)目標就獲得了優(yōu)化[12]。因此，可以認為生產(chǎn)計劃其實是一個將目標分解的過程，其目標是：在一定的條件約束下，將計劃層的總體目標集進行分解，使其成為若干子目標集映射到執(zhí)行層，求解得到局部目標最優(yōu)，然后對求解的結(jié)果進行協(xié)調(diào)。這樣，生產(chǎn)計劃和調(diào)度的過程就演變成目標分解—子目標求解—各目標協(xié)調(diào)的迭代過程。分層調(diào)度過程如圖2示。

圖2 ATC分層調(diào)度過程示意圖

4 柔性分布式車間分層調(diào)度模型

柔性分布式車間調(diào)度模型是圍繞一批訂單在N個柔性制造車間加工的任務來進行，這批訂單中有M個零件要加工，訂單中每個零件可以在這N個制造車間中任一個加工[13]。因為不同車間加工的環(huán)境、設備的加工性能都不一樣，使得零件在不同車間中的加工時間也不同，因此，調(diào)度系統(tǒng)的任務就是要根據(jù)零件的加工要求以及車間機器的加工性能來確定零件的加工車間，然后在車間中根據(jù)零件的加工時間和工藝約束來規(guī)劃車間內(nèi)零件的最佳加工路線。調(diào)度模型的目標是訂單所有零件的總加工時間最短，其中N個車間中最后完工車間的零件加工完成時間為總體的加工完成時間。

柔性分布式作業(yè)車間的分層調(diào)度是以總體調(diào)度時間最短作為總體目標，通過將生產(chǎn)計劃層的時間分解至車間調(diào)度層再至零件規(guī)劃層，先保證零件規(guī)劃層所用的時間最短，將最短時間作為目標傳至上層，層層之間達到最優(yōu)以實現(xiàn)整體的調(diào)度時間最短。它主要是利用ATC可以解決復雜系統(tǒng)協(xié)同優(yōu)化的思想以及GA能夠進行全局搜索及內(nèi)在的處理并行問題的能力[14]來實現(xiàn)調(diào)度分級后的整體最優(yōu)的目標。根據(jù)ATC的分層思想，將柔性分布式車間調(diào)度問題分為三個層次：（1）生產(chǎn)計劃層；（2）車間調(diào)度層；（3）零件規(guī)劃層。其調(diào)度模型如圖3所示。

4.1 生產(chǎn)計劃層模型

不同的車間調(diào)度問題往往有不同的約束條件，本文以時間為最終決策目標。生產(chǎn)計劃層的任務是以不同的車間為單位，通過協(xié)同調(diào)度使得各車間的加工盡可能同時完成來保證總調(diào)度時間最短，本層的目標值是柔性制造系統(tǒng)最終所能達到的進度，其數(shù)學模型為：

其中，式（1）表示本計劃層制造系統(tǒng)加工完成所用的時間最短；式（2）為生產(chǎn)計劃層的系統(tǒng)反映值，即加工較慢車間的進度值；式（3）表示本層的系統(tǒng)反應允許誤差，是生產(chǎn)計劃層給車間調(diào)度層中B1設定的系統(tǒng)反應，即要求的加工完成時間；是車間調(diào)度層中B1上傳給生產(chǎn)計劃層的系統(tǒng)反映值。式（4）表示設計變量。

4.2 車間調(diào)度層模型

車間調(diào)度層要完成零件的車間分配規(guī)劃，任務是為各個零件合理分配車間以及設備，形成設備集。本層的目標是車間所有零件完工的時間最短，本層的目標值是制造系統(tǒng)內(nèi)每個生產(chǎn)車間所能達到的制造進度。其數(shù)學模型為：

其中，式（5）表示本層制造車間加工完成所用的時間最短；式（6）為車間調(diào)度層的系統(tǒng)反映值，即加工較慢車間的進度值；式（7）表示本層每個車間加工的進度約束；是生產(chǎn)計劃層給車間調(diào)度層中Bi設定的系統(tǒng)反應，即要求的加工完成時間；是車間調(diào)度層中Bi上傳給生產(chǎn)計劃層的系統(tǒng)反映值；式（8）為柔性制造車間的局部設計變量，表示各零件的加工路線。

4.3 零件規(guī)劃層模型

零件規(guī)劃層的任務是安排車間內(nèi)零件加工的工藝路線，使車間中的零件能夠盡快完工。本層的目標是縮短車間內(nèi)每個零件的完工時間，本層的目標值是車間內(nèi)的零件所能達到的制造進度。其數(shù)學模型為：

其中，式（9）表示本層車間內(nèi)零件的完工時間最短；式（10）表示零件的加工進度約束；是車間調(diào)度層給零件規(guī)劃層設定的完工時間，是該層零件的實際完工時間，即該零件給車間調(diào)度層的反映值。

零件的完工時間受加工路線的影響，因此零件規(guī)劃層的任務是為零件選擇合適的加工路線使總的完工時間最短。本文運用遺傳算法，采用基于加工任務的編碼方式，每個染色體由n（任務數(shù)）乘m（工藝數(shù)）個代表加工任務的基因組成，是所有操作的一個排列[15]。解碼時，根據(jù)零件加工的工藝約束不同來安排加工順序，在平衡設備負荷的同時得出完工時間最短的工藝路線，依次加工形成最終的調(diào)度方案。

5 調(diào)度流程及算法求解步驟

圖3 柔性分布式車間作業(yè)分級調(diào)度模型

ATC柔性多車間調(diào)度是一種層次優(yōu)化的過程，生產(chǎn)計劃層通過設定目標值T0給車間調(diào)度層的各個車間設定同時完工策略，車間調(diào)度層給零件規(guī)劃層的各零件設定最小完工時間，在零件規(guī)劃層的優(yōu)化程序完成后，獲得的最小完工時間回傳給車間調(diào)度層，車間調(diào)度層再將各車間的完工時間回傳給生產(chǎn)計劃層，這樣進行不斷迭代，每次迭代下層最優(yōu)的值將作為新目標，直到最后獲得最優(yōu)解。

基于ATC的柔性分布式車間調(diào)度流程如圖4所示，調(diào)度算法主要步驟如下：

為了方便敘述，做如下規(guī)定：

循環(huán)次數(shù)為CN；生產(chǎn)計劃層的進化代數(shù)為VN；X0A為生產(chǎn)計劃層的決定變量；X0B為車間調(diào)度層決定變量；其他出現(xiàn)的符號同前面所提到的含義一致。

（1）預先設定生產(chǎn)計劃層、車間調(diào)度層、零件規(guī)劃層的允許誤差值 ε0、ε1、ε2，車間調(diào)度層傳給生產(chǎn)計劃層的響應值及零件規(guī)劃層傳遞給車間調(diào)度層的響應值同時設定生產(chǎn)計劃層的循環(huán)次數(shù)CN和車間調(diào)度層的進化代數(shù)VN。

（2）在生產(chǎn)計劃層內(nèi)，根據(jù)各車間中零件批量、進度完成快慢的不同情況，設定 X0A（生產(chǎn)計劃層決定變量），X0B（車間調(diào)度層決定變量）。

（3）在車間調(diào)度層內(nèi)，根據(jù)零件的工藝路線及零件在各類機器上的加工時間來初始分配各類加工設備，形成加工設備集，并用基因譜來描述。

（4）在零件規(guī)劃層內(nèi)，生產(chǎn)車間隨機產(chǎn)生n個個體作為初始染色體種群，染色體的位數(shù)由車間內(nèi)零件的種類數(shù)和設備的類型數(shù)來決定。

（5）根據(jù)零件的種類數(shù)和車間內(nèi)的設備類型數(shù)，以盡早完工為準則，對基因進行解碼，計算每個個體的完工時間，將最小的完工時間作為本車間零件層的反應值，判斷零件規(guī)劃層的響應值與進度值之差是否小于給定的誤差或者判斷循環(huán)次數(shù)是否大于給定的循環(huán)次數(shù)，如果是，則取之為最大值。

圖4 基于ATC的柔性分布式車間調(diào)度流程圖

（6）如果不是，則判斷零件規(guī)劃層的某零件的完成時間是否大于給定的響應值，如果是則返回（4）；如果不是則將最大、最小值所在的生產(chǎn)車間內(nèi)零件的染色體進行交叉操作同時將R重新排列并與R最大的單元的染色體進行交叉，完成遺傳操作后重新解碼。

（7）如果（5）成立，判斷車間調(diào)度層的完工時間與進度值之差是否滿足要求或者判斷循環(huán)次數(shù)是否大于給定的循環(huán)次數(shù)，如果是則取R為最大值；如果不是，則判斷遺傳操作是否全部完成或者判斷迭代次數(shù)是否大于給定的次數(shù)，如果是則取R為最大值。如果不是則返回（6）。

（8）如果（7）成立，判斷生產(chǎn)計劃層的完工時間與進度值之差是否滿足要求或者判斷迭代次數(shù)是否大于給定的次數(shù)，如果是則輸出結(jié)果，如果不是則返回（6）。

6 實例分析

本文以三個柔性車間的協(xié)同調(diào)度來說明實際調(diào)度過程。假定在A、B、C三個車間各有5臺機器，分別編號為A1，A2，A3，A4，A5，B1，B2，B3，B4，B5，C1，C2，C3，C4，C5?，F(xiàn)在有一批包括 9個零件的訂單要加工，其加工時間分別如表1所示。

設定算法初始參數(shù)如下：最大迭代次數(shù)CN為200，進化次數(shù)VN取為100，初始種群規(guī)模n為100，交叉概率為0.85。生產(chǎn)計劃層的系統(tǒng)允許反應誤差ε0為1.0，車間調(diào)度層的系統(tǒng)允許反應誤差ε1為0.6，零件規(guī)劃層的系統(tǒng)允許反應誤差ε2取為0.2。經(jīng)算法優(yōu)化后，得到的加工完成時間分別為A車間9 min，B車間10 min，C車間9 min，可知調(diào)度結(jié)果，調(diào)度系統(tǒng)完成這批9個零件的訂單需要花費最小時間為10 min。生產(chǎn)計劃層的染色體為[3322231121]，代表零件7，8和10在A車間中加工；零件3，4，5和9在B車間中加工；零件1，2和6在C車間加工。圖5所示為A車間的甘特圖，圖6所示為B車間的甘特圖，圖7所示為C車間的甘特圖，圖中橫坐標為加工時間，縱坐標為機場類型，而圖中間的數(shù)字表示加工的零件，并且依照時間從左向右的順序依次表示零件的1～3個工序，比如零件7的第一道工序在車間A的機器A4上進行，第二道工序在機器A3上進行，第三道工序在機器A4上進行，調(diào)度甘特圖如圖6。

表1 零件的工序及在三個車間的加工時間表 min

圖5 A車間的調(diào)度甘特圖

圖6 B車間的調(diào)度甘特圖

圖7 C車間的調(diào)度甘特圖

由圖5～7中可以看出：本文提出的柔性作業(yè)車間調(diào)度模型能很好地求解相關調(diào)度的優(yōu)化問題，在調(diào)度中既能把零件合理地分配到合適的車間加工以謀求總體最優(yōu)的加工時間，又能很好地規(guī)劃零件的加工路徑。

7 結(jié)論

（1）本文根據(jù)柔性分布式車間制造系統(tǒng)在多個車間一起進行加工的特點以及目標級聯(lián)法在解決分層調(diào)度問題上的優(yōu)越性，提出一種分級調(diào)度模型，以3個車間的調(diào)度結(jié)果說明了該模型的有效性。

（2）該方法能夠根據(jù)加工時間和加工數(shù)量動態(tài)，合理分配機器數(shù)量和工件的加工路徑，在優(yōu)化過程中如果采用改進的遺傳算法代替?zhèn)鹘y(tǒng)遺傳算法，能夠得到更好的優(yōu)化效果。

[1]楊敬松，崔廣才.基于混合遺傳算法的分布式車間作業(yè)調(diào)度問題[J].長春理工大學學報，2005，28（3）：19-22.

[2]黃英杰，姚錫凡.基于目標級聯(lián)法的作業(yè)車間調(diào)度[J].華南理工大學學報，2010，38（6）：128-132.

[3]Jia H Z.A modified genetic algorithm for distributed scheduling problems[J].Journal of Intelligent Manufacturing，2003，14：351-362.

[4]蘇生，戰(zhàn)德臣.多工廠生產(chǎn)計劃與調(diào)度優(yōu)化模型與求解算法[D].哈爾濱：哈爾濱工業(yè)大學計算機科學與技術學院，2007：1-176.

[5]張曉東，嚴洪森.多級車間生產(chǎn)計劃和調(diào)度的集成優(yōu)QL[J].機械工程學報，2005，4l（9）：98-105.

[6]姚錫凡，帥旗，譚偉，等.基于目標級聯(lián)法和IPDI原則的制造系統(tǒng)建模與優(yōu)化策略[J].南京理工大學學報：自然科學版，2009：257-262.

[7]韓文民，田麗麗，陳娟.基于目標級聯(lián)法的動態(tài)零件族跨單元生產(chǎn)的單元調(diào)度研究[J].機械設計與制造，2012（10）：113-115.

[8]黃英杰，姚錫凡.基于目標級聯(lián)法和粒子群算法的柔性分布式車間調(diào)度[J].中南大學學報，2012，43（1）：151-158.

[9]楊敬松，夏秀峰，崔廣才.混合遺傳算法在分布式車間作業(yè)調(diào)度中的應用[J].計算機工程與應用，2005，41（19）：213-215.

[10]Miehelena N，Kim H M，Papalambros P Y.A system partitioning and optimization approach to target cascading[C]// Proc 12th Int Conf on Eng Design，Munich，1999，2：1109-1112.

[11]趙剛，江平宇.面向大規(guī)模定制生產(chǎn)的e-制造單元層解分析優(yōu)化規(guī)劃模型[J].機械工程學報，2007，43（2）：178-185.

[12]曹楠，陳友玲.基于ATC和GA的可重構(gòu)制造單元分級調(diào)度研究[J].計算機應用研究，2011，28（12）：4467-4470.

[13]Michalek J J，Papalambros P Y.An efficient weighting update method to achieve acceptable consistency deviation in analytical target cascading[J].Journal of Mechanical Design，2005，127（2）：206-214.

[14]Moon C，Seo Y.Evolutionary algorithm for advanced process planning and scheduling in a multi-plan[J].Computers&Industrial Engineering，2005，48（2）：311-325.

[15]田穎，江平宇，周光輝.基于遺傳算法的工藝規(guī)劃與調(diào)度集成方法[J].西安交通大學學報，2006，40（9）：1041-1044.

YANG Jiangbo,CHEN Youling,CAO Nan

School of Mechanical Engineering,Chongqing University,Chongqing 400044,China

Aiming at the workshop distributed manufacturing system scheduling optimization problems,combined with the actual production situation,a hierarchical scheduling model based on analytical target cascading and genetic algorithms is proposed.The model divides the scheduling process into three parts:the planning layer,the workshop scheduling layer and the job planning layer,the whole time minimal as its target is divided into various levels,to achieve the overall optimal scheduling time.Taking a three job-shop system as an example to verify the proposed model could be used in jobs allocation and program the path of each job.

multi distributed manufacturing system;analytical target cascading;hierarchical scheduling;genetic algorithm

針對多車間分布式制造系統(tǒng)調(diào)度優(yōu)化問題，結(jié)合車間實際生產(chǎn)情況，提出一種基于目標級聯(lián)法和遺傳算法的層次調(diào)度模型。模型將生產(chǎn)調(diào)度過程劃分為生產(chǎn)計劃層、車間調(diào)度層和零件規(guī)劃層，并將整體時間最短的優(yōu)化目標劃分到各個層次，通過層層優(yōu)化達到時間最優(yōu)后反饋至上層，以實現(xiàn)整體調(diào)度時間最優(yōu)。以3個制造車間協(xié)調(diào)調(diào)度問題為例，驗證了該模型在零件分配和零件的工藝路線選擇上的合理性和有效性。

多層分布式制造系統(tǒng)；目標級聯(lián)法；分層調(diào)度；遺傳算法

A

TP391

10.3778/j.issn.1002-8331.1301-0169

YANG Jiangbo,CHEN Youling,CAO Nan.Research on grading scheduling model of flexible job distributed workshop.Computer Engineering and Applications,2014,50（23）：239-244.

國家自然科學基金（No.71271224）。

楊江波（1988—），男，碩士研究生，主要研究方向為生產(chǎn)調(diào)度、生產(chǎn)管理；陳友玲（1964—），女，博士，教授，碩導，主要研究方向為生產(chǎn)計劃與調(diào)度、生產(chǎn)系統(tǒng)建模與仿真；曹楠（1987—），女，碩士研究生，主要研究方向為生產(chǎn)調(diào)度、生產(chǎn)管理。E-mail：15025471015@163.com

2013-01-15

2013-04-15

1002-8331（2014）23-0239-06

CNKI網(wǎng)絡優(yōu)先出版：2013-05-03,http://www.cnki.net/kcms/detail/11.2127.TP.20130503.1707.003.html