基于模糊集的作業車間預測調度研究

□趙攀

北京空間技術研制試驗中心 北京 100094

在生產制造業中，作業車間在實際執行生產調度計劃的過程中，會存在各種各樣的不確定影響因素，如原材料短缺、設備故障、訂單變更以及加工誤差等［1］，使車間生產實際處于一個動態變化的環境中。這些因素的存在往往會導致原有調度計劃無法按預定的調度目標正常執行，因此,研究在該不確定因素下的預測調度問題成為了當前的研究熱點。

陳宇等［2］分析了不確定性事件對生產過程的干擾和對調度過程的影響，提出了一種基于設備整體效能的具有魯棒性的預測調度實現方法，設計了一種基于多Agent協作機制的預測調度系統模型。李巧云等［3］研究了可能遭遇機器故障的工件動態到達的單機總加權拖期生產調度問題，提出了一種帶空閑時間閾值的預測調度方法,基于工件動態到達的特點,充分利用初始調度中的空閑時間,通過空閑時間閾值靈活控制空閑時間的插入與否。張沙清等［4］建立了以調度計劃變更費用最小為優化目標的預測調度模型，并提出了不確定環境下多項目預測調度算法。針對作業車間的不確定性因素，模糊集理論已經成功應用于許多不確定性生產調度問題。文獻［5-7］介紹了基于模糊邏輯的預測調度解決作業車間調度問題，在材料短缺情況下，應用模糊規則求解空閑時間的插入，進而生成預測調度。金宏等［8］應用模糊規則和模糊調度理論,提出一個基于模糊反饋控制的調度算法，并建立相應的調度架構。

本文針對材料短缺對工件加工過程的影響，以工件的最大完工時間為目標，建立基于模糊集的預測調度數學模型。應用遺傳算法求解調度方案，找出預測調度在各機器上工件的加工順序，再找到一種可行的最優調度方案，得到最合適的最大完工時間，使其具有一定的魯棒性，能夠吸收有限的材料短缺干擾。最后通過仿真程序驗證模型及算法的可行性和有效性。

1 預測調度模型

假設以下條件。

（1）每個工件都包含一個由多道工序組成的工序集合，工件的工序加工順序預先給定，每道工序對應一臺確定的加工機器和一個加工時間 pji（j=1，...，N，i=1，...，M）；

（2）每個工件都對應一種材料，同一工件各個工序用相同的材料；

（3）不同工件的工序之間沒有順序約束，每臺機器在同一時刻只能加工一道工序，工序在加工過程中不允許中斷。

在 M 臺不同的機器 Mi（i=1，...，M）上加工 N 個不同的工件 Jj（j=1，...，N）,在保證滿足假設條件又考慮材料短缺的情況下，以工件的最大完工時間Cmax為目標，找出預測調度在各機器上工件的加工順序，找到一種可行的最優調度方案。 Cmax=max｛Cji|j=1，...，N；i=1，...，M｝，其中Cji表示工件Jj在機器Mi的加工時間 （Cji=pdji）。

預測調度是為了使材料短缺產生的可能不良影響最小化。在預測調度中，在每個工件的加工時間中插入空閑時間以生成擴展加工時間的方法來吸收調度過程中一定的材料短缺干擾。工件Jj在機器Mi上的加工時間為 pdji，pdji=pji+idji（ j=1，...，N；i=1，...，M），其中 idji表示預測調度為工件Jj每個工序插入的空閑時間，它是生產過程中每標準時間段內材料短缺發生次數的模糊數和材料短缺持續時間的模糊數之積，標準時間是工件每個工序平均加工時間。有G種不同的材料mg（g=1，...，G）參與加工過程。 材料 mg的短缺發生次數用離散有限集 NOCg表示，NOCg=｛nocg1，nocg2，...，nocgK｝。標準時間內工件Jj所用材料mg短缺發生次數的模糊數用模糊集Og表示，其模糊數用μOg（nocgk）/nocgk表示，即 Og=｛［μog（nocgk）/nocgk|k=1，...，K］｝ ，如圖 1 所示。每次材料短缺持續時間用關于模糊集Rg（trg）的連續梯形函數 μRg

（trg）表示，該連續函數由（trg1，trg2，trg3，trg4）4個參數決定，如圖2所示。

▲圖1 材料短缺發生次數模糊集

▲圖2 材料短缺持續時間模糊集

用離散模糊集Og和連續模糊集Rg的模糊乘法［4］計算被干擾工件標準時間段內總的材料短缺時間，即用二級模糊集Og?Rg來計算：

