單機魯棒性最小提前期研究

單機魯棒性最小提前期研究

蘇燕妮，王巍*，張永智

(東北林業大學 工程技術學院，哈爾濱 150040)

摘要：現代加工制造生產實際生產環境中有很多不確定因素，為了提高企業生產效率，提高生產調度的穩定性，保證生產的有序、高效進行，針對訂單式加工單機生產過程中新產品初始加工參數錯誤的情況，本文以最小提前期為目標，首先對魯棒性測度進行說明，根據單機魯棒性對其最小提前期進行確定，并且對問題進行分析，然后構建了以EDD為原則的初始調度模型與平均提前時間的優化調度模型。運用插入空閑加工時間的方法，保證優化調度滿足魯棒性測度，并且對初始調度方案以及優化調度方案通過Matlab軟件分別進行模型仿真驗證，仿真結果表明該方法應用下的優化調度模型的適用性和有效性。得到結論：該模型有效的支持最小提前期單機生產優化調度。

關鍵詞：單機；最小提前時間；魯棒調度

中圖分類號：S 782；Q 223

文獻標識碼：A

文章編號：1001-005X(2015)02-0125-05

Abstract：There are many uncertain factors in the modern manufacturing production environment.In order to improve the production efficiency and stability of production scheduling and ensure the orderly and efficient production，and according to the situation of initial processing parameter error for new products in order-based single production process，this paper sets the minimum earliness as the goal，firstly，explains the robustness measurement and determines the minimum earliness based on single-machine robustness in advance，and build up the initial scheduling model based on EDD principle and set a scheduling model which considers the case of the average error.Based on the inserting idle processing time method，the optimal scheduling was obtained to meet robustness requirement.The initial scheduling scheme and optimal scheduling scheme were simulated by Matlab，and the simulation results showed the applicability and effectiveness of the optimized scheduling model.It is concluded that this optimal scheduling model can support a minimum earliness single-machine production effectively.

Keywords：single-machine；minimum earliness；robustness scheduling

收稿日期：2014-09-19

基金項目：黑龍江省留學歸國科學基金項目(LC201407)

作者簡介：第一蘇燕妮，本科生。研究方向：生產與運作管理。

通訊作者：*王巍，博士，副教授。研究方向：工業工程。E-mail：cedar3@163.com

Single-Machine Robustness Scheduling with Minimum Earliness

Su Yanni，Wang Wei*，Zhang Yongzhi

(College of Engineering and Technology，Northeast Forestry University，Harbin 150040)

引文格式：蘇燕妮，王巍，張永智.單機魯棒性最小提前期研究[J].森林工程，2015，31(2)：125-129.

實際生產過程中存在的各種不確定因素，如機器故障、加工時間波動、緊急訂單和返工等，可能會擾亂初始調度，影響調度目標的實現。根據對不確定因素的掌握程度，通常將其分為完全未知、部分已知和完全已知不確定因素三類[1]。完全未知不確定因素沒有任何可用信息，在有這種不確定因素干擾的情形下，一般使用反應式調度。新產品初始加工參數錯誤多數屬于完全已知不確定因素。生產調度的魯棒性通常分為性能魯棒性和調度解魯棒性兩類。性能魯棒性是指初始調度在不確定因素擾動下的實際調度目標與實際最優調度目標的接近程度，兩者越接近，初始調度的性能魯棒性越好；調度解魯棒性是指不確定因素擾動下的實際調度方案與初始調度方案的接近程度，兩者越接近，調度解魯棒性越好[2-3]。

在過去的研究中，對于在生產過程中存在新產品初始加工參數錯誤的調度問題，各學者和工程技術人員進行了廣泛的研究。由于生產之前無法獲得實際數據，Selcuk Goren等[4]給出了兩種替代測度，并且利用實際案例說明了替代測度對魯棒調度是有效的。新產品初始加工參數錯誤則會導致訂單加工取消，帶來大量的空余時間，而根據新產品初始加工參數錯誤帶來的提前時間插入空閑時間也是一種比較有效的調度方法，文獻[5]在給出三種空閑時間度量方法的基礎上，研究了插入空閑時間的魯棒調度算法，并且給出了在調度性能和魯棒性之間進行權衡的方法。對于新產品初始加工參數錯誤下魯棒調度問題的研究，許多人關注其調度的魯棒性，但調度的魯棒性與調度性能往往互相牽制、互相影響。本文研究機器故障環境下的調度問題1|rj|Tmax的棒調度方法，縮小提前時間為目標，研究其優化方法。在對問題進行描述的基礎上，首先研究求解在限定魯棒性約束下使得調度性能目標最優的調度問題，提出Tmax最優調度方法，并給出仿真實例驗算，驗證本文所提方法的適用性和有效性。

