衛(wèi) 巍 楊志輝 謝浩然 胡倚薇

1(東華理工大學(xué)化學(xué)生物與材料科學(xué)學(xué)院 江西 南昌 330013)2(東華理工大學(xué)理學(xué)院 江西 南昌 330013)3(東華理工大學(xué)地球物理與測(cè)控技術(shù)學(xué)院 江西 南昌 330013)

0 引 言

自1954年以來，學(xué)者們對(duì)生產(chǎn)調(diào)度問題進(jìn)行了大量的研究。但是由于以往的生產(chǎn)調(diào)度模型都使用了大量的前提與假設(shè)，造成其模型在生產(chǎn)實(shí)踐中很難被應(yīng)用[1]。因此，對(duì)于更符合實(shí)際情況下的柔性作業(yè)車間調(diào)度問題(FJSP)具有非常重要的研究價(jià)值[2]。

21世紀(jì)，針對(duì)FJSP問題常使用啟發(fā)式的方法對(duì)問題進(jìn)行研究求解。Ho等[3]對(duì)FJSP使用組合分派方法；Chen等[4]用圖論模擬分段為兩部分染色體求解FJSP；王雷等[5]考慮快速解碼算法避免非法解產(chǎn)生，通過精英策略提高求解效率和求解的總適應(yīng)度；張曉星等[6]通過研究最大完工時(shí)間及總加工能耗，使用混合蛙跳算法求解FJSP，得到不同權(quán)重下的調(diào)度方案；Kato等[2]將問題分為粒子群優(yōu)化(Particle Swarm Optimization,PSO)，及隨機(jī)重啟爬山(Random-Restart Hill Climbing,RRHC)；Zandieh等[7]模擬了FJSP基于狀態(tài)的維護(hù)(Condition Based Maintenance,CBM)，并考慮Sigmoid函數(shù)和高斯分布的組合改進(jìn)CBM，提出了一種改進(jìn)的帝國競爭算法(Imperialist Competitive Algorithm,ICA)；Gao等[8]提出了一種改進(jìn)的人工蜂群(Improved Artificial Bee Colony,ABCIABC)算法，其中基于處理時(shí)間的不確定性，將其建模為模糊處理時(shí)間；趙詩奎[9]對(duì)已有鄰域進(jìn)行精簡與有效移動(dòng)的拓展，提出了融合改進(jìn)鄰域的混合算法；張新等[10]對(duì)入侵雜草算法做出了新的改進(jìn)；徐文豪等[12]對(duì)花授粉算法對(duì)問題的解進(jìn)行離散化，在過程中為平衡前期全局搜索能力與防止后期陷入局部優(yōu)解引入自適應(yīng)正則化因子。

在實(shí)際生產(chǎn)中，存在FJSP問題未考慮實(shí)際因素。在近年來，國內(nèi)外學(xué)者對(duì)實(shí)際問題的不同方面進(jìn)行了分析。Lin等[13]對(duì)工件運(yùn)輸過程消耗的時(shí)間進(jìn)行考慮，使用集成的GA-GSO-GTHS(Genetic Algorithm-Glowworm Swarm Optimization-green tra-nsport heuristic strategy)算法解決問題；Zhang等[14]與張國輝等[15]分別對(duì)FJSP問題在生產(chǎn)過程中綠色制造問題進(jìn)行了考慮，前者開發(fā)了基于動(dòng)態(tài)博弈的雙層調(diào)度算法，后者構(gòu)建了碳排放的定量模型，通過多目標(biāo)求最值獲得最優(yōu)解；Yazdani等[16]對(duì)流水線最早與延遲兩類情況分別的總時(shí)長作為目標(biāo)函數(shù)，針對(duì)問題的復(fù)雜性，構(gòu)建了基于有效鄰域混合的帝國競爭算法(ICA)；Rahmati等[17]考慮了糾正性維護(hù)(Corrective Maintenance,CM)和預(yù)防性維護(hù)(Preventive Maintenance,PM)方面的兩種維護(hù)方案，同時(shí)對(duì)多步驟間的加工過程進(jìn)行了考慮。

