□ 趙志綱 □ 孫征虎

中國空間技術研究院 北京 100094

工序加工時間的不確定直接影響著原材料、工裝夾具、設備人員等一系列生產(chǎn)準備工作的開展，嚴重制約著車間零部件生產(chǎn)的穩(wěn)定性和有序性。相對于確定性調度問題，在加工時間不確定的作業(yè)車間調度問題中，工序加工時間為不確定隨機變量，從而導致其目標量也為變量。由于各工序的開、完工時間無法準確獲得，使該類問題的調度解只能表示為機器上的加工序列。另外，隨機變量的引入，導致問題空間更為龐大，計算效率更加低下。因此，加工時間不確定的作業(yè)車間調度問題具有參數(shù)不確定性、目標變量化、調度解序列化、問題空間龐大、求解效率低下的特點。

程蓉［1］研究了隨機機器故障干擾的作業(yè)車間魯棒調度問題，提出了一種基于鄰域的魯棒性指標，指出將該魯棒性指標結合優(yōu)秀的重調度方法是提高調度魯棒性的有效措施，但在機器故障比較嚴重時稍有不足。朱海平等［2］提出了一種支持多目標和多優(yōu)先級車間調度策略的隨機規(guī)劃模型，并給出了求解算法。劉琳等［3］針對在加工時間大范圍不確定性的調度環(huán)境中，單機Just-in-time調度，設計出一種兩層協(xié)同進化遺傳算法，解決了絕對魯棒調度優(yōu)化問題，使加工時間變化范圍內預調度的最差性能最優(yōu)化。Beck等［4］提出了加工時間不確定條件下的Job Shop調度問題的相關理論，并給出了證明過程，仿真結果表明了這些理論的可行性和有效性。Selcuk Goren等［5］研究了不確定因素干擾下的單機調度問題，提出了魯棒性和穩(wěn)定性兩種指標，并設計了代理指標，在考慮工作時間和修復時間服從概率分布的情形下，采用禁忌搜索算法進行優(yōu)化求解，仿真結果表明，其中一種代理指標的結果優(yōu)于當時已有的最優(yōu)結果。于艾清等［6］針對并行機調度中的不確定工件加工時間，提出用粗糙變量來表示不確定量，并建立粗糙期望值規(guī)劃模型，設計了進化規(guī)劃算法，并改進了編碼方式和變異方法。周強等［7］討論了在不確定加工時間和機器故障的情況下，多目標流水車間調度問題的優(yōu)化過程，基于最大流程時間和最大延遲時間兩類目標，提出一種多目標遺傳算法，實驗結果表明該算法能較好地解決不確定條件下的Flow Shop調度問題。陳宇等［8］針對不確定環(huán)境下的Job Shop調度，提出了一種基于設備整體效能的具有魯棒性的預測調度實現(xiàn)方法，并設計了一種基于多Agent協(xié)作機制的預測調度系統(tǒng)模型。

本文基于提前/拖期這類非正規(guī)性能指標無法應用雙空間協(xié)同前攝調度方法的特點，引入了與調度解序列吻合度較高的序優(yōu)化思想。該算法將進化策略嵌入到序優(yōu)化過程中，從粗糙的評價模型到精確的評價模型，分階段進行優(yōu)化，先采用進化算法進行粗糙優(yōu)化，而后以精確模型評價各階段的較好解，達到從粗到精、逐步優(yōu)化的目的。最后通過算例仿真，驗證了該算法的正確性和有效性。

1 隨機期望值模型

提前/拖期是為了適應及時生產(chǎn)模式而提出的，它從控制生產(chǎn)成本的角度出發(fā)，對每個工件設置交貨期，工件提前完工產(chǎn)生提前懲罰成本，拖期完工產(chǎn)生拖期懲罰成本，從而盡可能地促使每個工件在交貨期節(jié)點準時完工。提前/拖期指標是指所有工件的提前/拖期懲罰成本之和，是一種非正規(guī)性能指標。

基于提前/拖期指標的加工時間不確定的作業(yè)車間調度問題可描述為：n 個工件 J=｛J1，J2，...，Jn｝在 m 臺機器 M=｛M1，M2，...，Mm｝上加工，每個工件 Ji有一組工序 O=｛，...，，且各工序的加工時間是一個不確定的隨機變量（期望和標準差已知），其中，工件早于交貨期完工將產(chǎn)生庫存成本，工件晚于交貨期完工則產(chǎn)生拖期懲罰成本。調度任務是在滿足工藝路線、機器能力等約束的前提下，確定每臺機器上的最佳加工順序，使提前/拖期總懲罰成本最低。該隨機期望值模型所需的數(shù)學符號見表1。

表1 隨機期望值模型變量說明

基于提前/拖期指標的加工時間不確定的作業(yè)車間調度問題隨機期望值模型如下：

式（1）為目標函數(shù)，即總提前/拖期懲罰成本最小。由于工序加工時間是隨機變量，使優(yōu)化目標也成為變量，因此，對基于提前/拖期指標的加工時間不確定的作業(yè)車間調度問題隨機期望值模型，其指標為總提前/拖期成本的期望值最?。皇剑?）為工件Ji的拖期量；式（3）為零件 Ji的提前量；式（4）為工藝順序約束，即：同一工件Ji內不同工序之間的時序關系約束；式（5）為機器能力約束，即：Ji同一承制機床上加工工序隊列的時序關系約束；式（6）為工件釋放期約束，即：Ji的首道工序的開工時間不早于其釋放期rdi。

