基于提前/拖期的隨機(jī)期望值模型及序優(yōu)化算法

□ 趙志綱 □ 孫征虎

中國(guó)空間技術(shù)研究院 北京 100094

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

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

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

1 隨機(jī)期望值模型

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

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

表1 隨機(jī)期望值模型變量說(shuō)明

基于提前/拖期指標(biāo)的加工時(shí)間不確定的作業(yè)車間調(diào)度問(wèn)題隨機(jī)期望值模型如下：

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

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

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

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

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

2 序優(yōu)化算法

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

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

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

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

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

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

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

3 算例分析

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

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

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

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

4 結(jié)論

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

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

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

［3］劉琳,谷寒雨,席裕庚.加工時(shí)間不確定的Just-in-time單機(jī)魯棒調(diào)度［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ī)劃的不確定加工時(shí)間的并行機(jī)調(diào)度［J］.控制與決策,2008,23（12）:1427-1431.

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

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