針對(duì)現(xiàn)有方法對(duì)于機(jī)器出現(xiàn)故障[18]時(shí)的調(diào)度考慮以及系統(tǒng)的穩(wěn)定性[19]方面考慮不足的局限，本文提出改進(jìn)的遺傳算法編碼方式及求解方法。通過結(jié)合多因素、多目標(biāo)的問題特征構(gòu)建編碼方式，利用改進(jìn)的遺傳算法對(duì)加工次序進(jìn)行求解，得到一組與最優(yōu)解總時(shí)間差距不大的較優(yōu)解。該方法不僅可以方便快速地求解此類問題，還可以提升此類問題的可解釋性和準(zhǔn)確程度，并且得到優(yōu)化的編碼形式更利于人們理解。

1 改進(jìn)遺傳算法解決RGV調(diào)度問題

1.1 相關(guān)工作

遺傳算法最早由美國密執(zhí)安大學(xué)Holland教授[20]根據(jù)物競天擇理論于20世紀(jì)60年代提出,至20世紀(jì)80年代形成基本的框架。2005年，江雷等[21]將遺傳算法并行化求解旅行商問題(Traveling Salesman Problem，TSP)，此算法進(jìn)一步提高了種群的多樣性和結(jié)果的準(zhǔn)確性。

RGV是一類可以根據(jù)指令自動(dòng)控制移動(dòng)方向和距離、作用是搬運(yùn)物料的智能車，并且此智能車運(yùn)行在固定軌道上，自帶一個(gè)機(jī)械手臂、兩個(gè)機(jī)械手爪與物料清洗位，可以對(duì)上下料及清洗物料等作業(yè)任務(wù)進(jìn)行操作完成，進(jìn)一步提升了加工的效率，并體現(xiàn)了其相對(duì)的智能性。

車間調(diào)度問題(JSP)作為一個(gè)最為常見的NP hard問題，它的調(diào)度目標(biāo)就是事先得到機(jī)器加工工序的時(shí)間，最終使得耗費(fèi)的資源最少。柔性作業(yè)車間調(diào)度問題(FJSP)是以上問題的擴(kuò)展問題。1990年，Bruker等[22]首次提出了FJSP的概念，即帶有機(jī)器柔性的JSP問題。與上述問題不同的是，柔性作業(yè)車間調(diào)度問題則是工件不確定其加工機(jī)器，也不確定加工工序，其靈活性較高，因此，此類問題是個(gè)有待解決的熱門問題。

(1) 此問題屬于NP難問題，大多數(shù)解法或多或少都會(huì)陷入局部收斂的障礙；

(2) 機(jī)器在運(yùn)作中還會(huì)有一定可能發(fā)生故障，從而影響整體結(jié)果。

針對(duì)上述不足,本文根據(jù)FJSP問題對(duì)遺傳算法進(jìn)行改進(jìn)，減少局部收斂出現(xiàn)的概率，使改進(jìn)后的方法所得到的解更接近最優(yōu)解。

(1) 在解決陷入局部收斂方面，將遺傳算法編碼分為機(jī)器選擇部分、工序排序部分、故障概率部分和工序分配部分；

(2) 在解決故障影響方面，本文引入了機(jī)器故障概率和機(jī)器維修時(shí)間概念。

本文中，智能RGV動(dòng)態(tài)調(diào)度問題的解決方法是通過使用解決柔性車間調(diào)度問題的方法來解決的。其問題本身就是一類在柔性前提下的作業(yè)車間調(diào)度問題，因而兩者一個(gè)為實(shí)際問題，一個(gè)為構(gòu)建的模型，并通過對(duì)此模型的求解得到智能RGV問題的調(diào)度方案。

1.2 問題描述

