車(chē)間作業(yè)調(diào)度研究范文

本站小編為你精心準(zhǔn)備了車(chē)間作業(yè)調(diào)度研究參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫(xiě)作靈感。歡迎深入閱讀并收藏。

《機(jī)械設(shè)計(jì)與制造工程雜志》2014年第六期

1問(wèn)題描述

本文研究的某加工車(chē)間是典型的流水車(chē)間，柔性流水車(chē)間調(diào)度問(wèn)題一般描述如下:有n種待加工工件Ji(i=1，2，…，n)，每種工件有ai個(gè)，每個(gè)零件表示為Jia(a=1，2，…，ai)，m種可用于加工工件的機(jī)器Mj(j=1，2，…，m)，每種機(jī)器有bj個(gè)相同并行機(jī)，每臺(tái)機(jī)器表示為Mjb(b=1，2，…，bj)，設(shè)第k道工序的機(jī)器為瓶頸機(jī)器。工件Ji的加工過(guò)程由m個(gè)操作Oi1，Oi2，…，Oim組成，且各工件預(yù)先給定的工藝路徑均相同，操作Oij的加工時(shí)間為Pij，每種機(jī)器Mj上可以同時(shí)加工相同種類(lèi)的零件cj個(gè)，且機(jī)器一旦開(kāi)始加工不能停止。經(jīng)典的柔性流水車(chē)間問(wèn)題如圖1所示。傳統(tǒng)的調(diào)度問(wèn)題是基于機(jī)器唯一性原則和流水順序不變?cè)瓌t進(jìn)行研究，但實(shí)際生產(chǎn)中，此約束存在一定程度的松弛:a．加工批量約束松弛。一臺(tái)機(jī)器同一時(shí)刻只能加工一個(gè)或一批工件。而實(shí)際加工車(chē)間同一工序的每次加工批量并不相同，或者前后相鄰工序間的加工批量也不盡相同。b．工藝順序松弛。加工車(chē)間為了緩解瓶頸設(shè)備的壓力，在允許工序超越的情況下，調(diào)換瓶頸工序和其相鄰的后續(xù)工序的加工順序，即存在加工順序局部可調(diào)的現(xiàn)象。此問(wèn)題與工藝路線可變的作業(yè)車(chē)間調(diào)度問(wèn)題既有相似性又有很大的不同。工藝路線可變的作業(yè)車(chē)間調(diào)度問(wèn)題指每個(gè)零件的加工工藝路線可能有幾條，具體選擇哪一條工藝路線要視機(jī)器的空閑情況和調(diào)度問(wèn)題的目標(biāo)而定;而該問(wèn)題加工順序只是局部調(diào)整，并不存在幾條不一樣的加工路線，即存在工序順序松弛現(xiàn)象。本文所研究的問(wèn)題是柔性流水車(chē)間調(diào)度問(wèn)題中的一種特殊情況，即考慮加工批量約束松弛和瓶頸工序順序松弛的新型柔性流水車(chē)間調(diào)度問(wèn)題。

2數(shù)學(xué)模型

柔性流水調(diào)度研究假設(shè):(1)不考慮零件加工的優(yōu)先權(quán);(2)操作允許等待，即前一個(gè)操作未完成，后面的操作需要等待;(3)在整個(gè)加工過(guò)程中，零件每道工序的加工時(shí)間保持不變;(4)每臺(tái)設(shè)備前都有一個(gè)無(wú)限容量的緩沖;(5)在零時(shí)刻所有零件都可開(kāi)始加工;(6)工序一旦開(kāi)始不允許中斷;(7)不考慮零件在機(jī)器間的轉(zhuǎn)移時(shí)間、準(zhǔn)備時(shí)間。所建數(shù)學(xué)模型如下:式(1)為數(shù)學(xué)模型的目標(biāo)函數(shù)，以最小化調(diào)度系統(tǒng)的Makespan為優(yōu)化目標(biāo);式(2)表示在時(shí)刻t、處于工序j加工的工件數(shù)必須不超過(guò)那個(gè)時(shí)刻可利用的機(jī)器數(shù);式(3)表示操作一旦開(kāi)始就不允許中斷;式(4)是順序約束;式(5)表示工件Jia在機(jī)器Mj的時(shí)間為加工時(shí)間;式(6)表示工件Jia在機(jī)器Mjb所占用的所有時(shí)間間隔在其完成時(shí)間之前;式(7)表示工件Jia在機(jī)器Mjb開(kāi)始時(shí)間應(yīng)在時(shí)間間隔(Ciaib－Pij)后;式(8)表示同一時(shí)間每臺(tái)機(jī)器最多加工的相同種類(lèi)工件數(shù)量應(yīng)小于等于機(jī)器可以同時(shí)加工的工件數(shù);式(9)表示相同機(jī)器上，下個(gè)零件的開(kāi)始時(shí)間在上個(gè)零件結(jié)束時(shí)間之后;式(10)、(11)、(12)是決策變量;式(12)表示一臺(tái)機(jī)器在相同時(shí)刻只能加工相同種類(lèi)的零件，且當(dāng)j，b，t不變時(shí)，只有一個(gè)i能使其值為1，其余均為0。

