劉 壯，張中敏，杜先軍

(合肥工業(yè)大學(xué) 機械與汽車工程學(xué)院，合肥 230009)

基于改進TOPSIS的制造車間重調(diào)度決策方法研究

劉 壯，張中敏，杜先軍

(合肥工業(yè)大學(xué) 機械與汽車工程學(xué)院，合肥 230009)

針對制造車間最優(yōu)重調(diào)度方案甄選問題，提出了一種基于改進逼近理想解排序的制造車間重調(diào)度決策方法。以可選調(diào)度方案集作為研究對象，考慮調(diào)度方案變更過程的耗損，設(shè)計工序相似性和額外機器能耗決策指標，實現(xiàn)調(diào)度方案性能的量化描述；利用基于Kullback-Leibler距離和灰色關(guān)聯(lián)度的改進逼近理想解排序方法，確定可選調(diào)度方案間的偏序關(guān)系，以判斷是否觸發(fā)重調(diào)度及選取最優(yōu)重調(diào)度方案。最后，通過實例驗證了所建立重調(diào)度決策方法的合理性和有效性。

決策指標；改進逼近理想解排序；重調(diào)度決策方法

0 引言

現(xiàn)代制造車間在實際生產(chǎn)過程中經(jīng)常面臨各種擾動事件，如機器故障、緊急訂單插入、操作延遲、工件返工或報廢等。生產(chǎn)擾動的發(fā)生將導(dǎo)致原調(diào)度方案逐漸偏離實際生產(chǎn)情形，致使原調(diào)度方案有效性降低，甚至失去可行性。為保證生產(chǎn)系統(tǒng)持續(xù)穩(wěn)定地運行，則需修正或重新生成調(diào)度方案，由此引出了制造車間重調(diào)度問題。重調(diào)度問題作為優(yōu)化調(diào)度問題的延伸，已成為生產(chǎn)調(diào)度領(lǐng)域研究的熱點，備受國內(nèi)外學(xué)者的關(guān)注，如Vieira等[1]提出了制造車間的重調(diào)度研究體系；閻志華等[2]通過蜂群算法解決工件隨機到達環(huán)境下的作業(yè)車間重調(diào)度問題；Akkan[3]為兼顧重調(diào)度的穩(wěn)定性和魯棒性，提出了分支定界與局部搜索結(jié)合的混合算法；文獻[4-6]考慮頻繁重調(diào)度易導(dǎo)致生產(chǎn)系統(tǒng)的振蕩，以事件驅(qū)動策略為研究對象進行了一系列改進研究；喬非等[7]引入最小重調(diào)度時間間隔約束，避免混合驅(qū)動策略中出現(xiàn)重調(diào)度觸發(fā)點間隔過小(或過大)現(xiàn)象，保證系統(tǒng)實時性和穩(wěn)定性；Petrovic等[8]以生產(chǎn)持續(xù)時間和原材料缺貨量為參數(shù)描述生產(chǎn)過程的不確定性，建立了基于模糊推理的重調(diào)度決策系統(tǒng)；劉明周等[9]提出基于損益云模型的重調(diào)度決策方法，實現(xiàn)重調(diào)度觸發(fā)判定及調(diào)度方案的選取。

綜上所述，現(xiàn)有重調(diào)度研究主要集中于重調(diào)度方法和重調(diào)度策略優(yōu)化方面，而有關(guān)重調(diào)度決策研究相對較少。通過重調(diào)度決策能幫助管理者了解調(diào)度變更的性能優(yōu)劣，避免因偽最優(yōu)重調(diào)度方案而造成的損失，保證生產(chǎn)系統(tǒng)穩(wěn)定運行。因此，本文在現(xiàn)有研究基礎(chǔ)上，考慮重調(diào)度耗損，提出基于改進TOPSIS的重調(diào)度決策方法。首先，構(gòu)建重調(diào)度決策模型，模型中以可選調(diào)度方案集為決策對象，設(shè)計的重調(diào)度決策指標作為方案評判標準，并采用G1法進行決策指標賦權(quán)；其次，采用基于Kullback-Leibler距離和灰色關(guān)聯(lián)度的改進TOPSIS對可選調(diào)度方案排序，實現(xiàn)重調(diào)度觸發(fā)判定及最優(yōu)重調(diào)度方案選擇；最后，通過實例論證決策方法合理性。