智能化RGV動(dòng)態(tài)調(diào)度問題中，智能RGV要在n臺(tái)機(jī)器之間來回移動(dòng)ω個(gè)獨(dú)立物料。其中工件集合為I={I1,I2,…,Im}，機(jī)器集合為J={J1,J2,…,Jm}，不確定每個(gè)工件的加工機(jī)器，也不確定加工不同工件的工序的先后順序，因此具有較大的靈活性。其中：工件具有H道工序；Oih表示第i個(gè)工件的第h道工序，每個(gè)Oih可以在相容的機(jī)器上任意加工，且不可重復(fù)加工同一個(gè)工件的同一道工序；pijh表示工件i的第h道工序在機(jī)器j上加工時(shí)間。在日常的加工過程中，除了機(jī)器加工時(shí)間之外，RGV移動(dòng)、物料上下料、清洗加工完成的工件都是不可忽略的。因此本文引入以下參數(shù)：eijh表示工件i的第h道工序在機(jī)器j上加工結(jié)束時(shí)間；qijh表示工件i的第h道工序在機(jī)器j上下料所需時(shí)間；a表示RGV完成一個(gè)物料清洗作業(yè)所需時(shí)間；rijh表示工件i的第h道工序移動(dòng)到機(jī)器上的時(shí)間。然而某些突發(fā)性事件，比如機(jī)器加工中途的損壞，也可能會(huì)極大地影響加工的結(jié)果，形成擁堵現(xiàn)象，顯著降低效率和穩(wěn)定性，得到的調(diào)度結(jié)果由于這樣的現(xiàn)象因而無法適用于實(shí)際的加工中，或者說由于效率和穩(wěn)定性的不足，只能適用于特定的加工環(huán)境中，不具有通用性。為此本文也引入了第i次維修所花的時(shí)間di、工件在機(jī)器加工時(shí)損壞的平均概率Eerr和用Nij表示工件i在機(jī)器j上是否發(fā)生故障，且假設(shè)工件一旦在加工時(shí)發(fā)生損壞后就不能再次加工或者當(dāng)作成品使用，即當(dāng)作廢料處理，這將顯著提高本問題在實(shí)際應(yīng)用中的實(shí)用性。因此，如何得到并解決具有最優(yōu)的系統(tǒng)穩(wěn)定性和加工效率的動(dòng)態(tài)調(diào)度多目標(biāo)規(guī)劃模型是一個(gè)具有實(shí)際意義的問題。

1.3 動(dòng)態(tài)調(diào)度模型的建立

1.3.1模型的約束條件

根據(jù)實(shí)際生產(chǎn)中工序的加工順序不同，并且一個(gè)工序不能同時(shí)在兩臺(tái)機(jī)器上進(jìn)行。與之相對(duì)的，任意機(jī)器一次也只能加工一個(gè)工件，因此需建立如下約束條件：

(1)

(2)

eijhi≤Tii∈[1,n],j∈[1,ω]

(3)

(4)

(5)

(6)

(7)

bih≥0,eih≥0i∈[1,n],h∈[1,hi]

(8)

式(1)和式(2)表示第i個(gè)工件在工序上存在先后順序，即工件的加工次序不可隨意打亂，bijh表示工件i的第h道工序在機(jī)器j上加工開始時(shí)間，pijh表示工件i的第h道工序在機(jī)器j上的加工花費(fèi)時(shí)間；式(3)表示任何一個(gè)工件的完工時(shí)間一定是小于最大完工時(shí)間，Ti表示最大完成時(shí)間，即加工所有工件的總時(shí)間；式(4)表示對(duì)一臺(tái)機(jī)器不能同時(shí)加工兩個(gè)工件，M表示一個(gè)足夠大的正數(shù)；式(5)表示第i個(gè)物料加工第h道工序所花費(fèi)的總時(shí)間，Pij表示工件i從開始向機(jī)器j移動(dòng)到在機(jī)器上結(jié)束加工所需的總時(shí)間，包含工件的上下料時(shí)間、RGV的移動(dòng)時(shí)間、機(jī)器加工時(shí)間以及完成一次清洗作業(yè)所需時(shí)間；式(6)表示任意時(shí)刻的一道工序只能在一臺(tái)機(jī)器加工；式(7)表示任意時(shí)刻同時(shí)加工機(jī)器的總數(shù)一定小于機(jī)器總數(shù)，Lijh表示工件i的第h道工序是否在機(jī)器j上加工，其值為1表示肯定，反之0表示否定；式(8)表示任意變量參數(shù)必須為正數(shù)。

