單機(jī)魯棒性最小提前期研究

蘇燕妮，王巍*，張永智

(東北林業(yè)大學(xué) 工程技術(shù)學(xué)院，哈爾濱 150040)

摘要：現(xiàn)代加工制造生產(chǎn)實(shí)際生產(chǎn)環(huán)境中有很多不確定因素，為了提高企業(yè)生產(chǎn)效率，提高生產(chǎn)調(diào)度的穩(wěn)定性，保證生產(chǎn)的有序、高效進(jìn)行，針對(duì)訂單式加工單機(jī)生產(chǎn)過(guò)程中新產(chǎn)品初始加工參數(shù)錯(cuò)誤的情況，本文以最小提前期為目標(biāo)，首先對(duì)魯棒性測(cè)度進(jìn)行說(shuō)明，根據(jù)單機(jī)魯棒性對(duì)其最小提前期進(jìn)行確定，并且對(duì)問(wèn)題進(jìn)行分析，然后構(gòu)建了以EDD為原則的初始調(diào)度模型與平均提前時(shí)間的優(yōu)化調(diào)度模型。運(yùn)用插入空閑加工時(shí)間的方法，保證優(yōu)化調(diào)度滿足魯棒性測(cè)度，并且對(duì)初始調(diào)度方案以及優(yōu)化調(diào)度方案通過(guò)Matlab軟件分別進(jìn)行模型仿真驗(yàn)證，仿真結(jié)果表明該方法應(yīng)用下的優(yōu)化調(diào)度模型的適用性和有效性。得到結(jié)論：該模型有效的支持最小提前期單機(jī)生產(chǎn)優(yōu)化調(diào)度。

關(guān)鍵詞：?jiǎn)螜C(jī)；最小提前時(shí)間；魯棒調(diào)度

中圖分類號(hào)：S 782；Q 223

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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

基金項(xiàng)目：黑龍江省留學(xué)歸國(guó)科學(xué)基金項(xiàng)目(LC201407)

作者簡(jiǎn)介：第一蘇燕妮，本科生。研究方向：生產(chǎn)與運(yùn)作管理。

通訊作者：*王巍，博士，副教授。研究方向：工業(yè)工程。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ī)魯棒性最小提前期研究[J].森林工程，2015，31(2)：125-129.

實(shí)際生產(chǎn)過(guò)程中存在的各種不確定因素，如機(jī)器故障、加工時(shí)間波動(dòng)、緊急訂單和返工等，可能會(huì)擾亂初始調(diào)度，影響調(diào)度目標(biāo)的實(shí)現(xiàn)。根據(jù)對(duì)不確定因素的掌握程度，通常將其分為完全未知、部分已知和完全已知不確定因素三類[1]。完全未知不確定因素沒(méi)有任何可用信息，在有這種不確定因素干擾的情形下，一般使用反應(yīng)式調(diào)度。新產(chǎn)品初始加工參數(shù)錯(cuò)誤多數(shù)屬于完全已知不確定因素。生產(chǎn)調(diào)度的魯棒性通常分為性能魯棒性和調(diào)度解魯棒性兩類。性能魯棒性是指初始調(diào)度在不確定因素?cái)_動(dòng)下的實(shí)際調(diào)度目標(biāo)與實(shí)際最優(yōu)調(diào)度目標(biāo)的接近程度，兩者越接近，初始調(diào)度的性能魯棒性越好；調(diào)度解魯棒性是指不確定因素?cái)_動(dòng)下的實(shí)際調(diào)度方案與初始調(diào)度方案的接近程度，兩者越接近，調(diào)度解魯棒性越好[2-3]。

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

本文的研究為新產(chǎn)品初始加工參數(shù)錯(cuò)誤環(huán)境下單機(jī)調(diào)度問(wèn)題提供了提前時(shí)間最小的調(diào)度方法，在實(shí)踐中能夠減小訂單加工參數(shù)錯(cuò)誤對(duì)初始調(diào)度的影響，保證在限定的魯棒性約束下保證初始調(diào)度的穩(wěn)定性，提高調(diào)度目標(biāo)的滿意程度。

1魯棒性指標(biāo)與問(wèn)題描述

1.1　符　號(hào)

本文主要用到以下符號(hào)：

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

1.2　魯棒性測(cè)度