1 重調(diào)度決策問題描述

重調(diào)度決策問題主要包括決策對象的確立、決策指標的設(shè)計及指標的賦權(quán)，其中決策對象為可選調(diào)度方案集，由右移重調(diào)度方法和智能搜索方法生成的調(diào)度方案組成，具體表示為{F1,F2,…,FK}，F(xiàn)1表征采用右移重調(diào)度形成的調(diào)度方案。

1.1 決策指標

1.1.1 工序相似性指標

JobShop制造車間發(fā)生生產(chǎn)擾動后，為適應(yīng)實時工況的變化，需要實施重調(diào)度。在重調(diào)度實施(即調(diào)度方案變更)過程中，由于車間生產(chǎn)制造資源的重新配置，致使可選調(diào)度方案與原調(diào)度方案出現(xiàn)偏離，產(chǎn)生一定附加成本，并可能造成工件完工時間的延遲。為降低重調(diào)度實施的損失，需要盡量避免車間各工件工序的加工機器、加工順序及開始加工時間的調(diào)整，即盡量與原調(diào)度方案工序的安排相同。因此，構(gòu)建工序相似性指標，表征可選調(diào)度方案與原調(diào)度方案相似程度：

(1)

(2)

式中，zij為調(diào)度決策變量，當zij為0時，表示可選調(diào)度方案和原調(diào)度方案中工件i的第j道工序的加工機器相同，當zij為1時，表示可選調(diào)度方案和原調(diào)度方案中工件i的第j道工序的加工機器不同。

1.1.2 額外機器能耗指標

隨著人類社會環(huán)保意識的加強，制造企業(yè)越來越關(guān)注制造車間的節(jié)能減排。本文從加工機器低碳策略角度出發(fā)，對重調(diào)度實施過程的加工機器能源耗損進行分析。由于原調(diào)度方案是靜態(tài)制造車間生產(chǎn)環(huán)境下經(jīng)優(yōu)化所獲得的最滿意調(diào)度方案即該調(diào)度方案性能水平最優(yōu)，由此可知，在加工機器調(diào)度性能方面，生產(chǎn)擾動發(fā)生后重調(diào)度方法所形成的可選調(diào)度方案必然比原調(diào)度方案增加一定的加工機器空載運行時間，即造成一定的額外能源消耗。因此，構(gòu)建額外機器能耗指標，表征調(diào)度方案變更過程中的能耗損失：

(3)

1.2 指標賦權(quán)

G1法是對AHP法的改進，無需進行一致性檢驗，克服了AHP法計算量大、計算復(fù)雜等缺點。方法通過專家對指標的重要性排序及相鄰指標重要程度之比，確定各指標的權(quán)重w，參考文獻[11]，指標賦權(quán)如下：

(1) 專家確定各指標的序關(guān)系：

I1?I2?…?Il，l=1,2,…N

(4)

式中：Il為指標排序后的第l個指標。

(2) 依據(jù)專家知識經(jīng)驗，確定相鄰指標的相對重要程度：

(5)

式中，zl為指標Il-1與指標Il的相對重要程度。

(3)計算指標的權(quán)重如下所示：

(6)

式中，wN表示指標IN的權(quán)重；wl-1表示指標Il-1的權(quán)重，wl表示指標Il的權(quán)重。

2 重調(diào)度決策方法