1.3.2存在故障的模型優(yōu)化

根據(jù)實(shí)際情況，需考慮機(jī)器可能在工件加工過程中發(fā)生故障的作業(yè)情況，因此需要引入故障發(fā)生的概率及其發(fā)生的時(shí)間，增加約束條件，以保證模型的合理。

多道工序發(fā)生故障的動(dòng)態(tài)調(diào)度模型相對(duì)上文，將所有bijh、eijh替換為sijh、cijh，其中：sijh表示考慮機(jī)器損壞時(shí)工件i的第h道工序在機(jī)器j上加工開始的時(shí)間；cijh表示考慮損壞時(shí)工件i的第h道工序在機(jī)器j上加工結(jié)束時(shí)間，在此之后增加如下約束條件：

(9)

di∈[Errmin,Errmax]

(10)

式中：Nij表示第i個(gè)工件的第j個(gè)工序是否發(fā)生故障，其中1表示發(fā)生，0表示不發(fā)生。

之后將式(2)、式(4)分別轉(zhuǎn)化成：

(11)

(12)

式(9)表示工件i在機(jī)器j上加工發(fā)生故障的概率，本文中的概率設(shè)置為0.1；式(10)表示故障發(fā)生一次的時(shí)間的范圍，di表示第i次發(fā)生故障維修時(shí)間，Errmin、Errmax表示故障維修的時(shí)間上下限；式(11)表示在存在損壞的前提下第i個(gè)工件的加工順序存在先后關(guān)系，本文假定當(dāng)機(jī)器發(fā)生損壞時(shí)，其加工工件當(dāng)作廢料丟棄處理，即丟棄的工件后一道工序的開始時(shí)間無限延期；式(12)表示在存在損壞的前提下同一時(shí)刻同一臺(tái)機(jī)器能加工的工序是唯一的，tijh表示工件i的第h道工序在機(jī)器j上發(fā)生故障時(shí)此工序已加工時(shí)間。

1.3.3目標(biāo)函數(shù)與綜合評(píng)價(jià)函數(shù)

最終的目標(biāo)是在加工工件的個(gè)數(shù)固定前提下時(shí)間達(dá)到最小，其目標(biāo)函數(shù)是：

f1=min{Ti}

(13)

同時(shí)機(jī)器在加工過程中可能出現(xiàn)故障，為了量化目標(biāo)在規(guī)定時(shí)間內(nèi)加工的工件的相對(duì)優(yōu)略，檢驗(yàn)在消除損壞影響下的機(jī)器執(zhí)行效率，故引入綜合評(píng)價(jià)函數(shù)：

(14)

式中：α和β為各自權(quán)重；Ti1是無維修時(shí)的完成時(shí)間；Ti2是有維修時(shí)的完成時(shí)間，使得在保證加工系統(tǒng)的穩(wěn)定性的同時(shí)也能保證加工的完成時(shí)間較小。

2 多分段遺傳編碼改進(jìn)遺傳算法

2.1 多分段遺傳編碼的構(gòu)建

本文針對(duì)實(shí)際生產(chǎn)中的復(fù)雜情況設(shè)計(jì)了一種整數(shù)編碼，由機(jī)器選擇部分、工序排序部分、故障概率部分和工序選擇部分四部分組成。

機(jī)器選擇(Machine Selection,MS)部分：此部分染色體長度為T0。要求每個(gè)編碼必須是整數(shù),每一個(gè)編碼中的整數(shù)代表當(dāng)前工序選擇的加工機(jī)器在可加工機(jī)器里的編號(hào)。這就保證了后續(xù)的操作都能得到可行解。

工序排序(Operations Sequencing,OS)部分：染色體長度為T0。采用整數(shù)編碼，其中整數(shù)為工件號(hào)，工件號(hào)出現(xiàn)的先后順序代表加工的先后順序。這種方法使得編碼更加穩(wěn)定,也能保證后續(xù)的操作都能得到可行解。