本文的研究為新產品初始加工參數錯誤環境下單機調度問題提供了提前時間最小的調度方法，在實踐中能夠減小訂單加工參數錯誤對初始調度的影響，保證在限定的魯棒性約束下保證初始調度的穩定性，提高調度目標的滿意程度。

1魯棒性指標與問題描述

1.1　符　號

本文主要用到以下符號：

rj為訂單j的釋放時間即最早可以開工的時間；Pj為訂單j的加工時間；Sj為訂單j的開工時間；dj為訂單j的交貨期；cj為訂單j的完工時間；T為平均提前時間；t為訂單無法加工的平均時間間隔；σ(k)為調度中σ第k個位置的訂單；σp為初始調度；Cmax(σ)為調度σ的最遲完工時間；Dj(σp)為實際調度σr與初始調度σp中訂單j的期望完工時間差絕對值；Tmax(σ)為調度σ的提前時間，Tmax(σ)=maxj(Cσ(j)-dσ(j))；RS為調度的魯棒性測度；Z為目標函數值，即總提前時間。

1.2　魯棒性測度

生產調度的性能魯棒性和調度解魯棒性有不同的測度方法，性能魯棒性通常用調度目標的差異度量，而調度解魯棒性通常用訂單的變化、開工或完工時間的差異等度量。Jorge等[1]用實際調度σr與初始調度σp的期望最遲完工時間差作為初始調度σp的魯棒性測度。因為初始調度σp受不確定因素擾動，剔出訂單的后續訂單完工時間均會提前，所以有Dmax(σp) ≥0。Ronan O Donovan等[3]用實際調度與初始調度各訂單期望完工時間差的絕對值之和表示調度魯棒性，即

RS=∑Dj(σρ)=E[∑|Cj(σr)-Cj(σp)|]。

公式(1)給出了在訂單j加工過程中的機器平均提前時間：

(1)

在訂單剔出環境下，調度σ的魯棒性可以定義為：

∑Dj(σp)=E[∑Cj(σr)-Cj(σp)]。

此時調度σ完成時間為

在這種情況下對于魯棒性最優的調度有

1.3　問題描述

在訂單式生產環境下，新單在試生產的過程中，極有可能因為對新產品設計及加工參數把握不當，出現生產錯誤，此時需要停止生產，對模具進行重新制定或其他處理，整個訂單將會取消并延遲生產。此時，后續訂單則會提前進行生產，從而產生加工完成時間提前于交期的現象。而停單后的下一筆訂單的開始加工時間又會影響本單以及后續訂單的完成時間。訂單完成時間小于交期會帶來庫存問題，對于現代制造企業來說，庫存即是浪費，能有效的減小成品存放對企業制造成本的減小有舉足輕重的作用。所以，應當在調度上合理控制。在保證給定調度魯棒性約束的前提下，對于調度σ，改變其開工時間，增大或減小訂單之間的空閑時間，則魯棒性也將發生變化，同時調度提前時間Tmax(σ)也將發生變化。求解在以調度魯棒性為約束性指標時，求解在滿足其要求的基礎上，使調度性能Tmax(σ)最小的調度方案。

2調度問題1|rj,RS<α|Tmax的求解

在訂單式實際生產中，通常要求在限定解魯棒性最優的調度方案，調度性能目標是最大提前時間，則問題表示為1|rj,RS<α|Tmax。

2.1　初始調度模型建立

調度方案結果顯示按照訂單交期順序進行生產，若訂單交期一樣，則按照訂單加工數量多少進行生產，數量多的優先生產，此時調度方案為最優，即“最早交貨最早加工EDD”規則。以每筆訂單交期與完成時間差值總和最小為目標函數，初始調度方案建立以下數學規劃模型(RP)：

