基于SPEAⅡ的雙資源多目標(biāo)車間調(diào)度模型

任曉青，殷日超，楊雨露，包振強(qiáng)，王維中

(揚(yáng)州大學(xué)信息工程學(xué)院，江蘇揚(yáng)州 225127)

基于SPEAⅡ的雙資源多目標(biāo)車間調(diào)度模型

任曉青，殷日超，楊雨露，包振強(qiáng)*，王維中

(揚(yáng)州大學(xué)信息工程學(xué)院，江蘇揚(yáng)州 225127)

針對(duì)復(fù)雜制造業(yè)環(huán)境下實(shí)際作業(yè)車間受多種資源約束的問(wèn)題，考慮工人綜合素質(zhì)及實(shí)際參與操作設(shè)備的人員數(shù)等因素所存在的差異性對(duì)工作效率的影響，建立了一種包含機(jī)器設(shè)備和操作工人2種約束資源的多目標(biāo)車間調(diào)度模型，然后以完工時(shí)間最短、加工成本最低以及總拖期最小為目標(biāo)，采用改進(jìn)的強(qiáng)度帕累托進(jìn)化算法(strength Pareto evolutionary algorithmⅡ，SPEAⅡ)求解該模型.仿真結(jié)果驗(yàn)證了該模型的正確性以及該文算法的可行性和有效性.

差異性操作效率;雙資源;強(qiáng)度帕累托進(jìn)化算法;多目標(biāo);調(diào)度模型

作業(yè)車間調(diào)度問(wèn)題是制造業(yè)企業(yè)生產(chǎn)管理的核心，大多數(shù)相關(guān)研究?jī)H考慮到機(jī)器設(shè)備的約束，然而據(jù)統(tǒng)計(jì)各領(lǐng)域中有60% ～90%的失效系統(tǒng)可歸因于人誤行為［1］，因此關(guān)于雙資源車間調(diào)度問(wèn)題的研究相繼見(jiàn)諸報(bào)道.劉曉霞［2］，Ertay［3］，Ren［4］等同時(shí)考慮了機(jī)器設(shè)備和操作工人的約束，但將兩者僅視為相互獨(dú)立的資源.實(shí)際生產(chǎn)中，尤其是在單件小批量的生產(chǎn)方式下存在著大量不同工人操作同一機(jī)器以及同一工人操作不同機(jī)器時(shí)操作效率差異顯著的現(xiàn)象，即存在差異性工人操作效率，這直接影響了生產(chǎn)成本及完工時(shí)間等目標(biāo).目前，求解雙資源調(diào)度模型的方法主要有基于學(xué)習(xí)和遺忘規(guī)則［5］、工人轉(zhuǎn)移規(guī)則［6-7］及優(yōu)先級(jí)規(guī)則［8］等的啟發(fā)式算法，以及遺傳算法［9］、混合禁忌搜索［10］等智能算法.其中，改進(jìn)的強(qiáng)度帕累托進(jìn)化算法［11］(strength Pareto evolutionary algorithmⅡ，SPEAⅡ)在求解多目標(biāo)問(wèn)題時(shí)表現(xiàn)出良好的收斂性和解集分布性，且運(yùn)行效率高.本文將在考慮差異性工人操作效率影響的基礎(chǔ)上，建立以完工時(shí)間最短、加工成本最低以及總拖期最小為目標(biāo)的雙資源多目標(biāo)車間調(diào)度模型，并應(yīng)用改進(jìn)的SPEAⅡ算法求解該模型.

1 建立模型

現(xiàn)有 n 個(gè)工件 Ji(i∈{1，2，3，…，n})，需要在由 w 個(gè)工人 Pp(p∈{1，2，3，…，w})和 m 臺(tái)機(jī)器Mk(k∈{1，2，3，…，m})組成的車間內(nèi)加工完成.每個(gè)工件包含一道或多道工序 Oij(j∈{1，2，3，…，Ni})，Ni為Ji的總工序數(shù)，各工序間存在先后約束的關(guān)系，每個(gè)工序可在一臺(tái)或多臺(tái)機(jī)器上加工，且機(jī)器在單位時(shí)間內(nèi)的加工費(fèi)用已知，但因各機(jī)器的性能不同，故工序的實(shí)際加工時(shí)間存在差異.每個(gè)工人可操作一臺(tái)或多臺(tái)機(jī)器，即w＜m.同一工人操作不同機(jī)器的效率及不同工人操作同一機(jī)器的效率均有所差異，因此工序的實(shí)際加工時(shí)間將受工人操作效率的影響.