3基于遺傳算法的求解方法

遺傳算法(GeneticAlgorithm，GA)具有優(yōu)良的并行性和全局尋優(yōu)能力，在求解FFSS時(shí)，序號(hào)編碼方式比非序號(hào)編碼更直接、更方便，但序號(hào)編碼的染色體不能在任意位置進(jìn)行交叉，必須使用PMX、OX和CX等特殊的交叉算子，這些交叉算子遺傳操作過(guò)程復(fù)雜，計(jì)算效率不高。李茂軍［11－12］等提出的單親遺傳算法(ParthenoGeneticAlgo-rithm，PGA)取消了傳統(tǒng)序號(hào)編碼GA的交叉算子，代之以?xún)H在一條染色體上操作的基因重組等遺傳算子，簡(jiǎn)化了遺傳操作，提高了計(jì)算效率，并且不要求初始群體的多樣性，也不存在“早熟收斂”問(wèn)題［11］。文獻(xiàn)［12］證明了PGA的基因重組算子隱含了序號(hào)編碼TGA的交叉算子的功能，并沒(méi)有影響進(jìn)化，并驗(yàn)證了PGA在flowshop問(wèn)題中的應(yīng)用效果，因此本文采用PGA進(jìn)行求解。隨機(jī)產(chǎn)生初始化染色體種群，計(jì)算當(dāng)代種群中個(gè)體適應(yīng)度，適應(yīng)度函數(shù)以柔性flowshop調(diào)度問(wèn)題的最大完工時(shí)間maxCiamb為判斷依據(jù)，對(duì)適應(yīng)度函數(shù)值較小的個(gè)體以較大概率進(jìn)行保留，再通過(guò)基因易位操作產(chǎn)生新一代染色體種群，如此循環(huán)直到滿(mǎn)足終止條件，輸出最優(yōu)調(diào)度方案。

3．1編碼文獻(xiàn)［13］針對(duì)混合流水車(chē)間調(diào)度問(wèn)題設(shè)計(jì)了如下形式的染色體:染色體由S個(gè)小段組成，每小段表示一道加工工序，每個(gè)小段包括L個(gè)不同的基因，第p段(1≤p≤S)上的每個(gè)基因apq表示第q(1≤q≤L)個(gè)工件在第p道工序上加工的機(jī)器和加工次序。其中apq由整數(shù)和小數(shù)兩部分組成，整數(shù)部分代表工序p加工用的工序序號(hào)，小數(shù)部分表示在同一臺(tái)機(jī)器上加工發(fā)生沖突后的先后順序。如果某臺(tái)機(jī)器上存在需要加工兩個(gè)或兩個(gè)以上的工件的沖突，此時(shí)小數(shù)部分決定加工它們的先后順序，較小的數(shù)先被加工。此編碼方式無(wú)法對(duì)批量約束松弛問(wèn)題進(jìn)行求解，因此本文在文獻(xiàn)［14］的基礎(chǔ)上做了如下改進(jìn):a．a(chǎn)pq改由3位數(shù)組成。百位表示工件在該道工序的第(apq/100)臺(tái)并行機(jī)上加工，十位和個(gè)位用確切的數(shù)字表示工件在該機(jī)器上的加工次序，如apq=302表示工件q的第p個(gè)工序在該工序的第3臺(tái)并行機(jī)上第2個(gè)加工。b．在同一個(gè)工序同一臺(tái)機(jī)器上加工的工件，其編碼的十位數(shù)和個(gè)位數(shù)表示的加工次序必須是從1開(kāi)始并且連續(xù)地遞增，不能跳躍遞增。例如不允許工序1在第一臺(tái)機(jī)器上加工的編碼為101、103。c．允許同一工序同一機(jī)器上不同工件具有相同的編碼，即表示幾個(gè)不同的工件在該機(jī)器上同時(shí)加工(同時(shí)開(kāi)始同時(shí)結(jié)束)，但是不同工件的個(gè)數(shù)要小于等于該機(jī)器上允許同時(shí)加工的零件數(shù)。d．由于假設(shè)只有相同種類(lèi)的零件才能同時(shí)加工，所以相同的編碼只能出現(xiàn)在同一種類(lèi)的零件中。例如，某車(chē)間有2類(lèi)工件，第1類(lèi)工件有3個(gè)，第2類(lèi)工件有4個(gè)。每類(lèi)工件都有3道工序:第1道工序的并行機(jī)機(jī)器數(shù)為2，第2道工序的并行機(jī)機(jī)器數(shù)為3，第3道工序的并行機(jī)機(jī)器數(shù)為1。用此編碼方式，得到此柔性flowshop調(diào)度問(wèn)題的一個(gè)染色體為:該染色體第1行表示第1道工序:工件3在并行機(jī)1上第1個(gè)加工，在并行機(jī)2上依次加工的工件號(hào)為1，5，2，6，4，7。第2行表示第2道工序:工件1在并行機(jī)1上第1個(gè)加工，工件3，6在并行機(jī)2上加工，加工次序?yàn)楣ぜ?，6，工件2，4，5，7在并行機(jī)3上加工，加工次序?yàn)楣ぜ?，5，4，7。第3行表示第3道工序:工件1，3在并行機(jī)1上第1個(gè)同時(shí)開(kāi)始加工，工件2在并行機(jī)1上第2個(gè)開(kāi)始加工，工件5，6在并行機(jī)1上第3個(gè)同時(shí)開(kāi)始加工，工件4，7在并行機(jī)1上第4個(gè)同時(shí)開(kāi)始加工。