生產(chǎn)調(diào)度的性能魯棒性和調(diào)度解魯棒性有不同的測(cè)度方法，性能魯棒性通常用調(diào)度目標(biāo)的差異度量，而調(diào)度解魯棒性通常用訂單的變化、開工或完工時(shí)間的差異等度量。Jorge等[1]用實(shí)際調(diào)度σr與初始調(diào)度σp的期望最遲完工時(shí)間差作為初始調(diào)度σp的魯棒性測(cè)度。因?yàn)槌跏颊{(diào)度σp受不確定因素?cái)_動(dòng)，剔出訂單的后續(xù)訂單完工時(shí)間均會(huì)提前，所以有Dmax(σp) ≥0。Ronan O Donovan等[3]用實(shí)際調(diào)度與初始調(diào)度各訂單期望完工時(shí)間差的絕對(duì)值之和表示調(diào)度魯棒性，即

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

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

(1)

在訂單剔出環(huán)境下，調(diào)度σ的魯棒性可以定義為：

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

此時(shí)調(diào)度σ完成時(shí)間為

在這種情況下對(duì)于魯棒性最優(yōu)的調(diào)度有

1.3　問(wèn)題描述

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

2調(diào)度問(wèn)題1|rj,RS<α|Tmax的求解

在訂單式實(shí)際生產(chǎn)中，通常要求在限定解魯棒性最優(yōu)的調(diào)度方案，調(diào)度性能目標(biāo)是最大提前時(shí)間，則問(wèn)題表示為1|rj,RS<α|Tmax。

2.1　初始調(diào)度模型建立

調(diào)度方案結(jié)果顯示按照訂單交期順序進(jìn)行生產(chǎn)，若訂單交期一樣，則按照訂單加工數(shù)量多少進(jìn)行生產(chǎn)，數(shù)量多的優(yōu)先生產(chǎn)，此時(shí)調(diào)度方案為最優(yōu)，即“最早交貨最早加工EDD”規(guī)則。以每筆訂單交期與完成時(shí)間差值總和最小為目標(biāo)函數(shù)，初始調(diào)度方案建立以下數(shù)學(xué)規(guī)劃模型(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)為調(diào)度中的單個(gè)訂單時(shí)間約束；約束(2)為相鄰兩個(gè)訂單的時(shí)間約束；約束(3)為后續(xù)訂單加工開始時(shí)間不得早于前訂單結(jié)束時(shí)間；約束(4)為初始完工時(shí)間。

2.2　問(wèn)題分析

2.3　優(yōu)化調(diào)度模型建立

在考慮平均加工時(shí)間的情況下，建立優(yōu)化調(diào)度模型，其目標(biāo)函數(shù)為每項(xiàng)訂單完工時(shí)間與交期差值的總和，此時(shí)完工時(shí)間為初始調(diào)度方案下完工時(shí)間減去平均提前時(shí)間。優(yōu)化調(diào)度方案建立以下數(shù)學(xué)規(guī)劃模型(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)為調(diào)度σp″中的單個(gè)訂單時(shí)間約束；約束(2)為相鄰兩個(gè)訂單的時(shí)間約束；約束(3)為各訂單完工時(shí)間需要延后；約束(4)為設(shè)置的虛擬訂單完工時(shí)間，約束(5)為調(diào)度σp″的最大提前時(shí)間約束；約束(6)為優(yōu)化調(diào)度與初始調(diào)度的魯棒性測(cè)度滿足條件。

3仿真分析

表1　加工訂單參數(shù) Tab.1 Processing order data

3.1　初始調(diào)度方案

根據(jù)2.1中所述建立模型，本文將調(diào)度問(wèn)題的條件和約束抽象為簡(jiǎn)化的模型表達(dá)式，并把調(diào)度的評(píng)價(jià)指標(biāo)作為調(diào)度模型優(yōu)化的目標(biāo)，調(diào)度方案以“最早交貨最早加工EDD”為規(guī)則，通過(guò)對(duì)模型的分析和求解來(lái)對(duì)的生產(chǎn)調(diào)度提供決策方案。為了模型的處理，提出以下假設(shè)：

(1)若某一訂單開始生產(chǎn)，在沒(méi)有完成之前，不能進(jìn)行另外訂單的生產(chǎn)，即單機(jī)生產(chǎn)方式。