為了準確計算每個工序的加工時間pji中加入的空閑時間idji，首先將二級模糊集轉換為標準模糊集，即將二級模糊集Og?Rg轉化為標準模糊集s-fuzzif（Og?Rg）［5］，標準模糊集函數方程為：

然后將標準模糊集應用重心法逆模糊化［4］，用tdg值表示標準時間段內材料短缺持續時間，則：

發生 4 次材料中斷的例子為：NOCg=｛1，2，3，4｝，

Og=0.7/1+1.0/2+0.4/3+0.25/4，Rg（trg）的梯形函數所組成的二級模糊集示例如圖3所示，則：

根據逆模糊化tdg計算插入到工件Jj工序i的空閑時間idji，idji=tdgpji/STD，其中STD為逆模糊參數常量。

當空閑時間idji確定后，將其加入到每個工序的加工時間pji中，應用遺傳算法生成預測調度。預測調度產生基準調度方案后，下發到生產車間指導生產，任務開始按序加工。在干擾發生之前，生產車間的所有機器上實際調度和預測調度的工件加工順序是相同的。

2 調度算法

▲圖3 材料mg在一定模糊數下總短缺時間的模糊值

調度模型確定后，預測調度及反應式調度都應用遺傳算法［9,10］求解。算法的基本思想是：首先采用基于優先列表編碼方式進行編碼，在該編碼方式下隨機生成初始種群；其次對種群進行評價，評價的適應度函數為最小化最大加工時間｝；評價后對種群進行選擇、交叉、變異操作，然后對種群進行精英選擇生成新一代群體，循環，直至達到最大進化代數結束，其具體過程如下。

2.1 編碼

基于編碼效率的考慮，本文采用基于優先列表的編碼方式。基于優先列表的編碼方式的染色體由M條子染色體組成，每個子染色體對應1臺機器，即對具有M臺機器的車間調度問題，基于優先列表編碼方式的染 色 體 可 以 描 述 為 ： ［σ1，σ2，...，σM］。 其 中 ：σi=［ki1，ki2，...，kiM］ 為機器 Mi（i=1，2，...，M）對應的子染色體，表示在機器Mi上待加工工件（相應操作）的加工優先表，kij（i=1，2，...，mj）為在機器 Mi上待加工工件的工件號，表示在機器Mi上待加工工件Jkji的 相 應 操 作 ，kij∈［1，2，...，N］ ，且若 x≠y，則 kjx≠kjy，mi為在機器 Mi上待加工工件（相應操作）的總數。

2.2 初始種群產生

隨機產生一種加工模式，針對該加工模式隨機產生n個加工方案，對n個加工方案進行解碼，然后將加工模式和加工方案組成一個二維向量染色體X，該種方式產生的染色體都是一個較優的可行解，如此循環產生最優染色體作為初始種群｛x1，...，xn｝。

2.3 選擇操作

本文利用二元錦標賽方法對排序較優的N個個體進行選擇，以進行后續的交叉、變異。二元錦標賽選擇法是一種基于染色體適應度排序的選擇方法，每次在若干染色體中，選擇適應度最高的一個染色體，且重復N次來得到由N個染色體組成的新一代種群。在選擇過程中，染色體是否被選擇只與染色體之間適應度的相對大小有關，而與其具體適應度無關。

二元錦標賽選擇法的流程可描述如下。

步驟1：在種群中隨機選取 2條染色體，然后選擇其中適應度最大的染色體；

步驟2：重復步驟 1，共N次，得到由 N條染色體組成的新一代種群。

2.4 交叉操作

對于優秀種群，隨機選擇出兩個染色體作為父代個體 X1、X2，通過交叉產生兩個子代個體 X1′、X2′，這里采用兩點交叉算子來生成子個體。

對于父代個體X1、X2，隨機產生兩個交叉點xp1和xp2，xp1≠xp2。通過交換兩交叉點之間的部分，得到子個體。圖4給出兩點交叉的示意圖。

2.5 變異操作

針對本文研究問題的編碼方式，采用逆操作作為變異算子，即隨機選擇染色體上某一機器對應的基因片段，然后將片段上的基因串逆。如對于 3×3問題的變異示意圖如圖 5所示，迭擇機器2上的基因片段做逆序操作。

變異操作后新個體的控制方案可以唯一確定控制成本，但其加工方案卻不一定是最優加工方案。對新個體進行局部搜索優化，此時保持個體控制方案不變，對加工方案進行禁忌搜索，以完全遍歷禁忌列表作為終止原則，尋找局部最優加工方案，提高種群質量。

2.6 精英進化策略