s.tCσ(j)≥sj+pj

(1)

Cσ(j)≥sj+pj

(2)

Cσ(j)-Cσ(j-1)≥pj

(3)

sj≥Cσ(j-1)

(4)

在該模型中，約束(1)為調度中的單個訂單時間約束；約束(2)為相鄰兩個訂單的時間約束；約束(3)為后續訂單加工開始時間不得早于前訂單結束時間；約束(4)為初始完工時間。

2.2　問題分析

2.3　優化調度模型建立

在考慮平均加工時間的情況下，建立優化調度模型，其目標函數為每項訂單完工時間與交期差值的總和，此時完工時間為初始調度方案下完工時間減去平均提前時間。優化調度方案建立以下數學規劃模型(RP)：

S.t.Cσp(k)≥rk+pk

(1)

Cσ″p(k)-Cσ″p(k-1)≥Pσ″p(k)

(2)

Cσ′p(k)≤σ″p(k)

(3)

Cσ″p(0)=0

(4)

Cσ′p(k)-Cσ″p(k)≤α

(5)

在該模型中，約束(1)為調度σp″中的單個訂單時間約束；約束(2)為相鄰兩個訂單的時間約束；約束(3)為各訂單完工時間需要延后；約束(4)為設置的虛擬訂單完工時間，約束(5)為調度σp″的最大提前時間約束；約束(6)為優化調度與初始調度的魯棒性測度滿足條件。

3仿真分析

表1　加工訂單參數 Tab.1 Processing order data

3.1　初始調度方案

根據2.1中所述建立模型，本文將調度問題的條件和約束抽象為簡化的模型表達式，并把調度的評價指標作為調度模型優化的目標，調度方案以“最早交貨最早加工EDD”為規則，通過對模型的分析和求解來對的生產調度提供決策方案。為了模型的處理，提出以下假設：

(1)若某一訂單開始生產，在沒有完成之前，不能進行另外訂單的生產，即單機生產方式。

(2)由于時間約束，從開始至生產結束過程中沒有停頓，即生產是連續性的。

(3)提前時間不進行取整，即生產完到截止日期差多少時間即為實際提前期。

例如第30 d的訂單，到28.5 d完成了，提前日期為1.5 d，而不是一天或者兩天。根據建模假設，對初始調度模型進行基本排序，初始調度方案通過Matlab實現，程序片段如下：

clc

clear

k=perms(1∶9)；

k_size=size(k)；

fori=1∶k_size(1)

i

Cj=0；

Z(i)=0；

forj=1∶k_size(2)

Num=k(i，j)；

Pj=Cj+Data(3，Num)；

Cj

Z(i)=Z(i)+(Data(2，Num)-Cj)*Data(4，Num)；

end

end

MinZ=min(Z)

j=find(Z<(MinZ+1))；

σ=k(j，：)

根據程序生成的最終序列，初始調度方案結果為：5、8、9、7、1、4、3、2、6，目標函數生成提前期的結果為：10.55。以上測試表明，建立的初始調度模型是正確可行的，生產過程存在著較大的生產提前期。

3.2　優化調度方案

為了控制生產中的不確定性，定義工廠生產參數魯棒性約束為10%，即要求加工完成時間與交期偏差限定在1.055 d以減少庫存成本。按照前文2中所建立的數學規劃模型，在考慮平均提前時間的情況下，如調度結果不滿于參數魯棒性約束，則采用交期與完成時間差值最小訂單補足空閑時間，使其完成時間等于交期，該訂單后續訂單最前的開始加工時間則為該訂單的交期，后續所有訂單按照前文2中的數學規劃模型重新排序，直到滿足魯棒性約束。

訂單j加工過程中的機器故障平均維修時間為：

對工件參數進行變換，令rj′=rj,pj′=pj+E(Rj),dj′=dj+E(Rj)，參照2.3中所述約束及假設建立模型。其主程序片段如下：

clc

clear

Cj′=10.55；

k=perms(1∶9)；

k_size=size(k)；

fori=1：k_size(1)

Z(i)=0；

forj=1∶k_size(2)

Num=k(i，j)；

Cj=Cj+Data(3，Num)；

Cj