調(diào)度的目標(biāo)是確定各項(xiàng)加工任務(wù)在機(jī)器中的最佳加工順序和選擇合適的機(jī)器及其對(duì)應(yīng)的操作工人，使得資源配置最優(yōu)化，同時(shí)使完工時(shí)間、生產(chǎn)總成本和總拖期3項(xiàng)性能指標(biāo)相對(duì)最佳.本文需要同時(shí)優(yōu)化的目標(biāo)函數(shù)有:

1）生產(chǎn)成本函數(shù)

式中為Oij受工人操作效率的影響在M k中的實(shí)際完工時(shí)間，，tijk為Oij在M k中的理論完工時(shí)間，ek為工人操作M k的影響因子，Ck為M k的單位時(shí)間加工費(fèi)用，W k為工人操作M k的單位時(shí)間加工費(fèi)用，t p為工人P p的操作時(shí)間.

2）完工時(shí)間函數(shù)

3）總拖期函數(shù)

2 本文算法

2.1 算法流程

本文算法實(shí)現(xiàn)步驟如下：

1）隨機(jī)初始化產(chǎn)生一個(gè)規(guī)模為x的種群R0，令規(guī)模為y的歸檔集Q0為空，用T表示預(yù)定的進(jìn)化代數(shù)，同時(shí)初始化且令進(jìn)化代數(shù)t＝0；

2）計(jì)算Rt和Q t中各個(gè)體的適應(yīng)度；

3）選擇Rt和Q t中的非支配個(gè)體保存至Qt＋1.若｜Qt＋1｜＞y，則通過(guò)修剪過(guò)程進(jìn)行刪減；若｜Qt＋1｜＜y，則再選擇y－｜Qt＋1｜個(gè)適應(yīng)度值小的支配個(gè)體保存至Qt＋1；

4）若t＞T，則結(jié)束進(jìn)化，此時(shí)Qt＋1中所有非支配解即最終所求的最優(yōu)解；否則，繼續(xù)進(jìn)行下一步；

5）采用錦標(biāo)賽法對(duì)Qt＋1選擇配對(duì)；

6）對(duì)配對(duì)染色體進(jìn)行交叉、變異，從中選擇優(yōu)秀的個(gè)體進(jìn)入下一代，令t＝t＋1，轉(zhuǎn)至步驟2）.

2.2 編碼

根據(jù)本文雙資源多目標(biāo)車間調(diào)度模型的特點(diǎn)，同時(shí)結(jié)合本文算例，設(shè)計(jì)了如圖1所示的三維編碼方式.每個(gè)完整的染色體均由如下三部分組成：

1）工序編碼.同一個(gè)工件用相同的實(shí)數(shù)表示，工序的加工順序即其對(duì)應(yīng)的實(shí)數(shù)出現(xiàn)的順序.如圖1所示的工序編碼中，第1次出現(xiàn)的“2”表示第2個(gè)工件的第1道工序，第2次出現(xiàn)的“2”表示第2個(gè)工件的第2道工序，第3次出現(xiàn)的“2”表示第2個(gè)工件的第3道工序，以此類推.

2）機(jī)器編碼.采用實(shí)數(shù)編碼方式.如圖1中機(jī)器編碼染色體的前三位數(shù)字分別表示O11由M7加工，O12由M6加工，O13由M7加工，以此類推.

3）工人編碼.類似于機(jī)器編碼方式.

圖1 三維染色體編碼Fig.1 Chromosome coding scheme

2.3 選擇

在構(gòu)造新的群體時(shí)，首先通過(guò)計(jì)算Rt和Q t中各個(gè)體的適應(yīng)度進(jìn)行環(huán)境選擇，然后采用錦標(biāo)賽法對(duì)Qt＋1配對(duì)進(jìn)行繁殖選擇.

2.4 交叉

