劉 壯，張中敏，杜先軍

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

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

劉 壯，張中敏，杜先軍

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

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

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

0 引言

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

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

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

1.1 決策指標(biāo)

1.1.1 工序相似性指標(biāo)

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

(1)

(2)

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

1.1.2 額外機(jī)器能耗指標(biāo)

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

(3)

1.2 指標(biāo)賦權(quán)

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

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

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

(4)

式中：Il為指標(biāo)排序后的第l個(gè)指標(biāo)。

(2) 依據(jù)專家知識(shí)經(jīng)驗(yàn)，確定相鄰指標(biāo)的相對重要程度：

(5)

式中，zl為指標(biāo)Il-1與指標(biāo)Il的相對重要程度。

(3)計(jì)算指標(biāo)的權(quán)重如下所示：

(6)

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

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

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

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

(7)

Step2: 由于決策指標(biāo)越小越好，借鑒TOPSIS思想，確定正、負(fù)理想解：

(8)

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

(9)

(10)

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

(11)

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

(12)

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

(13)

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

3 實(shí)例驗(yàn)證

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

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

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

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

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

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

(14)

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

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

(15)

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

表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)度方案的完工時(shí)間為55，與圖1初始調(diào)度方案的完工時(shí)間相同，即重調(diào)度后沒有出現(xiàn)完工延遲，則說明最優(yōu)重調(diào)度方案有效，進(jìn)而表明重調(diào)度決策方法的方案選擇是合理的。

3.2 改進(jìn)TOPSIS性能分析

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

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

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

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

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

4 結(jié)論

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

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

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

[2] 閻志華, 丁秋林. 用蜂群算法實(shí)現(xiàn)動(dòng)態(tài)作業(yè)車間調(diào)度[J]. 組合機(jī)床與自動(dòng)化加工技術(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)的改進(jìn)的混合重調(diào)度策略研究[J]. 計(jì)算機(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)保護(hù)與控制, 2014, 42(6): 14-19.

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

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

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

[16] 劉樹林, 邱菀華. 多屬性決策的TOPSIS夾角度量評價(jià)法[J]. 系統(tǒng)工程理論與實(shí)踐, 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àn)橹悄軆?yōu)化與生產(chǎn)調(diào)度研究，(E-mail)linglin8787@126.com。

TH186；TG65

A