故障概率(Failure Probability,FP)部分：染色體長度等于所有工件的工序之和T0。其順序與工序排序部分的順序相對(duì)應(yīng)。其中：1表示機(jī)器出現(xiàn)故障；0表示機(jī)器正常運(yùn)行，而在實(shí)際的生產(chǎn)過程中，對(duì)于加工損壞的工件是進(jìn)行丟棄處理。

工序選擇(Process Selection,PS)部分：染色體長度等于所有機(jī)器的個(gè)數(shù)T1。第j個(gè)空格表示第j個(gè)機(jī)器只可執(zhí)行的工序。其中：空格中數(shù)字為1表示此機(jī)器加工第一工序；數(shù)字為2表示加工第二工序，以此類推。

染色體編碼如圖1所示，此處只例舉工件1和工件2的所有工序。工件1的第一道工序有五臺(tái)機(jī)器可選擇進(jìn)行加工，與之對(duì)應(yīng)的4表示第四臺(tái)機(jī)器是可加工的，即表示工件O11在機(jī)器上加工。而對(duì)于后續(xù)的工序排序部分，假設(shè)一開始進(jìn)行加工的工序染色體為[22112]，其中第一個(gè)2代表第二個(gè)工件的第一道工序，即O21，故各工件的工序加工順序?yàn)椋篛21-O22-O11-O12-O23。

圖1 多分段遺傳編碼

2.2 遺傳算法的求解

2.2.1初始化

初始化是遺傳算法中的第一步，T是最大進(jìn)化代數(shù)，隨機(jī)生成M個(gè)基因個(gè)體作為初始群體。本文根據(jù)需要考慮機(jī)器選擇帶來的機(jī)器負(fù)荷問題的原因，使用全局選擇操作對(duì)染色體進(jìn)行初始化，使得每個(gè)被選取的機(jī)器都能保證在工作，進(jìn)而提高利用率。

全局選擇的步驟如下：首先取一個(gè)長度與機(jī)器數(shù)目相同的整形數(shù)組，其中數(shù)組的序號(hào)依次為機(jī)器的序號(hào)，數(shù)組位置上的值初始化為0。隨機(jī)選擇當(dāng)前要加工的工件，在可選機(jī)器中找到所花時(shí)間最小(工件移動(dòng)到該機(jī)器的時(shí)間、機(jī)器上料時(shí)間以及機(jī)器加工工件的所需時(shí)間)的加工機(jī)器，將所選擇的加工機(jī)器加工對(duì)應(yīng)的數(shù)值更新到數(shù)組中，以此類推直到該工件加工完成。再重新選擇一個(gè)工件開始，直到所有的加工任務(wù)完成。用全局選擇方法可以保證機(jī)器加工時(shí)間最短的先被選中且機(jī)器加工的工作負(fù)荷平衡。

舉例說明，假設(shè)第一次隨機(jī)抽取到工件I1，第二次隨機(jī)抽取到工件I2，則執(zhí)行前兩道工序的過程如圖2所示。

圖2 全局選擇流程圖

2.2.2選 擇

用上文全局選擇方法對(duì)種群進(jìn)行初始化后要執(zhí)行選擇操作，對(duì)機(jī)器選擇、工序排序、故障概率和工序選擇四個(gè)部分每次選取全局最優(yōu)解中的90%，淘汰相對(duì)情況不太好的10%，以此得到最終較優(yōu)的局部最優(yōu)解。

2.2.3交 叉

對(duì)于選擇進(jìn)化出下一代的個(gè)體，隨機(jī)找到兩個(gè)不同的基因，根據(jù)交叉發(fā)生的概率，進(jìn)行相互交換，產(chǎn)生新的下一代個(gè)體。交叉操作中一共分為機(jī)器選擇部分、工序排序部分、故障概率部分以及工序選擇四部分。

(1) 機(jī)器選擇部分：為保證每個(gè)基因的先后順序不變，此部分采用了均勻交叉的操作。主要步驟如下：