TOPSIS因具有計算簡單、結(jié)果量化客觀等優(yōu)點，在決策問題解決上得到廣泛應(yīng)用。但傳統(tǒng)TOPSIS只體現(xiàn)了評價對象與理想解的位置相似程度，當評價對象連線被正、負理想解連線垂直平分或評價對象位于正、負理想解連線中垂線上，則無法區(qū)分優(yōu)劣[12]。而信息論中Kullback-Leibler距離能有效解決位于正、負理想解連線中垂線的評價對象排序問題[13]，同時灰色關(guān)聯(lián)分析法能很好地評價曲線(評價對象的各指標構(gòu)成)間形狀相似性。因此，可在傳統(tǒng)TOPSIS中將Kullback-Leibler距離與灰色關(guān)聯(lián)度結(jié)合來替代歐式距離，使決策效果更加合理，基于改進TOPSIS的重調(diào)度決策方法步驟如下：

Step1:構(gòu)建加權(quán)標準決策矩陣：

(7)

Step2: 由于決策指標越小越好，借鑒TOPSIS思想，確定正、負理想解：

(8)

Step3:考慮歐式距離表征可選調(diào)度方案與正、負理想解相似程度的局限性，本文將Kullback-Leibler距離和灰色關(guān)聯(lián)度結(jié)合，構(gòu)建綜合相似度公式，具體計算如下所示：

(9)

(10)

式中，ε為分辨系數(shù)，通常取值為0.5。

(11)

Step4:計算可選調(diào)度方案Fh的相對貼近度Ah為：

(12)

Step5:按照相對貼近度從大到小對可選調(diào)度方案排序，并進行序列分析：

(13)

Step6:若重調(diào)度方案集φR為?，則繼續(xù)執(zhí)行原調(diào)度方案，反之，則觸發(fā)重調(diào)度，并選擇相對貼近度最大的調(diào)度方案作為最優(yōu)重調(diào)度方案。

3 實例驗證

本文以Benchmark6×6JobShop調(diào)度問題為例，通過Matlab7.8編寫的仿真程序分析決策方法的可行性。假設(shè)t=25時，1號機器發(fā)生故障，維修5min。采用混合粒子群優(yōu)化算法[14]生成調(diào)度方案，并與右移調(diào)度方案構(gòu)成可選調(diào)度方案集，依據(jù)式(1)～(3)計算各可選調(diào)度方案決策值見表1。初始優(yōu)化調(diào)度方案如圖1。

圖1 初始調(diào)度方案

決策指標可選調(diào)度方案F1F2F3F4F5F6Rh1．211．131．061．261．151．08Eh2．322．111．942．212．061．91

表1用于分析可選調(diào)度方案的優(yōu)劣，指標越小，方案越優(yōu)。例如，可選調(diào)度方案F3的工序相似性指標值為1.06，是所有方案工序相似性指標的最小值，則說明在工序相似性指標方面，可選調(diào)度方案F3最好。

3.1 重調(diào)度決策方法

Step2:基于表1數(shù)據(jù)，根據(jù)式(7)建立加權(quán)標準決策矩陣：

(14)

Step3:依據(jù)式(8)，確定加權(quán)標準決策矩陣的正、負理想解：

F+={0.46,0.37}F-={0.55,0.45}

(15)

表2 可選調(diào)度方案評價

表2中，相對貼近度Ah表示可選調(diào)度方案的優(yōu)良程度，按照相對貼近度Ah從大到小對可選調(diào)度方案排序，可得方案的排序序列為：F3?F6?F2?F5?F1?F4。

Step5:依據(jù)排序序列，可得重調(diào)度方案集為φR={F2,F3,F5,F6}，則觸發(fā)重調(diào)度，并選取相對貼近度最大的可選調(diào)度方案F3作為最優(yōu)重調(diào)度方案來執(zhí)行重調(diào)度。最優(yōu)重調(diào)度方案如圖2。

圖2 最優(yōu)重調(diào)度方案

由圖2可知最優(yōu)重調(diào)度方案的完工時間為55，與圖1初始調(diào)度方案的完工時間相同，即重調(diào)度后沒有出現(xiàn)完工延遲，則說明最優(yōu)重調(diào)度方案有效，進而表明重調(diào)度決策方法的方案選擇是合理的。