1）工序交叉.將全部工件隨機(jī)分成2個(gè)非空集合X1，X2，X1＝｛1，3，5｝，X2＝｛2，4｝，復(fù)制父代染色體U1中包含在X1的工件到子代染色體V1，復(fù)制父代染色體U2中包含在X2的工件到子代染色體V2，保留它們的位置；復(fù)制U2中包含在X2的工件到V1，復(fù)制U1中包含在X1的工件到V2，保留它們的順序，如圖2（a）所示.

2）機(jī)器交叉.首先隨機(jī)產(chǎn)生a個(gè)交叉點(diǎn)（a為不大于染色體長(zhǎng)度的實(shí)數(shù)），然后依次在父代染色體A1，A2中尋找并交換這些交叉點(diǎn)所對(duì)應(yīng)的機(jī)器，其余機(jī)器則保留到子代產(chǎn)生兩個(gè)子代染色體V1，V2，如圖2（b）所示.由圖2（b）可見(jiàn)，隨機(jī)交叉點(diǎn)為3個(gè)，分別是位置2，5，8.

3）工人交叉.其方法類似于機(jī)器交叉操作.

圖2 交叉操作Fig.2 Crossover operation

2.5 變異

1）工序變異.隨機(jī)選擇一個(gè)工序，再隨機(jī)產(chǎn)生一個(gè)插入點(diǎn)，將該工序插入到產(chǎn)生的插入點(diǎn)位置，如圖3（a）所示，即可由父代染色體P1變異為子代染色體C1.

2）機(jī)器變異.隨機(jī)選擇機(jī)器編碼染色體中的一個(gè)基因，從可加工集｛1，3，5，6，7｝中任選一個(gè)替代之，如圖3（b）所示.

3）工人變異.與機(jī)器變異操作方法類似.

圖3 變異操作Fig.3 Mutation operation

3 仿真與分析

本文算法運(yùn)用Java編程語(yǔ)言實(shí)現(xiàn)，程序運(yùn)行環(huán)境為P4 CPU，主頻為2.8 GHz，內(nèi)存為1.25 GB.

某機(jī)械加工車間計(jì)劃由8臺(tái)機(jī)器（M1～M8）和6名工人來(lái)生產(chǎn)5種各自具有多道工序的工件（J1～J5）.各工件原材料成本分別為160，210，440，340，570元，每臺(tái)機(jī)器的單位時(shí)間加工費(fèi)用分別為8，5，10，9，7，6，9，4元·h－1，每個(gè)工人單位時(shí)間加工費(fèi)用分別為20，15，15，20，15，20元·h－1.其余加工數(shù)據(jù)如表1～2所示.

表1 各機(jī)器對(duì)應(yīng)的工人操作效率Tab.1 Worker efficiency of each machine

表2 柔性作業(yè)車間調(diào)度的加工時(shí)間Tab.2 Associated time of each job

程序運(yùn)行結(jié)束后得到一組解，筆者根據(jù)個(gè)人偏好，在優(yōu)先考慮交貨期的前提下選取部分Pareto優(yōu)化結(jié)果，并采用本文算法對(duì)考慮平均工人操作效率的雙資源車間調(diào)度模型進(jìn)行仿真，結(jié)果如表3所示.由表3可見(jiàn)，考慮差異性工人操作效率影響普遍比考慮平均工人操作效率下的結(jié)果更優(yōu).

限于篇幅，同樣僅根據(jù)個(gè)人偏好選擇表3中第4組結(jié)果給出對(duì)應(yīng)的甘特圖，如圖4所示.圖4（a）中“5－2－6－8”表示工件5的第2道工序由工人6在機(jī)器8中加工完成.由圖4可知，考慮差異性工人操作效率的影響明顯比考慮平均工人操作效率下的完工時(shí)間短，機(jī)器利用率更高，綜合效益更大.

圖4 甘特圖Fig.4 Gantt

4 結(jié)語(yǔ)

本文在研究雙資源車間調(diào)度問(wèn)題的基礎(chǔ)上，考慮差異性操作工人操作效率的影響，建立了一種新的雙資源多目標(biāo)車間調(diào)度模型.針對(duì)該模型的特點(diǎn)，提出一種改進(jìn)的SPEAⅡ算法，設(shè)計(jì)了一種適合雙資源要求的三維編碼方式，并對(duì)染色體的交叉、變異等操作進(jìn)行了改進(jìn)，對(duì)過(guò)程中可能產(chǎn)生的非法染色體進(jìn)行了相應(yīng)的修復(fù)處理.仿真結(jié)果表明，合理的工人分配不僅能縮短生產(chǎn)周期，降低生產(chǎn)成本，還能提高企業(yè)的綜合效益.