3．2選擇算子采用基于輪盤(pán)賭的比例選擇法確定哪些個(gè)體被選擇進(jìn)行基因移位操作。為防止過(guò)早收斂，本文采用非線性排序來(lái)確定個(gè)體被選擇的概率，首先將種群中各染色體按適應(yīng)度值從高到低進(jìn)行排序，使得排在前面的適應(yīng)度值較高的個(gè)體被選擇到的概率ui也較大。

3．3基因移位算子基因移位操作是按一定的概率把一條染色體中的一個(gè)(或一些)子串中的基因依次后移，并把該子串的最后一個(gè)基因移到最前面的位置，移位是在同一條染色體中進(jìn)行。基因移位的子串及其長(zhǎng)3．4解碼編碼操作和遺傳操作會(huì)得到不同的染色體，這些染色體必須利用解碼技術(shù)才能被轉(zhuǎn)化成各個(gè)機(jī)器上工件的實(shí)際加工順序。本文解碼算法的偽代碼如下:

4算例及結(jié)果分析

算例來(lái)自某車(chē)間實(shí)際算例。該車(chē)間有2類(lèi)工件，第1類(lèi)工件有3個(gè)，第2類(lèi)工件有4個(gè)。工藝順序?yàn)?粗車(chē)—精車(chē)—拉床—加工中心，每道工序并行機(jī)的數(shù)量分別為2，3，2，3。其中拉床為瓶頸設(shè)備。當(dāng)瓶頸設(shè)備繁忙時(shí)，可以調(diào)換零件在拉床和加工中心的加工順序。每個(gè)工件在每道工序上加工的時(shí)間已知，見(jiàn)表1。采用仿真軟件進(jìn)行仿真，軟件平臺(tái)為:Win—dows7操作系統(tǒng)。取基因移位操作概率為0．8，變異概率為0．05，種群規(guī)模為30，仿真代數(shù)為100。當(dāng)不考慮本文所提的約束松弛條件，只是按照傳統(tǒng)的FFSS進(jìn)行排程，所得結(jié)果如圖3所示，其Makespan為25。當(dāng)只考慮加工批量約束松弛時(shí)，所得結(jié)果如圖4所示，其Makespan為22，比不考慮加工批量約束松弛調(diào)度Makespan縮短12%。當(dāng)只考慮瓶頸工藝順序松弛時(shí)的調(diào)度結(jié)果如圖5所示，其Makespan為22，比不考慮瓶頸工藝順序松弛調(diào)度Makespan縮短12%。調(diào)整加工順序的工件是零件2和零件3。從圖4、圖5可知，考慮加工批量約束松弛和瓶頸工藝順序松弛時(shí)，得到的調(diào)度結(jié)果更優(yōu)，比不考慮約束松弛得到調(diào)度的Makespan縮短了12%。顯而易見(jiàn)，根據(jù)現(xiàn)場(chǎng)工況調(diào)整部分約束，不僅可以緩解設(shè)備能力不足帶來(lái)的生產(chǎn)壓力，更能為生產(chǎn)變更或生產(chǎn)調(diào)整提供更多的選擇余地。因此在實(shí)際的生產(chǎn)過(guò)程中，考慮約束松弛具有較強(qiáng)的實(shí)際意義。

5結(jié)束語(yǔ)

本文立足企業(yè)生產(chǎn)實(shí)際，突破傳統(tǒng)調(diào)度中假設(shè)滿(mǎn)足機(jī)器唯一性和流水順序不變等的約束，通過(guò)考慮加工批量約束松弛和瓶頸工序順序松弛，得到了Makespan性能更優(yōu)的調(diào)度方案。考慮約束松弛進(jìn)行調(diào)度優(yōu)化不僅緩解了設(shè)備能力不足帶來(lái)的生產(chǎn)壓力，更為生產(chǎn)調(diào)度管理人員實(shí)施調(diào)度提供了更多的選擇，也為分析調(diào)度約束、提高調(diào)度性能提供了實(shí)用的分析工具。未來(lái)考慮多種混合約束松弛進(jìn)行約束柔性流水調(diào)度研究，并將此研究推廣到作業(yè)車(chē)間的調(diào)度研究中。

作者：張翠林王爍王軍強(qiáng)單位：西安航空學(xué)院經(jīng)濟(jì)管理系西北工業(yè)大學(xué)生產(chǎn)與運(yùn)作系統(tǒng)性能分析中心西北工業(yè)大學(xué)現(xiàn)代設(shè)計(jì)與集成制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室