Step1在[1,T0]內(nèi)隨機(jī)產(chǎn)生一個(gè)整數(shù)r1，再隨機(jī)得到r1個(gè)不同的整數(shù)；

Step2依據(jù)上述步驟得到整數(shù)r1，進(jìn)而將父代染色體P1和P2內(nèi)對(duì)應(yīng)位置的基因根據(jù)目標(biāo)位置機(jī)器數(shù)范圍比例復(fù)制到子代染色體C1和C2中，保持它們的位置和順序；

Step3將P1和P2余下的基因順次復(fù)制到C1和C2中，保證它們的位置一致，順序不變。

圖3為機(jī)器選擇部分的互換交叉過程。

圖3 機(jī)器選擇部分的交叉

(2) 工序排序部分：將每個(gè)染色體中對(duì)多個(gè)工件進(jìn)行操作，更好地繼承父輩的優(yōu)良基因。

Step1使得工件集{I1,I2,…，In}隨機(jī)劃分成兩個(gè)不同的工件集；

Step2將父代染色體P1和P2中包含在上述劃分的兩個(gè)工件集中的工件復(fù)制到C1和C2，保證它們的位置一致，順序不變；

Step3將P1和P2中不包括在上面劃分的兩個(gè)工件集中的工件復(fù)制到C2和C1，同時(shí)要保證它們的順序不變。

圖4為工序排序部分的互換交叉過程。

圖4 工序排序部分的交叉

(3) 故障概率部分：

Step1在區(qū)間[1,T0]內(nèi)隨機(jī)產(chǎn)生一個(gè)整數(shù)r1，再次隨機(jī)產(chǎn)生r1個(gè)互不相同的整數(shù)；

Step2將染色體P1和P2中對(duì)應(yīng)的位置進(jìn)行交叉。

圖5為故障概率部分的互換交叉過程。

圖5 故障概率部分的交叉

(4) 工序選擇部分：

Step1在區(qū)間[1,T1]內(nèi)隨機(jī)產(chǎn)生一個(gè)整數(shù)r2，再隨機(jī)產(chǎn)生r2個(gè)互不相同的整數(shù)；

Step2將染色體P1中r2個(gè)位置相互交換，P2以此類推。

圖6為工序選擇部分的互換交叉過程。

圖6 工序選擇部分的交叉

2.2.4變 異

變異通過對(duì)染色體的隨機(jī)微小改變，使得產(chǎn)生一組新的個(gè)體，提高了種群多樣性，并且一定程度上改變了局部搜索能力。

(1) 機(jī)器選擇部分：

Step1在變異染色體中隨機(jī)選取r1個(gè)位置；

Step2順序選擇所有的基因，對(duì)所有位置的機(jī)器設(shè)置為現(xiàn)在工序機(jī)器集合里可被選擇且同時(shí)加工時(shí)間最短的機(jī)器。

(2) 工序排序部分：

Step1在變異染色體中隨機(jī)選擇r1個(gè)不同基因，然后根據(jù)選取基因生成此排序的所有鄰域；

Step2將所有的鄰域相應(yīng)適應(yīng)值進(jìn)行評(píng)價(jià)，選出其中最優(yōu)的個(gè)體作為下一子代。

(3) 故障概率部分：

Step1按照隨機(jī)數(shù)r1再隨機(jī)產(chǎn)生r1個(gè)互不相等的整數(shù)；

Step2將染色體P1和P2中對(duì)應(yīng)的位置進(jìn)行互換變異。

(4) 工序選擇部分：

Step1按照隨機(jī)數(shù)r1再隨機(jī)產(chǎn)生r2個(gè)互不相等的整數(shù)；

Step2將染色體P1中r2個(gè)位置自身變異，變異成一個(gè)在工序數(shù)以內(nèi)的隨機(jī)正整數(shù)。

2.2.5創(chuàng)新特點(diǎn)

為了解決如何在機(jī)器的加工工序未知、引入機(jī)器故障的情況下選擇出較優(yōu)的加工分配方案的問題，本文在遺傳編碼中引入了工序排序部分和機(jī)器故障部分，提高了算法的并行性和準(zhǔn)確性，進(jìn)一步增加了此類問題結(jié)果的有效性。

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

