□趙攀

北京空間技術(shù)研制試驗中心 北京 100094

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

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

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

1 預(yù)測調(diào)度模型

假設(shè)以下條件。

（1）每個工件都包含一個由多道工序組成的工序集合，工件的工序加工順序預(yù)先給定，每道工序?qū)?yīng)一臺確定的加工機(jī)器和一個加工時間 pji（j=1，...，N，i=1，...，M）；

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

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

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

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

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

▲圖1 材料短缺發(fā)生次數(shù)模糊集

▲圖2 材料短缺持續(xù)時間模糊集

用離散模糊集Og和連續(xù)模糊集Rg的模糊乘法［4］計算被干擾工件標(biāo)準(zhǔn)時間段內(nèi)總的材料短缺時間，即用二級模糊集Og?Rg來計算：

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

然后將標(biāo)準(zhǔn)模糊集應(yīng)用重心法逆模糊化［4］，用tdg值表示標(biāo)準(zhǔn)時間段內(nèi)材料短缺持續(xù)時間，則：

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

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

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

當(dāng)空閑時間idji確定后，將其加入到每個工序的加工時間pji中，應(yīng)用遺傳算法生成預(yù)測調(diào)度。預(yù)測調(diào)度產(chǎn)生基準(zhǔn)調(diào)度方案后，下發(fā)到生產(chǎn)車間指導(dǎo)生產(chǎn)，任務(wù)開始按序加工。在干擾發(fā)生之前，生產(chǎn)車間的所有機(jī)器上實際調(diào)度和預(yù)測調(diào)度的工件加工順序是相同的。

2 調(diào)度算法

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

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

2.1 編碼

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

2.2 初始種群產(chǎn)生

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

2.3 選擇操作

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

二元錦標(biāo)賽選擇法的流程可描述如下。

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

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

2.4 交叉操作

對于優(yōu)秀種群，隨機(jī)選擇出兩個染色體作為父代個體 X1、X2，通過交叉產(chǎn)生兩個子代個體 X1′、X2′，這里采用兩點(diǎn)交叉算子來生成子個體。

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

2.5 變異操作

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

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

2.6 精英進(jìn)化策略

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

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

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

3 實驗結(jié)果及分析

本節(jié)以在6臺機(jī)器上加工6個工件為例來分析模糊規(guī)則在車間作業(yè)預(yù)測調(diào)度中的應(yīng)用，并使用C++編程進(jìn)行仿真分析。

每個工件需要用一種材料，則需要6種材料，每種材料的標(biāo)準(zhǔn)時間段分別為 9 h、8 h、5 h、3 h、9 h、7 h；標(biāo)準(zhǔn)時間內(nèi)插入的空閑時間分別為6 h、5 h、3 h、1 h、3 h、5 h。

根據(jù)第3節(jié)的模糊集可以計算擴(kuò)展加工時間，見表1。

表1 工件擴(kuò)展加工時間/h

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

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

表2 最優(yōu)解工序排列方案

表3 各工件最優(yōu)完工時間/h

4 結(jié)論

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

［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］ 陳宇,陳新,陳新度,等.基于設(shè)備整體效能和多 Agent的預(yù)測-反應(yīng)式調(diào)度［J］.計算機(jī)集成制造系統(tǒng),2009,15（8）:1599-1605.

［3］ 李巧云,王冰,王曉明.隨機(jī)機(jī)器故障下單機(jī)預(yù)測調(diào)度方法［J］.系統(tǒng)工程理論與實踐,2011,31（12）:2387-2393.

［4］ 張沙清,陳新度,陳慶新,等.資源不確定環(huán)境下模具多項目預(yù)測-反應(yīng)式調(diào)度算法［J］.計算機(jī)集成制造系統(tǒng),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］ 金宏,王宏安,傅勇,等.模糊反饋控制實時調(diào)度算法［J］.軟件學(xué)報,2004,15（6）:791-798.

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

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