3.2 改進TOPSIS性能分析

為進一步驗證決策方法的性能，針對可選調(diào)度方案的優(yōu)劣排序問題，將本文的改進TOPSIS的方法與傳統(tǒng)TOPSIS方法、正交投影法[15]、夾角余弦法[16]進行對比，各方法的具體結(jié)果見表3。

表3 各方法的方案相對貼近度

依據(jù)表3數(shù)據(jù)，確定各方法關(guān)于可選調(diào)度方案優(yōu)劣關(guān)系，結(jié)果見表4。

表4 各方法的方案優(yōu)劣排序

方法可選調(diào)度方案優(yōu)劣排序序列改進TOPSISF3?F6?F2?F5?F1?F4傳統(tǒng)TOPSISF3=F6?F2?F5?F1?F4正交投影法F3?F6?F2?F5?F1=F4夾角余弦法F3?F6?F5?F2?F1?F4

由表4中可選調(diào)度方案排序序列對比可知，改進TOPSIS、傳統(tǒng)TOPSIS、正交投影法和夾角余弦法獲得的方案優(yōu)劣排序序列大體一致，均認為F3是最優(yōu)的，同時F4是最差的。但傳統(tǒng)TOPSIS、正交投影法和夾角余弦法產(chǎn)生的排序序列都有一定的不足，傳統(tǒng)TOPSIS與正交投影法中都出現(xiàn)個別方案相對貼近度相等的情況，致使方案優(yōu)劣無法區(qū)分，其中傳統(tǒng)TOPSIS中F3和F6相對貼近度相等，正交投影法中F1和F4相對貼近度相等；夾角余弦法中F2和F5的相對貼近度大小比較結(jié)果與其他方法不同，導(dǎo)致F2和F5在排序序列中的位置顛倒。而改進TOPSIS除了方案排序序列與傳統(tǒng)TOPSIS的方案排序序列基本一致以外，還能夠規(guī)避其他方法存在的風險，如方案相對貼近度相等而導(dǎo)致無法區(qū)分方案優(yōu)劣，或者出現(xiàn)方案優(yōu)劣排序相反的現(xiàn)象，這說明了本文的改進TOPSIS具有較好的評價效果，進而驗證了基于改進TOPSIS的重調(diào)度決策方法是可行有效的。

4 結(jié)論

(1) 從重調(diào)度耗損角度出發(fā)，基于工件和機器兩個層面構(gòu)建重調(diào)度決策指標，對重調(diào)度過程中可選調(diào)度方案相對于原調(diào)度方案性能進行定量描述和分析，為可選調(diào)度方案優(yōu)劣評價提供依據(jù)。

(2) 提出基于改進TOPSIS的重調(diào)度決策方法，為重調(diào)度判定和最優(yōu)重調(diào)度方案選擇提供科學(xué)手段，并通過算例分析及改進TOPSIS與傳統(tǒng)TOPSIS、正交投影法、夾角余弦法的對比，驗證了該決策方法的有效性。

[1]VieiraGE,HerrmannJW,LinE.Reschedulingmanufacturingsystems:Aframeworkofstrategies,policies,andmethods[J].JournalofScheduling, 2003, 6 (1): 39-62.

[2] 閻志華, 丁秋林. 用蜂群算法實現(xiàn)動態(tài)作業(yè)車間調(diào)度[J]. 組合機床與自動化加工技術(shù), 2004(2): 47-48,50.

[3]AkkanC.Improvingschedulestabilityinsingle-machinereschedulingfornewoperationinsertion[J].Computers&OperationsResearch, 2015, 64: 198-209.

[4]HaruhikoS.Anewwhen-to-schedulepolicyinonlineschedulingbasedoncumulativetaskdelays[J].InternationalJournalofProductionEconomics, 2007, 110(1/2): 175-186.