為了驗(yàn)證所建模型，本文使用一種在實(shí)際生產(chǎn)中被使用的智能化RGV動(dòng)態(tài)調(diào)度測(cè)試算例進(jìn)行驗(yàn)證。

根據(jù)不同的加工參數(shù)，此算法都能得到同時(shí)考慮系統(tǒng)穩(wěn)定性和效率的解決方案，而不單單只考慮效率，并且不只使用同一種解決方案，體現(xiàn)了算法的動(dòng)態(tài)性。

假設(shè)情況中可進(jìn)行加工的機(jī)器共有8臺(tái)，由1輛軌道式自動(dòng)引導(dǎo)車(RGV)、8臺(tái)計(jì)算機(jī)數(shù)控機(jī)床(Computer Number Controller，CNC)、1條直線軌道、1條下料傳送帶、1條上料傳送帶等附屬設(shè)備組成，模擬圖如圖7所示。

圖7 智能加工系統(tǒng)示意圖

由于尚沒有可靠的標(biāo)準(zhǔn)算例可以用于此類柔性流水車間調(diào)度問題并被驗(yàn)證可靠，因此將其工作時(shí)的相關(guān)參數(shù)進(jìn)行如表1所示的定義。

表1 加工系統(tǒng)作業(yè)參數(shù) s

其在遺傳算法中的參數(shù)、加工過程中的參數(shù)與穩(wěn)定性函數(shù)中參數(shù)的數(shù)值定義如表2所示。

表2 參數(shù)設(shè)置

表中:pm是變異概率；pc是交叉概率；α、β是綜合評(píng)價(jià)函數(shù)的兩個(gè)參數(shù)；Errmin、Errmax是機(jī)器損壞時(shí)間的上下界。

假設(shè)一個(gè)元件被2臺(tái)平行機(jī)器進(jìn)行加工，一個(gè)加工第一道工序，另一個(gè)加工第二道工序。分別假設(shè)加工機(jī)器為單臺(tái)加工機(jī)器和兩臺(tái)平行放置的機(jī)器，故用表1中的數(shù)據(jù)進(jìn)行模擬時(shí)沒有RGV的移動(dòng)時(shí)間，8臺(tái)機(jī)器加工的工件件數(shù)與2臺(tái)機(jī)器加工的工件件數(shù)之比分別會(huì)小于4。為了評(píng)價(jià)該模型的實(shí)用性，2臺(tái)機(jī)器加工設(shè)置了4、3、2三個(gè)指標(biāo)，數(shù)值越高代表模型實(shí)用性較優(yōu)，數(shù)值越低代表模型實(shí)用性較差。

表1中所給的三組數(shù)據(jù)共分為兩種情況：情況一為加工第一道工序所需時(shí)間大于加工第二道工序所需時(shí)間，即算例1、算例3；情況二為加工第一道工序所需時(shí)間小于加工第二道工序所需時(shí)間，即算例2。兩類流水線的示意圖如圖8所示。

(a)(b)圖8 兩類流水線的示意圖

假定使用2臺(tái)機(jī)器分別加工第一道工序和第二道工序并且平行放置，則加工工件的最大值滿足：

(15)

式中：ehk代表數(shù)組k中CNC加工第h道工序所需時(shí)間；q1k代表數(shù)組k中部分CNC一次上下料所需的時(shí)間；q2k代表數(shù)組k中另一部分CNC一次上下料所需的時(shí)間；ak代表數(shù)組k中RGV完成一個(gè)物料的清洗作業(yè)所需時(shí)間；e(3-h)k代表數(shù)組k中的CNC加工第3-h道工序所需時(shí)間，并要求ehk大于e(3-h)k。

以加工150個(gè)工件為例，計(jì)算8臺(tái)機(jī)器在規(guī)定件數(shù)下加工所需的時(shí)間與只有2臺(tái)機(jī)器時(shí)在規(guī)定件數(shù)下加工所需的時(shí)間長度數(shù)之比，結(jié)果如表3所示。并計(jì)算3種算例的平均數(shù)表示該模型的實(shí)用性，其平均值為3.34。由于作業(yè)參數(shù)比例越大越好并且其最大值為4，故該模型實(shí)用性較好。

