高端制造業(yè)批量處理問題的優(yōu)化方案研究

問題背 研究現(xiàn)狀及必要 帶有不相容工作族的??→??|????????問 問題模 問題下 算法設(shè) 數(shù)值實(shí) 案例生 數(shù)值結(jié)果與分 總 帶有不相容工作族及有限緩沖區(qū)限制條件的??→??|????問 問題模 問題下 GSPT算 數(shù)值實(shí) 案例生 數(shù)值結(jié)果及分 總 結(jié) 參考文 問題背如半導(dǎo)體制造、火箭廠等。FlowShopJobShop排程。但在實(shí)際生產(chǎn)中，我們經(jīng)常會遇到批處理機(jī)器，批1.1中，在半導(dǎo)體生產(chǎn)線上不同的1.1研究現(xiàn)狀及必要作業(yè)研究的一個(gè)重要分支。為了問題描述的簡化，下文我們以β→δ|Z代表此問題，其中β代表批處理機(jī)而δ代表單機(jī)。Z則代表了問題的目標(biāo)。Ahmadietal.[1]研究了βδ問題并就工作周期（????????）FullBatch-dealingSPT算法。同時(shí)他還拓展了β→δ問題，為其加入了不相容Ahmadietal.工作的基礎(chǔ)上，HoogeveenandVelde[2利用了位置完成時(shí)間的概念并以β→δ|????為目標(biāo)提出了一種時(shí)間復(fù)雜度為O(nlog??)的算法并給出了其一個(gè)日下界。KimandKim[3]利用信息不變性原則為解決β→δ|∑????提出了GA為基礎(chǔ)的新的方案。Suetal.[4則考慮了第二階段有限等待時(shí)間這一限制就β→δ|????????問題提出了一個(gè)啟發(fā)式算法及混合線性整數(shù)規(guī)劃模型。SuandChen[5]則就不等同工作尺寸限制條件下的β→δ|????????提出了一種啟發(fā)式算法和一種分支定界算法。Yaoetal[6]考慮了動態(tài)工作到達(dá)及不相容工作族、有限等待時(shí)間限制條件下的β→δ|????????問題。他們都為我們解決這些問題提供了諸多GongandTang[7]Gongetal.[8]在考慮????????和總堵塞時(shí)間的目標(biāo)下對β→留在批處理機(jī)中。他們提出了幾種近似算法。Suetal.[9研究了有限緩沖區(qū)限制條件下的β→δ|????????問題并給出了一種思路以及一個(gè)分支定界程序以進(jìn)行基準(zhǔn)化分析。Fuetal.[10]就不相容工作族及有限緩沖區(qū)條件下的β→δ|??了研究，其中??從該問題的研究現(xiàn)狀，我們得出β→δ|Z例如帶有不相容工作族的β→δ|∑????????限制條件的βδ|????問題，而且這些空白在現(xiàn)實(shí)生產(chǎn)中更普遍，更接近實(shí)際情Ahmadietal.[1]所述的，β→δ|????問題是plete所研究的帶有不相容工作族的β→δ|∑????????問題和帶有不相容工作族及有限緩沖區(qū)限制條件的βδ|????問題很顯然也是plete問題。接下來我們在第三章討論帶有不相容工作族的βδ|????????問題，在第四章討論帶有不相容工作族及有限緩沖區(qū)限制條件的β→δ|∑????問題帶有不相容工作族的??→??|????????問 pat|∑????????問題的滿批次性，其每一個(gè)工件族中的工件數(shù)量都是批量生產(chǎn)機(jī)器容量的整數(shù)所有的工件尺寸所有的批次在批處理機(jī)器上擁有相同的處理優(yōu)先權(quán)在批量處理器與單機(jī)上都不被允兩個(gè)處理器間的緩沖區(qū)是無限工件可以以任意順序在單機(jī)上進(jìn)行處NN=｛1,2, F=｛1,2,nkkBB=｛1,2,Fkkpii Mwii變量xilxil=1il，否則xil=yklykl=1lk的工件，否則ykl=uijuij=1當(dāng)工件i在工件j之前在單機(jī)上進(jìn)行處理，否則uij=0； 工件i的完成時(shí)間Uzsoy11]引理3.1：存在一個(gè)β→δ，pat|????????調(diào)度問題的最有解，除了每個(gè)工味著工件總數(shù)n∑knk=αbα代表滿批次性下的批次數(shù)量。因此，基于以BDMI：min∑i∈N s.t.∑??∈Bxil= ?i∈ ∑i∈Nxil= ?l∈ ∑??∈Fykl= ?l∈B, =nk ???∈F,??∈B xil≤ ???∈F,l∈B,uij+uji= ?i,j∈N,i<j,Ci?pi≥Cj? ?i,j∈N,i≠j,Ci?pi≥t∑??∈Blxil ?i∈N,uij∈{0,1},?i,j∈N,i≠j,（10）∈{0,1},???∈F,l∈B,xil∈ ?i∈N,l∈B,約束（6）lkk的工件才可開始處理。約束（9）i所在的批次在批量處理器上完成了處（10（11）范圍。在此，我們可以設(shè)置B=｛1,2,…,α|｝以及M=αt+∑i∈NpiBDMI等式定制滿批次數(shù)據(jù)來進(jìn)行計(jì)算實(shí)驗(yàn)。對應(yīng)的計(jì)算結(jié)果將在3.4部分 引理3.2：當(dāng)??1≤?≤??n與??1≤?≤??n??n??1+?+??1??n≤??σ(1)??1+?+??σ(n)??n≤??1??1+?+其中??σ(1),…,??σ(n)為??1,…,??n即，單機(jī)的等待時(shí)間可以忽略。據(jù)此，我們在提法1中推導(dǎo)第一個(gè)下界LB1。推論3.1將權(quán)重w按降序排列，將處理時(shí)間按升序排列，則LB pat|∑????的一個(gè)下界 j=1j(?b?t+j ??證明：設(shè)（x?,y?,u?,C?）是問題的一個(gè)最優(yōu)解。對于每個(gè)工件j,記其所需完成時(shí)間為C?，令w?和p?分別為其權(quán)重和處理時(shí)間。顯然，每個(gè)C?包含三個(gè)部分： 批量處理器上的完成時(shí)間t∑l∈Bx?在緩沖區(qū)的等待時(shí)間 0以及單機(jī) 間p?。因此，為了使目標(biāo)函數(shù) w?C?最小化，我們需要以下不等式 j w?C?=

w?(t x?+△?+j

n

≥ w?(t j

≥ j(??t+j)= 個(gè)問題就變?yōu)榱酸尫艜r(shí)間全部為t的單機(jī)時(shí)間規(guī)劃問題。這類問題可以通過WSPT法則，即Smith’srule,來取得最優(yōu)解。推論3.2：將所有工件按pj/wj進(jìn)行增序排列，?j∈N,??≤? ??，則LB=?(t∑j?)為β→δ1 2 i=1pat|∑????????的一個(gè)下證明：記（xyuC?）是問題的一個(gè)最優(yōu)解，對于每個(gè)工件j,記其所需完成時(shí)間為C?，令w?和p?∑nw?C? j

n∑

w?C?≥j

w?(t+j

in≥

t+

nw?∑

≥ ?jt+ ?j ?i tLB1就會更精確。除此之GRWC-WSPT算Uzsoy[11]提出了一種用于求解一個(gè)批次處理機(jī)器上不兼容工件組的最小時(shí)間工序（GRWC）的貪心算法。批次處理器上的GRWC過程、單WSPT規(guī)則以及一些其他的有用信息組合起來并設(shè)計(jì)了的第一個(gè)啟發(fā)式算法，其記作GRWC-WSPT。下表描述了其流程：GRWC-第五步：讓單機(jī)處于待機(jī)狀態(tài)，直到所有的批次都已釋放，之后再按p/w的上界，記為UB。UB可被用于分析所提算法的情況?！埔?.3：令UB=αt∑nj=1wj+ΓWSPT，則UB為 pat|∑????????的∑

?

情況下，第i批工件中的工件的釋放時(shí)間可以被視為????+(?????)=????，該公式H0。對H0我們可以找到一個(gè)可行解，我們很容易確認(rèn)其目標(biāo)值為Obj(H0)=αt∑n wj+ΓWSPT=UB.證明完成。推論3.3：GRWC-WSPT是 pat|∑????????問題的α近似算法，其證明：考慮引理三證明中工序H0出現(xiàn)在算法的第五步，我們有Obj(GRWC-WSPT)≤UB，基于第四節(jié)LB1LB2，以及引理3給出的UB，不難驗(yàn)證LB1≥t∑n wj以及UB?LB2=αt∑n wj?∑n ?jt。因此，以下不等

Obj(GRWC?WSPT)≤1+Obj(GRWC?WSPT)? ≤1αt

UB? LB1 ?=1t

j=1wj

wj=1wj? ≤1

t = LP-WSPTLP-WPST的流程如下：第二步：在第k個(gè)工件組中，按c的增序排列工件第六步：重定義cj=cj/wj，重復(fù)步驟2-5，返回計(jì)劃表π2及相依目標(biāo)值Obj(π2)序在單機(jī)上進(jìn)行處理。返回該規(guī)劃π3極其函數(shù)值Obj(π3)。推論3.4：LP-WSPT是β→δ， 證明：考慮到引理3中H0被整合入算法的第七步，同推論3相似

Obj(LP?WSPT)≤1+Obj(LP?WSPT)?

≤1

UB? ≤的LP-relaxation問題。本節(jié)進(jìn)行了一些計(jì)算試驗(yàn)來檢驗(yàn)所算法的表現(xiàn)。所有的試驗(yàn)均在64位的Windows7系統(tǒng)上運(yùn)行硬件配置為InCore3.3GHZ的CPU,RAM4.0GB。算法C++編寫VS2010運(yùn)行BDMI的數(shù)學(xué)公式求Cplex12.5進(jìn)行（默認(rèn)的求解時(shí)間上限為3600s）對于每個(gè)組合“n-m-b”，設(shè)置n=b?n?,j=1,…,m?1,和 =n?∑m?1n 對于每個(gè)工件i，其權(quán)重由1-2之間的均勻分布給出，處理時(shí)間????和單機(jī)則由1-10的均勻分布給出。批次處理時(shí)間t被設(shè)置為n p。這樣的設(shè)計(jì)可以有效 i=1G1：n={8,12,16,20},m={2,4},b=G2：n={100,200,300,400},m={2,4,10},b=G3：n={800,1000},m={4,10},b=

≥Gap1：GRWC-WSPT與BDMI結(jié)果的平均差Gap1與Gap2的計(jì)算方法如下Obj(H)?Obj(BDMI)Gap1(2)= 顯然，Gap<0BDMI的表現(xiàn)更好，Gap1(2)>0CplexBDMI的平均最佳目標(biāo)函數(shù)值。Time欄表示求解表中所述的一樣的，Lp-relaxation更為精密，由此法可在個(gè)人電腦上在一小時(shí)內(nèi)解12個(gè)工件的問題。當(dāng)工件數(shù)目增加至20時(shí)，沒有任何案例可以在一小時(shí)內(nèi)求解，對于所有組合，Gap0的最大值是6.64%。3.1G1BDMI模型求解結(jié)3.2展示了兩種算法的結(jié)果的對比以及G1CplexBDMI結(jié)果。每個(gè)組合的結(jié)10個(gè)案例的平均。值得注意的是對于每個(gè)例子，我們都計(jì)算LB1,LB2Lp-r中的最大值，而LB欄中的值則是10個(gè)值的平均值。顯然，Gap1Gap2BDMI的解的質(zhì)量高于我們所提的3.49%。另一方面，GRWC-WSPT1.1256，而LP-WSPT則是比其稍好（除了組合16-2-4。3.2G1表格3.3則給出了兩種算法G1情形的情況結(jié)果以及相應(yīng)的差值與比值。值。對n=812的組合來說（12-2-2，Gap1與Gap2的最小0，這6.77%。兩個(gè)算法比值的最低值均小于1.1097，最大值均為1.1678，這意味著這兩表3.3算例G1的最好和對比結(jié)表3.4給出了三個(gè)算法在G2組中的對。標(biāo)記同表2相似，在此不做詳述。如表中所示，Gap0的最大值為14.09%（組合400-2-10），這意味著Cplex給出的著我們算法相較于Cplex給出的BDMI解質(zhì)量更高。就ratio方面而言，計(jì)算時(shí)間也稍長一些，但是相差不會超過362.66s.3.4G2表3.5給出了兩種算法在G2組的情況分析。標(biāo)記同表三相似，不做詳述。兩者在RATIO上的值均為1.1472.當(dāng)n>200時(shí)，兩者的最大值都小于1.0941.200-2-20的所有組合，LP-WSPT的平均比值都要較小。Gap1Gap2的表3.5算例G2的最好和對比結(jié)3.6GRWC-WSPT算法在G3組的解。角標(biāo)含義與前類似。應(yīng)當(dāng)注只有GRWC-WSPT能夠用于解決這類大規(guī)模問題。此外，我們還記算了LB1LB2中的最大值，并取其為每個(gè)算例的下界。如表6所示，每個(gè)算例的ratio均小于1.1034。尤其值得注意的是，對于800-10-50之外的所有組合，Max-R下的最大ratio均小于1.0726，這說明對于大規(guī)模問題該算法仍有著不錯(cuò)的表現(xiàn)。等同批次處理時(shí)間。其二則是考慮證明這個(gè)問題是否存在一個(gè)常數(shù)近算法。帶有不相容工作族及有限緩沖區(qū)限制條件的??→??|????問在此部分，我們首先給出帶有不相容工作族及有限緩沖區(qū)限制條件的β→∑所有工作一開始都已做好了進(jìn)入批處理器處理的準(zhǔn)備每個(gè)族的工作數(shù)目都是批處理機(jī)容量的整數(shù)所有工作的尺寸相同每批工作的處理時(shí)間只取決于其內(nèi)工作所屬的族工作在批處理機(jī)上的處理時(shí)間比其在單機(jī)上的處理時(shí)間長批處理機(jī)及單機(jī)都不具有優(yōu)先權(quán)緩沖區(qū)尺寸是批處理機(jī)容積的整數(shù)工作能夠在單機(jī)上以任意順序被處理N:N={1,2FF={1,2????：kBB={1,2????：k????：k????：一個(gè)大的正不失一般性的說，我們假設(shè)??1≤??2≤??3≤?≤????；Uzsoy[11]fullbatchproperty，其各工作的完工時(shí)間呈單調(diào)遞增。引理4.1：存在βδ|????的最優(yōu)解使得除了最后一批的每一批工作都是滿帶有不相容工作族及有限緩沖區(qū)限制條件的β→δ|????min∑??∈????s.t.∑??∈????????=1?i∈N（2∑??∈????????=b，?l∈B，∑??∈????????=1，?l∈ ??=????，?k∈F，??∈????????????≤??????，?i∈????，l∈B，?????????≥0，?l∈ ????+1?????+1≥????，?l∈B，??≠??,∑??∈??,??≠????????+1≤??(????)+??1(1???????)，???∈??,??≥?+1，??∈∑??∈??,??≠????????+1≥??(????)+??+[1???(????)???]??????，???∈??,??≥?+1，??∈??，（10）????≥?????p?????2(1???????)，???∈??,??≥?+1，??∈??，????≥??????????，?k∈F，l∈ ??????+??????=1，???，??∈??,??< ?????????≥???????2??????，???，??∈??,??< ?????????≥???????3(1???????)，???∈??,??∈ ??????∈{0,1}，???，??∈??,??≠ ??????∈{0,1}，???∈??,??∈ ??????∈{0,1}，???∈??,??∈ ??????∈{0,1}，???∈??,??∈ k族的工作被分配為????個(gè)批次進(jìn)行處理；限制方程（6）lk族的工作時(shí)，kl以設(shè)??1=n-b(l-h)、??=0.01；限制方程（11）保證了在某一批次工作釋放時(shí)緩沖區(qū)至少存在一個(gè)單位的閑置空間，我們可以設(shè)??2=∑??∈??????????+∑??∈??????+???????????∈??????；限制條件（12）定義了批處理所需時(shí)間；限被釋放到緩沖區(qū)的工作，我們可以設(shè)??3=∑??∈??????????+∑??∈??????；限制條件（16）（17（18（19）在這一部分推導(dǎo)出帶有不相容工作族及有限緩沖區(qū)限制條件的β→δ|∑????問題的兩個(gè)下界，這將有利于我們檢驗(yàn)算法所得結(jié)果的質(zhì)量。推論4.1：將各批次工作按批處理時(shí)間????升序排列，使得??1??2??3

(1+????1=∑[????(??+1?∑????) ]??????+∑ 為帶有不相容工作族及有限緩沖區(qū)限制條件的β→δ|????證明：記???j的最優(yōu)化完工時(shí)間，????（忽略堵塞時(shí)間）j處理機(jī)上的 工時(shí)間，???和???分別為工作j在批處理機(jī)上的完工時(shí)間和單機(jī) 間???、批處理機(jī)上的堵塞時(shí)間和緩沖區(qū)的等待時(shí)間??以及單機(jī)上的處理時(shí)間???。 ??=1因此令???= ???為最優(yōu)化的總完工時(shí)間，我們??=1???= ???= (???+??+???)≥ (???+???)= (???????=1 ??=1 ??=1 1)?????+ ??=1 ≥ (?????+

+

(1+=∑[????(??+1?∑????) ]??????+∑

下面我們從另一個(gè)角度來推導(dǎo)另一個(gè)下界????2?？紤]所有工作自批處理機(jī)SPT規(guī)則得到最優(yōu)解。由此我們有下面題。推論4.2：將各批次工作按獨(dú)立處理時(shí)間????升序排列，使得2≤?≤????2= [??1+(?????+1)??為帶有不相容工作族及有限緩沖區(qū)限制條件的β→δ|???? ∑ ???≥∑

+(?????+1)???]≥

+(?????+1)???? ????1和????2計(jì)算的時(shí)間復(fù)雜度均接近??(??log??)，均能很快地通過計(jì)算得到。因此我們可以利用這兩個(gè)下界來評測我們所算法在處理問題時(shí)的表現(xiàn)。GSPT4.1fullbatchpolicySPT規(guī)則。得到初步編對各工作族????按照????升序排列在各族內(nèi)部對工作按照????升序排列，??∈貪婪地（即每一批在可能的情況下都組滿構(gòu)建工作批次，順序按照計(jì)算各批次工作在單機(jī)上所需的總處理時(shí)間令????=????，批處理機(jī)按照????令????????????5）6）得到另一種可能方案??2，計(jì)算對應(yīng)目標(biāo)值Obj(??2)；記此可能方案為??3，計(jì)算對應(yīng)目標(biāo)值Obj(??3)；確定參數(shù)???=????????????????????(????)，i=1，2，3；給出方案???該算法的時(shí)間復(fù)雜度為??(??log??)。接下來我們對此算法進(jìn)行分析δ|∑????問題的b-近算法，其中b代表批處理機(jī)的容積。證明：令Γ= [??(??+1?∑???1??)?(1+????)????]????。令每一批次工作 成時(shí)間為????????????GSPT (1+ ????= ????= [????(??+1? ????) ]????+

=Γ2+ 然后以Γ1乘以b，我們 (??+??Γ1= [??????(????+??? ??????) ]

= [????(??+???

(??+????) ] ????(??? ????(?????Γ1?Γ2=

[????(???1)

]????=2

]????≥由第四部分所給出的下界????1的值我們可以得到下列不等

Γ2+

≤ = ≤

≤Γ1+Γ1+

Γ1Γ1+

由此我們證明了我們的結(jié)論：GSPT為b-近算法 64win73.3GHzCoreCPU及4.0GB的運(yùn)行內(nèi)存。算法以C++語言進(jìn)行編程并在VisualStudio2010中運(yùn)行。第的數(shù)量；b代表批處理機(jī)的容積；h代表緩沖區(qū)的容積。針對每個(gè)組合我們跑了10個(gè)樣例，樣例的生成參考了[1]和[12]。

=??[??]，j=1,2,…,m-????=???∑???1????∈??(1,10)，????為整數(shù)；U(a,b)為從[a,b]批處理機(jī)處理時(shí)間為??(?? ???10,?? ??+10)且為整數(shù)，這使得對 ??=1 ??=1近。同時(shí)如果有樣例不符合假設(shè)5，那么這個(gè)樣例將會被刪除。??3n={400,600,800,1000},m={5,10},b={10,20},h={2,3}

>12116個(gè)時(shí)，得結(jié)果和最優(yōu)值的對比如表4.1所示。MIP代表第三部分中的方程組。差距??????(????????)?

×4.1GSPT算 目標(biāo)值時(shí) 目標(biāo) 時(shí)Obj：由GSPT給出的目標(biāo)值；；Avg-R：GSPTLB間的平均比值；Max-R：GSPTLB對于每個(gè)組合，LB、Obj和Time均為10個(gè)樣例給出數(shù)據(jù)的平均值，同時(shí)我們對每一個(gè)組合的每一個(gè)樣例計(jì)GSPTLB間的比值，Avg-R為每個(gè)組10個(gè)0.05Avg-R出現(xiàn)在(100,4,5,1)1.197；最大的Max-R出現(xiàn)在(200,4,5,1)的組合中，最大比值為1.295；這些結(jié)果說明GSPT在4.2GSPT4.3展示了??3GSPT算法處理的結(jié)果。每個(gè)問題的處理時(shí)間都少于0.6秒，對于大部分樣例其Avg-R值均小于11，最大的Avg-R出現(xiàn)在(1000,5,10,2)的組合中，最大比值為1.127；Max-R的值同樣十分小，最大的Max-R出現(xiàn)在4.3GSPT們還給出了一種b-近算法并給出了其兩個(gè)下界以對其運(yùn)行結(jié)果進(jìn)行。通過數(shù)值運(yùn)算的結(jié)果我們相信此算法在大規(guī)模工作的處理上具有顯著的優(yōu)越性與結(jié)些空白，本文具體討論了帶有不相容工作族的β→δ|????????作族及有限緩沖區(qū)限制條件的βδ|????參考文J.H.Ahmadi,R.H.Ahmadi,S.Dasu,andC.S.Tang,“Batchingandschedulingjobsonbatchanddiscreteprocessors,”O(jiān)perationsresearch,vol.40,no.4,pp.750–763,1992.H.HoogeveenandS.vandeVelde,“Schedulingbypositionalcompletiontimes:ysisofatwo-stageflowshopproblemwithabatchingmachine,”MathematicalProgramming,vol.82,no.1-2,pp.273–289,1998.B.KimandS.Kim,“Applicationofgeneticalgorithmsforschedulingbatch-discreteproductionsystem,”ProductionPlanning&Control,vol.13,no.2,pp.155–165,2002.L.-H.Su,“Ahybridtwo-stageflowshopwithlimitedwaitingtimeconstraints,”Computers&IndustrialEngineering,vol.44,no.3,pp.409–424,2003.F.S.Yao,M.Zhao,andH.Zhang,“Two-stagehybridflowshopschedulingwithdynamicjobarrivals,”Computers&OperationsResearch,vol.39,no.7,pp.1701–1712,2012.H.GongandL.