Z(i)=Z(i)+(Data(2，Num)-Cj)*Data(4，Num)；

end

end

MinZ=min(Z)

if(Cj′-MinZ)/Cj′<=0.1；

Z(i)=Z(i)+(Data(2，Num)-Cj)

else

Z(i)=Data(2，Num)-Cj；

j2((min(Z)))=[]；

whilei(i<=9)

loc=find(j2((min(Z))))；

j=find(Z<(MinZ+1))；

end

end

j=find(Z<(MinZ+1))；

σ=k(j，：)

根據文獻中的基本算法，所給參數的訂單以最小提前時間Tmin(σ)為調度性能目標，得到最優魯棒調度σ′，其中Tmin(σ)=4.03，如圖1所示，優化后的調度方案為：5、1、7、9、8、4、3、2、6。

圖1　最優調度 Fig.1 Optimal scheduling

3.3　仿真結果

通過最小提前期調度系統仿真的實際效果來看，基本上達到了優化調度的要求，通過比較兩組計算結果可以看出，在考慮新產品初始加工參數錯誤造成的訂單剔出后，對后續訂單來帶提前期影響的情況下，通過優化調度模型，獲得新的調度方案，其目標函數值表示的總提前時間明顯縮短，優化幅度達61.77%，改方案和模型是切實有效的。魯棒性RS與調度性能呈現相反的變化趨勢，要使魯棒性更好，調度性能就會變差，表明調度魯棒性的提高要以降低調度性能為代價。因此，最小提前期調度方案可以給企業的生產管理帶來一定的決策依據。

4結束語

新單在試生產或正式投入生產的過程中經常出現的不確定因素，本文針對這一情況，研究了在新單加工出現錯誤需要剔出的情況下，以調度最大提前時間的單機魯棒調度優化方法，探討了在最大提前時間約束下求解最優魯棒性的方法。在此基礎上，給出了單機魯棒行最小提前調度優化方法，并且仿真驗證了該方法的適應性和有效性。本文的研究局限于單機環境，Flow Shop和Job Shop等復雜機器環境下針對機器故障的魯棒調度問題將是進一步研究的重點。

【參考文獻】

[1]Leon V J，Wu S D，Storer R H.Robustness measures and robust scheduling for job shops[J].IIE Transactions，1994，26(5)：32-43.

[2]Sevaux M，Sorensen K.A genetic algorithm for robust schedules in a one-machine environment with ready times and due dates[J].Quarterly Journal of the Belgian，French and Italian Operations Research Societies，2004，2(2)：129-147.

[3]O Donovan R，Uzsoy R，Mckay K N.Predictable scheduling of a single machine with breakdowns and sensitive jobs[J].International Journal of Production Research，1999，37(18)：4217-4233.

[4]Goren S，Sabuncuoglu I.Robustness and stability measures for scheduling：single-machine environment[J].IIE Transactions，2008，40(1)：66-83.

[5]Briskorn D，Leung J，Pinedo M.Robust scheduling on a single machine using time buffers[J].IIE Transactions，2011，43(6)：383-398.

[6]張先超，周泓.單機魯棒調度多目標優化方法[J].計算機集成制造系統，2013，19(10)：2459-2466.

[7]何正文，劉人境，徐渝.基于隨機活動工期的資源約束項目魯棒性調度優化[J].系統工程理論與實踐，2013，33(3)：650-659.

[8]胡信布，何正文，徐渝.基于資源約束的突發事件應急救援魯棒性調度優化[J].運籌與管理，2013，22(2)：72-79.

[9]張宏國，徐曉飛，戰德臣.不確定資源約束下項目魯棒性調度算法[J].計算機應用研究，2009，26(6)：2079-2082+2089.

[10]魏巍，譚建榮，馮毅雄，等.柔性工作車間調度問題的多目標優化方法研究[J].計算機集成制造系統，2009，15(8)：1592-1598.

[11]田文迪，胡慕海，崔南方.不確定性環境下魯棒性項目調度研究綜述[J].系統工程學報，2014，29(1)：135-144.

[12]徐鳴，馬龍華，顧江萍，等.一種改進的魯棒多目標優化方法[J].控制與決策，2013，28(8)：1178-1182+1189.

[責任編輯：胡建偉]