為了獲取式（1）的最優(yōu)解，最易想到的方法就是遍歷解空間Θ，目標函數(shù)值最小的解即為最優(yōu)解。但是，隨著解空間Θ的不斷增大，這種枚舉方法的計算量將呈指數(shù)級增長，在實際操作中是不可行的。

因此，基于仿真能夠有效地描述系統(tǒng)的隨機性特點，利用仿真的思想來對目標值進行評價，但由于式（1）中 F（S）是隨機變量，其期望值要通過大量的仿真才可能近似獲得，這將導致問題求解過程耗時過長。因此采用仿真評價函數(shù)代替目標函數(shù)（見式7），根據(jù)仿真次數(shù)建立評價模型，這樣，一方面可以通過仿真次數(shù)控制目標值的穩(wěn)定程度，另一方面大大減少了所需的仿真次數(shù)，得到了進化策略中進行解的評估的評價模型：

▲圖1 序優(yōu)化算法流程圖

足夠大的L能確保目標值的樣本均值足夠穩(wěn)定。

2 序優(yōu)化算法

由于加工時間不確定的作業(yè)車間調度問題的解為調度列，而序優(yōu)化則采用序比較代替值進行比較，因此，將序優(yōu)化方法引入到加工時間不確定的作業(yè)車間調度問題隨機期望值模型中是非常吻合的。針對加工時間不確定的作業(yè)車間調度問題隨機期望值模型，依據(jù)序優(yōu)化和目標優(yōu)化兩個思想，在序優(yōu)化中嵌入（μ+λ）進化算法，設計出序優(yōu)化算法。

首先采用（μ+λ）進化算法對粗糙模型進行優(yōu)化，得到性能較好的前N個解；然后在精確優(yōu)化階段增加仿真次數(shù)，提高精度，同時選取優(yōu)良解的個數(shù)減少。通過逐步優(yōu)化過程，最終獲得能夠滿足需求的較好解。

因此，序優(yōu)化算法首先需要確定分幾個階段優(yōu)化、每個優(yōu)化階段有多少次仿真以及選出多少優(yōu)良解這幾個問題，其參數(shù)計算如下：

式中：ns為序優(yōu)化算法優(yōu)化過程的子階段個數(shù)；Li為子階段i仿真的次數(shù)；Ni為在子階段i選擇出的足夠好解集的大?。籰e和lr為模型仿真的長度，且Le=105，Lr=368。

式（8）～式（10）分別給出了 ns、Li、Ni的計算方法，在Li和Ni的計算過程中，對非整數(shù)的Li和Ni需要進行圓整計算。其中式（8）既保證了ns是仿真長度大于精確模型需仿真長度的Le最小值，同時又保證了ns是最后子階段足夠好候選解集個數(shù)的最小值。序優(yōu)化算法的流程圖如圖1所示。

表2 8×8算例的工藝路線參數(shù)

表3 8×8算例的各工序加工時間數(shù)字特征參數(shù)

3 算例分析

該測試算例設計過程為：8×8算例工藝路線參數(shù)見表2，不確定工序加工時間的數(shù)字特征 （期望和方差）見表3，交貨期參數(shù)見表4，并且設計各工件的提前懲罰因子和拖期懲罰因子都是1。

表4 8×8算例的交貨期參數(shù)

對于分階段優(yōu)化的序優(yōu)化算法而言，首先需要確定有多少個子階段、各階段的仿真次數(shù)及候選解的規(guī)模。設定，依據(jù)式（8）計算出優(yōu)化階段個數(shù)ns=6，由式（9）、式（10）求出各階段需仿真次數(shù)Li和候選解的規(guī)模 Ni，結果見表 5。

表5 序優(yōu)化算法結果

4 結論

提出了基于提前/拖期指標的加工時間不確定的作業(yè)車間調度問題隨機期望值模型，仿真結果表明，加工時間隨機變量服從正態(tài)分布時的最優(yōu)解序列，優(yōu)于加工時間隨機變量服從均勻分布時的最優(yōu)解序列。

［1］程蓉.復雜生產(chǎn)環(huán)境下優(yōu)化調度方法研究與系統(tǒng)實現(xiàn)［D］.武漢：華中科技大學,2006.

［2］朱海平,邵新宇,張國軍.不確定信息條件下的車間調度策略研究［J］.計算機集成制造系統(tǒng),2006,12（10）:1637-1642.

［3］劉琳,谷寒雨,席裕庚.加工時間不確定的Just-in-time單機魯棒調度［J］.控制與決策,2007,22（10）:1151-1154.

［4］Beck J Christopher,Wilson Nic.Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations ［J］.Journal of Artificial Intelligence Research,2007,28:183-232.

［5］Selcuk Goren,Ihsan Sabuncuoglu.Robustness and Stability Measures for Scheduling:Single-machine Environment［J］.IIE Transactions,2008,40（2）:66-83.

［6］于艾清,顧幸生.基于粗糙規(guī)劃的不確定加工時間的并行機調度［J］.控制與決策,2008,23（12）:1427-1431.

［7］周強,崔遜學.一種不確定條件下的多目標流水車間調度優(yōu)化算法 ［J］.模式識別與人工智能,2009,22 （1）:101-107.

［8］陳宇,陳新,陳新度.不確定環(huán)境下的多Agent魯棒性預測調度研究［J］.中國機械工程,2009（16）:1937-1943.