［1］何旭紅，黃祥瑞.工業(yè)系統(tǒng)中人的可靠性分析：原理、方法與應(yīng)用 ［M］.北京：清華大學(xué)出版社，2007：137.

［2］劉曉霞，謝里陽(yáng)，崔敬巍.雙資源生產(chǎn)車間調(diào)度問(wèn)題的研究 ［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（6）：10－13.

［3］ERTAY T，SATOGLU S I.System parameter selection with information axiom for the new product introduction to the hybrid manufacturing systems under dual－resource constraint［J］.Int J Prod Res，2012，50（7）：1825－1839.

［4］REN Huiyuan，JIANG Lili，XI Xiaoying，et al.Heuristic optimization for dual－resource constrained job shop scheduling［C］／／2009 International Asia Conference on Informatics in Control，Automation and Robotics.Bangkok，Thailand：Institute of Electrical and Electronics Engineers Computer Society，2009：485－488.

［5］KHER H V.Examination of flexibility acquisition policies in dual resource constrained job shops with simultaneous worker learning and forgetting effects［J］.J Oper Res Soc，2000，51（5）：592－601.

［6］SALUM L，ARAZ O U.Using the when／where rules in dual resource constrained systems for a hybrid pushpull control［J］.Int J Prod Res，2009，47（6）：1661－1677.

［7］BOKHORST J A C，SLOMP J，GAALMAN G J C.On the who－rule in dual resource constrained（DRC）manufacturing systems［J］.Int J Prod Res，2004，42（23）：5049－5074.

［8］BERND S R，JENS H，TORSTEN H.Analysis of priority rule－based scheduling in dual－resource－constrained shop－floor scenarios［C］／／International Conference on Advances in Machine Learning and Systems Engineering.Berkeley，United States：Springer Verlag，2010，68：269－281.

［9］ELMARAGHY H，PATEL V，ABDALLAH I B.Scheduling of manufacturing systems under dual－resource constraints using genetic algorithms［J］.J Manuf Syst，2000，19（3）：186－198.

［10］LIANG Di，LIU Si，TAO Ze.Based on Petri nets and hybrid genetic－Tabu search approach to scheduling optimization for dual－resource constrained job shop［C］／／Proceedings of the 2nd International Conference on Electronic and Mechanical Engineering and Information Technology.Shenyang，Liaoning，China：Atlantis Press，2012：1355－1359.

［11］AMIN－TAHMASBI H，TAVAKKOLI－MOGHADDAM R.Solving a bi－objective flowshop scheduling problem by a multi－objective immune system and comparing with SPEA2＋and SPGA ［J］.Adv Eng Softw，2011，42（10）：772－779.

Multi－objective dual－resource shop scheduling model based on SPEAⅡ

REN Xiaoqing，YIN Richao，YANG Yulu，BAO Zhenqiang＊，WANG Weizhong

（Sch of Inf Engin，Yangzhou Univ，Yangzhou 225127，China）

Multiple resource constraints exist in the actual job shop under the complex manufacturing environment，so a multi－objective dual resource shop scheduling model considering differences between operational efficiency is established.There are three objectives in the model：the shortest completion time，the lowest cost and the minimum total tardiness.In view of the limitation of traditional algorithms for single resource，an improved SPEAⅡis proposed for model in this paper.Finally，the feasibility and efficiency of the model are proved by the simulation experiment.

differences between operational efficiency；dual－resource；strength Pareto evolutionary algorithm；multi－objective；scheduling model

TP 18

A

1007-824X(2015)03-0051-05

2014-10-16.* 聯(lián)系人，E-mail:yzbzq@163.com.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61170201);江蘇省研究生科研創(chuàng)新項(xiàng)目(CXZZ13-0919);江蘇省大學(xué)生創(chuàng)新項(xiàng)目(201411117041Z).

任曉青，殷日超，楊雨露，等.基于SPEAⅡ的雙資源多目標(biāo)車間調(diào)度模型［J］.揚(yáng)州大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，18(3):51-55.

（責(zé)任編輯 林 子）