在較優解的基礎上進行交叉、變異操作獲得優秀后代個體的機率比較大，因此在產生新種群時，基于精英保留策略將根據偏序關系得到的優秀個體復制進入下一代，加快獲得最優解，提高求解效率。利用優秀個體進行交叉變異產生新的子代個體，將優秀個體X整體作為操作對象，這樣新種群中引入新染色體的概率比較大，提高了種群的多樣性，避免了種群早熟。

▲圖4 個體互換交叉示意圖

▲圖5 個體逆序變異示意圖

3 實驗結果及分析

本節以在6臺機器上加工6個工件為例來分析模糊規則在車間作業預測調度中的應用，并使用C++編程進行仿真分析。

每個工件需要用一種材料，則需要6種材料，每種材料的標準時間段分別為 9 h、8 h、5 h、3 h、9 h、7 h；標準時間內插入的空閑時間分別為6 h、5 h、3 h、1 h、3 h、5 h。

根據第3節的模糊集可以計算擴展加工時間，見表1。

表1 工件擴展加工時間/h

工件在機器上的加工順序：工件1為機器4、機器1、機器 2、機器 3、機器 6、機器 5；工件 2 為機器 6、機器 3、機器 5、機器 2、機器 1、機器 4；工件 3為機器 6、機器 4、機器 3、機器 2、機器 5、機器 1；工件 4為機器5、機器 1、機器 3、機器 4、機器 2、機器 6；工件 5 為機器 3、機器 2、機器 5、機器 6、機器 1、機器 4；工件 6 為機器 5、機器 4、機器 2、機器 1、機器 3、機器 6。

每個工序的空閑時間插入到各工序中得到擴展加工時間后，應用遺傳算法來生成預測調度工序排列方案和完工時間。遺傳算法中，種群大小為100；進化代數為100；染色體是基于優先列表編碼、采用隨機機制產生；選擇算子采用二元錦標賽選擇；交叉算子采用兩點互換交叉，交叉概率為0.8；變異算子采用基于優先列表的通用二進制變異方法，變異概率為0.1。遺傳算法對每個工件在機器上進行排序生成預測調度，預測調度工序排列方案和完工時間見表2和表3。

表2 最優解工序排列方案

表3 各工件最優完工時間/h

4 結論

本文建立了基于模糊集的預測調度數學模型，并應用遺傳算法找出了預測調度在各機器上工件的加工順序，找到了可行的最優調度方案，以在6臺機器上加工6個工件為例驗證了模型和算法的可行性。結果表明，當材料短缺發生時間不大于最大完工時間的五分之一，預測調度能夠吸收有限的材料短缺干擾，使其具有一定的魯棒性，因此對預測調度性能的影響不大。

［1］ Niu Ganggang,Sun Shudong,Lafon Pascal,etal.A Predictive-reactive Approach forJSP with Uncertain Processing Times ［C］.In Research in Interactive Design:Virtual,Interactiveand Integrated ProductDesign and Manufacturing for Industrial Innovation，Paris,2010.

［2］ 陳宇,陳新,陳新度,等.基于設備整體效能和多 Agent的預測-反應式調度［J］.計算機集成制造系統,2009,15（8）:1599-1605.

［3］ 李巧云,王冰,王曉明.隨機機器故障下單機預測調度方法［J］.系統工程理論與實踐,2011,31（12）:2387-2393.

［4］ 張沙清,陳新度,陳慶新,等.資源不確定環境下模具多項目預測-反應式調度算法［J］.計算機集成制造系統,2010,16（12）:2688-2696.

［5］ Petrovic D,Duenas A.A Fuzzy Logic Based Production Scheduling/rescheduling in the Presence ofUncertain Disruptions ［J］.Fuzzy Sets and Systems,2006,157 （16）:2273-2285.

［6］ Duenas A,Petrovic D.An approach to Predictive-reactive Scheduling of Parallel Machines Subject to Disruptions ［J］.Annals of Operations Research,2008,159（1）:65-82.

［7］ Petrovic S,Petrovic D,Burke E.FuzzyLogicBased Production Scheduling/Rescheduling in the Presence of Uncertainty ［J］.Planning Production and Inventories in the Extended Enterprise,2011,152:531-562.

［8］ 金宏,王宏安,傅勇,等.模糊反饋控制實時調度算法［J］.軟件學報,2004,15（6）:791-798.

［9］ 周明,孫樹棟.遺傳算法原理及應用 ［M］.北京:國防工業出版社,1999.

［10］王凌.車間調度及其遺傳算法 ［M］.北京:清華大學出版,2003.