(2)由于時(shí)間約束，從開始至生產(chǎn)結(jié)束過(guò)程中沒(méi)有停頓，即生產(chǎn)是連續(xù)性的。

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

例如第30 d的訂單，到28.5 d完成了，提前日期為1.5 d，而不是一天或者兩天。根據(jù)建模假設(shè)，對(duì)初始調(diào)度模型進(jìn)行基本排序，初始調(diào)度方案通過(guò)Matlab實(shí)現(xiàn)，程序片段如下：

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，：)

根據(jù)程序生成的最終序列，初始調(diào)度方案結(jié)果為：5、8、9、7、1、4、3、2、6，目標(biāo)函數(shù)生成提前期的結(jié)果為：10.55。以上測(cè)試表明，建立的初始調(diào)度模型是正確可行的，生產(chǎn)過(guò)程存在著較大的生產(chǎn)提前期。

3.2　優(yōu)化調(diào)度方案

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

訂單j加工過(guò)程中的機(jī)器故障平均維修時(shí)間為：

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

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，：)

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

圖1　最優(yōu)調(diào)度 Fig.1 Optimal scheduling

3.3　仿真結(jié)果

通過(guò)最小提前期調(diào)度系統(tǒng)仿真的實(shí)際效果來(lái)看，基本上達(dá)到了優(yōu)化調(diào)度的要求，通過(guò)比較兩組計(jì)算結(jié)果可以看出，在考慮新產(chǎn)品初始加工參數(shù)錯(cuò)誤造成的訂單剔出后，對(duì)后續(xù)訂單來(lái)帶提前期影響的情況下，通過(guò)優(yōu)化調(diào)度模型，獲得新的調(diào)度方案，其目標(biāo)函數(shù)值表示的總提前時(shí)間明顯縮短，優(yōu)化幅度達(dá)61.77%，改方案和模型是切實(shí)有效的。魯棒性RS與調(diào)度性能呈現(xiàn)相反的變化趨勢(shì)，要使魯棒性更好，調(diào)度性能就會(huì)變差，表明調(diào)度魯棒性的提高要以降低調(diào)度性能為代價(jià)。因此，最小提前期調(diào)度方案可以給企業(yè)的生產(chǎn)管理帶來(lái)一定的決策依據(jù)。

4結(jié)束語(yǔ)

新單在試生產(chǎn)或正式投入生產(chǎn)的過(guò)程中經(jīng)常出現(xiàn)的不確定因素，本文針對(duì)這一情況，研究了在新單加工出現(xiàn)錯(cuò)誤需要剔出的情況下，以調(diào)度最大提前時(shí)間的單機(jī)魯棒調(diào)度優(yōu)化方法，探討了在最大提前時(shí)間約束下求解最優(yōu)魯棒性的方法。在此基礎(chǔ)上，給出了單機(jī)魯棒行最小提前調(diào)度優(yōu)化方法，并且仿真驗(yàn)證了該方法的適應(yīng)性和有效性。本文的研究局限于單機(jī)環(huán)境，F(xiàn)low Shop和Job Shop等復(fù)雜機(jī)器環(huán)境下針對(duì)機(jī)器故障的魯棒調(diào)度問(wèn)題將是進(jìn)一步研究的重點(diǎn)。

【參考文獻(xiàn)】

[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，F(xiàn)rench 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ī)魯棒調(diào)度多目標(biāo)優(yōu)化方法[J].計(jì)算機(jī)集成制造系統(tǒng)，2013，19(10)：2459-2466.

[7]何正文，劉人境，徐渝.基于隨機(jī)活動(dòng)工期的資源約束項(xiàng)目魯棒性調(diào)度優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2013，33(3)：650-659.

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

[9]張宏國(guó)，徐曉飛，戰(zhàn)德臣.不確定資源約束下項(xiàng)目魯棒性調(diào)度算法[J].計(jì)算機(jī)應(yīng)用研究，2009，26(6)：2079-2082+2089.

[10]魏巍，譚建榮，馮毅雄，等.柔性工作車間調(diào)度問(wèn)題的多目標(biāo)優(yōu)化方法研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2009，15(8)：1592-1598.

[11]田文迪，胡慕海，崔南方.不確定性環(huán)境下魯棒性項(xiàng)目調(diào)度研究綜述[J].系統(tǒng)工程學(xué)報(bào)，2014，29(1)：135-144.

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

[責(zé)任編輯：胡建偉]