[5]KopanosGM,Capon-GarciaE,EspunaA,etal.CostsforReschedulingActions:ACriticalIssueforReducingtheGapbetweenSchedulingTheoryandPractice[J].Industrial&EngineeringChemistryResearch, 2008, 47(22): 8785-8795.

[6]KaoHP,WangB,DongJ,etal.Anevent-drivenapproachwithmakespan/costtradeoffanalysisforprojectportfolioscheduling[J].ComputersinIndustry, 2006, 57(5): 379- 397.

[7] 喬非, 李莉, 王遵彤, 等. 面向半導(dǎo)體生產(chǎn)的改進的混合重調(diào)度策略研究[J]. 計算機集成制造系統(tǒng), 2007, 13(3): 558-562.

[8]PetrovicD,DuenasA.Afuzzylogicbasedproductionscheduling/reschedulinginthepresenceofuncertainDisruptions[J].FuzzySetsandSystems, 2006, 157(16): 2273-2285.

[9] 劉明周, 張璽, 張銘鑫, 等. 基于損益云模型的制造車間重調(diào)度決策方法 [J]. 控制與決策, 2014, 29(8): 1458-1464.

[10]ZakariaZ,PetrovicS.Geneticalgorithmsformatch-upreschedulingoftheflexiblemanufacturingsystems[J].Computers&IndustrialEngineering, 2012, 62(2): 670-686.

[11] 王學(xué)軍, 郭亞軍. 基于G1法的判斷矩陣的一致性分析[J]. 中國管理科學(xué), 2006, 14(3): 65-70.

[12] 李正明, 施詩, 潘天紅, 等. 基于灰色關(guān)聯(lián)度和理想解法的電能質(zhì)量綜合評估方法[J]. 電力系統(tǒng)保護與控制, 2014, 42(6): 14-19.

[13] 趙萌, 邱菀華, 劉北上. 基于相對熵的多屬性決策排序方法[J]. 控制與決策, 2010, 25(7): 1098-1100.

[14] 劉明周, 單暉, 蔣增強, 等. 不確定條件下車間動態(tài)重調(diào)度優(yōu)化方法[J]. 機械工程學(xué)報, 2009, 45(10): 137-142.

[15] 華小義, 譚景信. 基于“垂面”距離的TOPSIS法—正交投影法[J]. 系統(tǒng)工程理論與實踐, 2004, 24(1): 114-119.

[16] 劉樹林, 邱菀華. 多屬性決策的TOPSIS夾角度量評價法[J]. 系統(tǒng)工程理論與實踐, 1996, 16(7): 12-16.

(編輯 李秀敏)

Rescheduling Decision Method of Manufacturing Shop Based on Improved TOPSIS

LIU Zhuang, ZHANG Zhong-min, DU Xian-jun

(School of Mechanical and Automotive Engineering, Hefei University of Technology, Hefei 230009, China)

Aiming at the schedule selection problem of rescheduling in manufacturing shop, a rescheduling decision method based on improved TOPSIS is proposed. Firstly, the set of optional schedules is taken as the research subject, and then considering consumption in schedule changing process, the procedure similarity decision index and additional machine energy consumption decision index is established in order to depict performance of the optional schedules. Secondly, the partial order of optional schedules is ascertained by improved TOPSIS which is based on Kullback-Leibler divergence and grey correlation degree, which determines whether or not reschedule and chooses the optimal reschedule. Finally, an example is given to demonstrate the rationality and validity of the rescheduling decision method.

decision index; improved TOPSIS; rescheduling decision method

1001-2265(2017)01-0157-04

10.13462/j.cnki.mmtamt.2017.01.043

2016-03-01；

2016-04-08

劉壯(1990—)，男，黑龍江綏芬河人，合肥工業(yè)大學(xué)碩士研究生，研究方向為智能優(yōu)化與生產(chǎn)調(diào)度研究，(E-mail)linglin8787@126.com。

TH186；TG65

A