本站小編為你精心準備了車間作業調度研究參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《機械設計與制造工程雜志》2014年第六期

1問題描述

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

2數學模型

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

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

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

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

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

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

4算例及結果分析

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

5結束語

本文立足企業生產實際，突破傳統調度中假設滿足機器唯一性和流水順序不變等的約束，通過考慮加工批量約束松弛和瓶頸工序順序松弛，得到了Makespan性能更優的調度方案。考慮約束松弛進行調度優化不僅緩解了設備能力不足帶來的生產壓力，更為生產調度管理人員實施調度提供了更多的選擇，也為分析調度約束、提高調度性能提供了實用的分析工具。未來考慮多種混合約束松弛進行約束柔性流水調度研究，并將此研究推廣到作業車間的調度研究中。

作者：張翠林王爍王軍強單位：西安航空學院經濟管理系西北工業大學生產與運作系統性能分析中心西北工業大學現代設計與集成制造技術教育部重點實驗室