表3 加工系統(tǒng)作業(yè)參數(shù)

同樣以加工150件工件為例，對(duì)于無故障的加工時(shí)間求解來說就是在前面的基礎(chǔ)上將故障概率部分都設(shè)為0。根據(jù)是否使用此調(diào)度算法得到了兩種調(diào)度方案，不使用此調(diào)度方案的執(zhí)行方式是可能在遇到損壞并還未維修完成的機(jī)器上仍舊進(jìn)行加工，其可能導(dǎo)致之后將要加工時(shí)出現(xiàn)擁堵現(xiàn)象。對(duì)得到的兩種不同的帶有故障的時(shí)間與未帶故障時(shí)求解得到的時(shí)間計(jì)算穩(wěn)定性函數(shù)。

由于遺傳算法的局限性和故障發(fā)生的隨機(jī)性，一次運(yùn)算的結(jié)果往往不具有代表性，因此本文對(duì)大量運(yùn)算結(jié)果進(jìn)行了處理。

在配置為：Intel i5-6300HQ的CPU，主頻為2.3 GHz，內(nèi)存為16 GB的個(gè)人電腦上運(yùn)行。對(duì)每組進(jìn)行50次重復(fù)實(shí)驗(yàn)，并求取各算例下不同算法的加工總時(shí)間，進(jìn)一步求取平均值，得到減小每次隨機(jī)誤差后的綜合評(píng)價(jià)值，結(jié)果如表4所示。

表4 模型的綜合評(píng)價(jià)

將各個(gè)算例下不同算法的時(shí)間做成折線圖，如圖9所示。

圖9 兩類算法的時(shí)間對(duì)比

綜上所述，此模型可以得到一個(gè)既滿足穩(wěn)定性高又滿足所花時(shí)間少的調(diào)度優(yōu)化結(jié)構(gòu)。

4 結(jié) 語

本文在研究此柔性作業(yè)車間調(diào)度問題的相應(yīng)特點(diǎn)的前提下，提出了解決該問題的多段染色體編碼的遺傳算法優(yōu)化算法。該算法對(duì)機(jī)器選擇部分、工序排序部分、故障概率部分和工序選擇部分四部分，分別使用了不同的編碼方式。多段編碼保證了在求解過程中問題解的穩(wěn)定性與可解性的提升。在實(shí)際問題的模型構(gòu)建中，考慮了對(duì)于機(jī)器損壞的時(shí)間以及機(jī)器運(yùn)動(dòng)的時(shí)間，進(jìn)而減少了約束條件，保證問題與實(shí)際相符合。同時(shí)通過使用相應(yīng)算例對(duì)模型進(jìn)行驗(yàn)證，由數(shù)據(jù)與對(duì)比結(jié)果進(jìn)一步驗(yàn)證了此算法的有效性以及實(shí)用性。根據(jù)兩種調(diào)度方案所需時(shí)間以及與得到的加工系統(tǒng)作業(yè)參數(shù)均值為3.34進(jìn)行對(duì)比，進(jìn)而驗(yàn)證本文所構(gòu)建模型的實(shí)用性較好。

在實(shí)際問題中常常會(huì)出現(xiàn)機(jī)器的損壞，從而給最終結(jié)果造成極大的誤差。為了避免此類問題的發(fā)生，我們引入了綜合評(píng)價(jià)函數(shù)，使得最終結(jié)果在滿足穩(wěn)定性高的情況下得到數(shù)據(jù)的最大化。同時(shí)更貼近實(shí)際生產(chǎn)過程中會(huì)出現(xiàn)機(jī)器損壞導(dǎo)致作業(yè)中斷的情況，即可能導(dǎo)致之后將要在損壞并還未維修完成的機(jī)器上進(jìn)行加工時(shí)造成擁堵現(xiàn)象。最后通過調(diào)度算法有效緩解了該擁堵現(xiàn)象。