應(yīng)用離散事件系統(tǒng)控制理論求解生產(chǎn)調(diào)度的新方法

伍乃騏, 喬 巖

(澳門科技大學(xué)系統(tǒng)工程研究所,澳門)

1 引言

調(diào)度問題是一個經(jīng)典的研究問題,也是各個領(lǐng)域廣泛面對的問題.它的一個重要分枝是生產(chǎn)調(diào)度.一般認(rèn)為,生產(chǎn)調(diào)度的理論和方法已基本成熟,有大量的研究,早在1974年Baker就出版了相關(guān)的專著[1].由于一般的調(diào)度問題屬于NP-hard問題,為了有效求解,對于大規(guī)模的生產(chǎn)調(diào)度問題,人們一般選擇啟發(fā)式算法、搜索算法和元啟發(fā)式算法求解[2-7].隨著生產(chǎn)過程越來越復(fù)雜,調(diào)度問題的規(guī)模越來越大,以及客戶定制導(dǎo)致產(chǎn)品的多樣化和小批量(甚至單件定制),實時動態(tài)調(diào)度成為迫切需求.在動態(tài)調(diào)度的要求下,元啟發(fā)式算法也難滿足實時性需求,而啟發(fā)式算法難于保證解的性能.因此,目前生產(chǎn)調(diào)度問題仍是熱門的研究領(lǐng)域,人們希望根據(jù)不同問題的特點,尋求有效的方法.人工智能也引入調(diào)度領(lǐng)域的研究[8-9].此外,有些系統(tǒng)存在潛在的沖突或死鎖,為了求得無死鎖、無沖突的調(diào)度,研究人員結(jié)合Petri網(wǎng)模型和啟發(fā)式算法求解[10-11].這些算法也涉及到計算復(fù)雜性問題.

有一大類的生產(chǎn)過程具有嚴(yán)格的工藝約束.例如,自動化的生物化學(xué)物質(zhì)快速篩選系統(tǒng)(high throughput screening systems,HTSS)中某些工序必須在一個嚴(yán)格的時間窗口內(nèi)完成[12];印刷電路和半導(dǎo)體芯片制造中,很多工序要求加工完成后工件必須在規(guī)定的時間內(nèi)從加工裝置中移出[13];在某些石油化工過程中,物料罐相當(dāng)于離散制造中的一臺加工設(shè)備,經(jīng)常在物料注入罐中后需要等待規(guī)定的時間才能使用[14].由于這些約束的存在,啟發(fā)式算法和元啟發(fā)式算法難于保證約束得到滿足,人們不得不尋求數(shù)學(xué)規(guī)劃的求解方法[15-19],這就面臨計算復(fù)雜性問題.當(dāng)問題規(guī)模巨大時,幾乎無法實際應(yīng)用.同樣,當(dāng)不確定性存在,需要實現(xiàn)動態(tài)調(diào)度時,基于數(shù)學(xué)規(guī)劃的方法也難于應(yīng)用.這是調(diào)度問題研究中面臨的嚴(yán)峻挑戰(zhàn)之一.

注意到,調(diào)度問題面對的系統(tǒng)包含了離散事件過程.在離散事件過程控制中,過程的狀態(tài)可分為合法狀態(tài)和非法狀態(tài).離散事件過程控制的重要問題之一是設(shè)計一種控制策略使得合法狀態(tài)保留,而所有的非法狀態(tài)不會出現(xiàn).對以上調(diào)度問題,可以應(yīng)用離散事件系統(tǒng)控制理論將所有違反約束的狀態(tài)定義為非法狀態(tài),而其他狀態(tài)定義為合法狀態(tài).然后,利用該理論研究解的存在性,并推導(dǎo)出解的存在性條件.基于所獲得的條件,可以在可行空間內(nèi)求解,從而獲得有效的求解方法.

本文旨在介紹這一生產(chǎn)調(diào)度新方法,并以半導(dǎo)體芯片制造中的一類典型系統(tǒng)作為例子,較為詳細(xì)地說明這種方法的求解過程.它把本來非常復(fù)雜的離散優(yōu)化問題轉(zhuǎn)換為簡單的連續(xù)優(yōu)化問題.結(jié)果,不僅可以對給定的問題有效求解,還可以對系統(tǒng)的干擾實現(xiàn)有效的優(yōu)化響應(yīng).

2 問題描述

半導(dǎo)體芯片是由很多層電路構(gòu)成的集成電路,每一層電路的形成都要經(jīng)歷沉積、涂膠、曝光、顯影、光刻、蝕刻、清洗等工藝過程,其中絕大部分工藝過程是由稱之為組合設(shè)備(cluster tools)的裝備完成.因此,它的調(diào)度和控制問題是晶圓制造的關(guān)鍵之一.

如圖1所示,一臺組合設(shè)備主要由若干加工模塊(process module,PM),兩個稱之為loadlocks(LLs)的裝卸裝置,以及一臺機械手.在圖中兩個LL分別用AL和CL表示.機械手可以是單臂和雙臂的,相應(yīng)的組合設(shè)備稱之為單臂和雙臂組合設(shè)備.在晶圓加工過程中,一般以25枚晶圓為一批,它們裝在一個箱子里.裝有25枚晶圓的箱子通過車間的物料傳送裝置載入其中的一個LL,抽真空后即可進行加工.晶圓的加工路徑是根據(jù)工藝要求預(yù)先設(shè)定的.在加工中,機械手從一個LL中取出一枚晶圓,按照預(yù)先設(shè)定的順序送到各PM進行加工,加工完畢的晶圓送回原來的LL.當(dāng)一個LL中的晶圓在加工時,另一個LL可以進行晶圓箱的裝卸操作,因此整個系統(tǒng)可以連續(xù)不斷地運行.

圖1 組合設(shè)備示意圖Fig.1 The illustration of cluster tools

一些工藝過程需要反復(fù)進入某些PM進行加工,這種加工工藝稱之為具有重入的加工工藝.原子沉積是一種重要的電路層生成工藝,屬于典型的重入工藝[19].本文以一種雙臂組合設(shè)備重入工藝調(diào)度問題討論所提出的算法,其加工流程可以表示為(PM1,(PM2,PM3)2).它的含義是,一枚晶圓首先由PM1加工第1道工序,然后依次由PM2和PM3完成第2和第3道工序,此后晶圓需要再進入PM2和PM3進行第4和第5道工序的加工,最后回到相應(yīng)的LL.

晶圓在PM的加工是一個物理化學(xué)過程,工序加工完成后,如果晶圓在PM駐留時間過長,PM中的環(huán)境會損害加工好的晶圓.這就要求加工完的晶圓須在規(guī)定的時間內(nèi)取出.令ai表示晶圓在PMi中所需要的加工時間,δi表示加工完成后可在其中的停留時間,τi表示晶圓在PMi中的駐留時間(包括加工時間和停留時間).那么,這一工藝約束可以表示為

正是約束(1)給系統(tǒng)的調(diào)度帶來嚴(yán)峻的挑戰(zhàn),這一約束稱之為駐留時間約束.

為了保證加工質(zhì)量的穩(wěn)定性和一致性,希望求得一個單晶圓周期性調(diào)度.如果每完成一枚晶圓后系統(tǒng)完全回到原來的狀態(tài),這樣的調(diào)度稱之為單晶圓調(diào)度.

本文以雙臂組合設(shè)備在加工流程(PM1,(PM2,PM3)2)下的調(diào)度問題進行討論.雙臂組合設(shè)備在交換策略下運行.機械手在PMi的交換策略可以描述如下:在一只手臂握著從PMi?1卸下的已加工晶圓而另一只手空閑的狀態(tài)下,機械手移動到PMi,取出其中的已加工晶圓,然后將從PMi?1中取出的晶圓載入PMi中.這就完成了一次在PMi的交換操作.

在沒有重入和忽略駐留時間約束,以及盡早執(zhí)行策略(earliest starting strategy,ESS)的條件下,已被證明交換策略是生產(chǎn)率最大化意義上的最優(yōu)運行方式[20].在有重入和忽略駐留時間約束的條件下,人們曾經(jīng)認(rèn)為,應(yīng)用交換策略會形成一個最優(yōu)的單晶圓周期調(diào)度[21].實際上,文獻(xiàn)[22]證明這樣的系統(tǒng)不可能形成一個單晶圓調(diào)度,而是一個3-晶圓調(diào)度,即每完成3枚晶圓才重復(fù)原來的過程.同時還證明,在某些參數(shù)下系統(tǒng)永遠(yuǎn)不會進入穩(wěn)態(tài),而是一直處于一種動態(tài)過程中.接下來,本文討論如何應(yīng)用基于控制理論的方法解決所面臨的這一系列問題.

3 系統(tǒng)建模

離散事件系統(tǒng)控制建立在一個系統(tǒng)模型之上.作為一種有效的離散事件過程建模工具,研究人員用面向進程的Petri網(wǎng)(process-oriented Petri nets,POPN)對組合設(shè)備建模,從而推導(dǎo)出整數(shù)規(guī)劃模型對系統(tǒng)的調(diào)度問題求解[15-19].與其他研究人員的建模方法不同,本文用面向資源的Petri網(wǎng)(resource-oriented Petri nets,ROPN)建模.它是一種有限容量的Petri網(wǎng),表示為:PN=(P,T,I,O,M,K),其中:P={p1,p2,··· ,pm}是有限庫所集合;T={t1,t2,··· ,tn}是有限變遷集合,且有P ∪T ?=?和P ∩T=?;I:P×T →N={0,1,2,···}是輸入函數(shù);O:P×T →N為輸出函數(shù);M:P →N為系統(tǒng)標(biāo)識,描述系統(tǒng)中令牌在庫所中的分布狀態(tài),M0代表初始標(biāo)識;K:P →{1,2,3,···}是容量函數(shù),K(p)表示庫所p可以容納的最大令牌數(shù).

用?t={p:p ∈P和I(p,t)>0}表示變遷t的前集,即t的輸入庫所集;它的后集則表示為t?={p:p∈P和O(p,t)>0}.類似地,p的前集表示為?p={t∈T:O(p,t)>0}以及其后集表示為p?={t ∈T:I(p,t)>0}.然后,可以定義有限容量Petri網(wǎng)的變遷使能和引發(fā)規(guī)則如下.

定義1 有限容量PN中一個變遷t ∈T稱之為被使能,如果?p ∈P有

一個被使能的變遷可以引發(fā),在標(biāo)識M下引發(fā)變遷t導(dǎo)致一個新的系統(tǒng)標(biāo)識

定義1表示,只有在t的前集所有庫所有足夠的令牌,而后集的所有庫所有足夠的空間,t才可以引發(fā).因此,條件(2)表明進程使能,而條件(3)表明資源使能.

基于上面的知識,可以討論系統(tǒng)的建模,系統(tǒng)的模型如圖2所示.系統(tǒng)的調(diào)度本質(zhì)上是資源分配,用ROPN可以很好描述資源分配.在所討論的系統(tǒng)中,主要的資源是3個PM,2個LL,以及一臺雙臂機械手.所要完成的加工流程是(PM1,(PM2,PM3)2).由此可知,系統(tǒng)有3個加工步驟,且PMi服務(wù)于步驟i.將2個LL視為裝卸站,用庫所pL表示.由于任何時候2個LL中均有晶圓需要加工,因此有K(pL)=∞.用庫所r表示機械手,且K(r)=2代表它有2只手臂.

圖2 系統(tǒng)的Petri網(wǎng)模型Fig.2 The Petri net model for the system

令N3={1,2,3},用模塊化方式對步驟i ∈N3建模.其中用pi表示PMi,且有K(pi)=1.用庫所qi1和qi3分別表示機械手對PMi的交換操作前后的等待,且有K(qi1)=K(qi3)=1.用q22表示機械手在交換操作過程中的等待,此時每一只手臂均握著一枚晶圓,所以K(qi2)=2.用ti0表示交換操作中從PMi下載已加工晶圓,它的引發(fā)需要庫所pi,qi1和r中有令牌,因此,如圖所示?ti0={pi,qi1,r};同時,引發(fā)后兩只手臂各握著一枚晶圓,并執(zhí)行交換操作中的等待,因此t?i0={qi2}.用ti1表示交換操作中將從PMi?1卸下的已加工晶圓載入PMi,它的引發(fā)需要庫所qi2中有令牌,因此,?ti1={qi2};同時,釋放一只手臂,然后機械手在qi3中等待,因此t?i1={pi,qi3,r}.至此,完成了步驟i ∈N3的模塊化建模.

在模塊化建?；A(chǔ)上,變遷t12連接庫所q13和q21,t23連接庫所q23和q31,t32連接庫所q33和q21,tL1連接庫所pL和q11,以及t3L連接庫所q33和pL.注意到,q33中的令牌可使能t32也可使能t3L,這是一個沖突問題,需要予以解決.為此,引入顏色,使得模型成為著色Petri網(wǎng).

定義2 在以上PN模型中,定義變遷ti具有唯一顏色C(ti)=ci.

基于定義2,定義q33中令牌的顏色以解決以上沖突問題.令Wd為一個令牌,代表第d枚從LL送到系統(tǒng)中加工的晶圓.那么,q33中令牌的色定義如下.

定義3 如果q33中的一個令牌Wd下一步要到步驟j ∈{2,L}加工,那么定義該令牌的顏色為C(q33,Wd)=c3j.

令Wd(q)為q33中的一個令牌,它代表停留在庫所q33并完成了第q道工序的第d枚送到系統(tǒng)加工的晶圓.那么,基于圖2 的模型,如果1 ≤q<5,則有C(q33,Wd(q))=C(t32)=c32;以及C(q33,Wd(5))=C(t3L)=c3L.當(dāng)Wd的顏色為cij,此時Wd使能tij.結(jié)果,如果1 ≤q<5,q33中令牌Wd(q)使能t32,而Wd(5)使能t3L.因此,系統(tǒng)的生產(chǎn)流程得到精確描述.

通過上面的建模過程確定了模型結(jié)構(gòu),但還需要描述系統(tǒng)的狀態(tài)(即標(biāo)識),變遷使能和引發(fā)規(guī)則,以及時間特性.首先,需要確定初始標(biāo)識M0.理論上,初始標(biāo)識應(yīng)描述系統(tǒng)啟動時的狀態(tài),即空閑狀態(tài),此時所有PM均空閑.但是,考慮到本文的目標(biāo)是求一個最優(yōu)的穩(wěn)態(tài)周期調(diào)度.在穩(wěn)態(tài)下,所有的PM均處于加工狀態(tài).為了解決這一問題,可以認(rèn)為,初始時系統(tǒng)正在處理一種虛擬晶圓W0,結(jié)果可以設(shè)置初始標(biāo)識M0為M0(pi)=K(pi)和M0(qij)=0,i ∈N3,j ∈N3.當(dāng)系統(tǒng)模型按照規(guī)則演化時,虛擬晶圓會一枚一枚移出,而實際的晶圓會一枚一枚載入,當(dāng)所有虛擬晶圓移出后,系統(tǒng)進入真正的穩(wěn)態(tài).

在這一初始標(biāo)識下,為了保證機械手交換操作的正確執(zhí)行,設(shè)定ti0,i ∈N3的使能必須滿足下列條件:

以上得到的模型存在著潛在死鎖.觀測圖2所示的PN模型,假設(shè)系統(tǒng)達(dá)到標(biāo)識M使得M(q13)=M(r)=1.在此標(biāo)識下,按照變遷使能和引發(fā)規(guī)則,tL1已使能,可以引發(fā).它的引發(fā)將一個令牌移入q11,同時從r取走一個令牌.此時,容易驗證系統(tǒng)處于死的狀態(tài),因為沒有變遷可以引發(fā),也就是說它是一個死鎖標(biāo)識.可以通過施加一個控制規(guī)則避免這一事件的發(fā)生.這由加入一個控制庫所cp實現(xiàn),使得cp是tL1的輸入庫所,即?tL1?{cp}.然后令u為庫所cp的一個函數(shù)使得u(cp)∈{1,0}.如果u(cp)=1,那么cp的輸出變遷控制使能,否則其輸出變遷在控制上禁止引發(fā).為此,下面的引理成立.

引理1 如果下列條件滿足,以上獲得的PN無死鎖

觀測圖2所示的模型可知,模型中所有庫所與變遷代表的事件均需花費時間來完成,因此它們均需要賦予時間.用μ表示引發(fā)t12,t23和t32所需的時間,即機械手在兩個PM之間移動或PM與LL之間移動所需時間;用α和β表示引發(fā)ti0和ti1分別需要的時間,即機械手從PM卸載晶圓和裝載晶圓至PM分別所需時間.因此,引發(fā)tL1和t3L所需時間分別為α+μ和β+μ.如果在庫所pi,i ∈N3的交換操作中沒有等待,引發(fā)ti0和ti1的時間構(gòu)成了交換操作的時間,用λ表示.機械手在qij中的等待時間是本方法求解調(diào)度的決策變量,令ωi1,ωi2和ωi3分別表示機械手在qi1,qi2和qi3的等待時間(即交換操作前、交換操作中和交換操作后的等待時間).如果交換操作中等待時間不為零,交換操作所需的時間為λ+ωi2.考慮到qi3后接著是ti(i+1),然后是q(i+1)1,因此機械手在qi3和q(i+1)1中的等待可以合并.為此,總令ωi3=0.表1總結(jié)了模型中各庫所和變遷的含義,以及所需要的時間.

表1 模型中庫所和變遷的含義和分別所需時間Table 1 The meaning of places and transitions in the model and the time associated with them

至此,已完成了系統(tǒng)的建模.盡管,通過建模保證系統(tǒng)是無死鎖的,但不能保證系統(tǒng)不會出現(xiàn)非法狀態(tài).考慮約束(1),它意味著對每一個庫所pi都與此關(guān)聯(lián),一旦違反該約束,系統(tǒng)進入一個非法狀態(tài).而約束(1)滿足與否,取決于ti0和ti1開始引發(fā)的時刻.注意到,ti0和ti1引發(fā)與否是一個離散事件,傳統(tǒng)的方法通過數(shù)學(xué)規(guī)劃建模和求解[15-19],無法逾越組合爆炸的問題.基于所建立的模型給出可行調(diào)度的定義如下.

定義4 基于為具有重入和晶圓駐留時間約束雙臂組合設(shè)備所建立的PN模型,一個周期調(diào)度稱之為可行的,如果在該調(diào)度下任何可達(dá)標(biāo)識都是合法的,即在任何標(biāo)識M下如果ti0被使能,有τi ?ai≤δi,i ∈N3,成立.

基于所建立的模型和分析,本文應(yīng)用離散事件控制理論,將一個調(diào)度視為一個控制策略,研究系統(tǒng)的可調(diào)度性,從而獲得有效的調(diào)度方法.

4 可行調(diào)度存在性分析和調(diào)度算法

這里所討論的調(diào)度問題需要滿足嚴(yán)格的工藝約束,因此在給定的參數(shù)下存不存在可行解是一個首要問題.正如文獻(xiàn)[22]中所指出,如果按照標(biāo)準(zhǔn)的交換策略,問題不存在單晶圓調(diào)度,甚至不能達(dá)到穩(wěn)態(tài).因此,首要問題是單晶圓穩(wěn)態(tài)解的存在性.

4.1 單晶圓穩(wěn)態(tài)解的存在性

令M={Γ1,Γ2,Γ3,Γ4}表示圖2所示PN的標(biāo)識,其中Γi={Wd(q)},i ∈N3,表示pi中的令牌.令牌Wd(q)表示第d枚送進系統(tǒng)中的第q道工序正在加工中,而Γ4={Wd(q)}表示機械手握著第d枚送進系統(tǒng)的晶圓,接下來要加工第q道工序.例如,如果第1、第2、第3枚晶圓正分別在PM3,PM2,PM1中加工,而機械手握著將要加工第1道工序的第4枚晶圓,此時的標(biāo)識為M={W3(1),W2(2),W1(3),W4(1)}.因為第1道工序必須由PM1加工,因此機械手位于PM1并準(zhǔn)備執(zhí)行交換操作.實際上,如果按照標(biāo)準(zhǔn)的交換策略,這就是系統(tǒng)剛進入穩(wěn)態(tài)時的標(biāo)識,可認(rèn)為是初始狀態(tài).

已證明,通過控制系統(tǒng)的初始標(biāo)識可以求得單晶圓穩(wěn)態(tài)調(diào)度[23].例如,如果初始標(biāo)識為M1={W4(1),W2(4),W3(3),W5(1)},那么圖2所示的PN的演化軌跡為

注意到M1和M6是等同的,因此完成了一個周期,并且加工完一枚晶圓.這一過程可以反復(fù)進行,因此是一個單晶圓穩(wěn)態(tài)過程.

接下來分析一個周期的特點.在上面的演化過程中,從M1到M2需要執(zhí)行變遷引發(fā)序列(機械手操作)σ1=〈在p1交換→引發(fā)t12〉;從M2到M3需執(zhí)行σ2=〈在p2交換→引發(fā)t23〉;從M3到M4需執(zhí)行σ3=〈在p3交換→引發(fā)t32〉;從M4到M5需執(zhí)行σ4=〈在p2交換→引發(fā)t23〉;從M5到M6需執(zhí)行σ5=〈在p3交換→引發(fā)t3L →引發(fā)tL1〉.序列σ3和σ4一起形成了重入過程的循環(huán),稱之為局部循環(huán);而序列σ1,σ2,σ5一起形成了對全部3個步驟的循環(huán),稱之為全局循環(huán).也就是說,從M1到M6包含了一個局部循環(huán)和一個全局循環(huán).這意味著反復(fù)地從局部循環(huán)到全局循環(huán),再從全局循環(huán)到局部循環(huán)的切換,每經(jīng)歷一個局部循環(huán)和一個全局循環(huán)之后,一個周期完成.

4.2 時間特性分析

從上面的周期性分析可知,系統(tǒng)的演化由機械手的操作決定,因此機械手的等待起著關(guān)鍵作用.實際上,后面將看到,一個調(diào)度完全由調(diào)節(jié)機械手的等待時間決定.因此需要合適地描述機械手等待時間.

4.3 可行解存在條件和調(diào)度算法

基于以上的分析,現(xiàn)在可以討論可行解的存在性和調(diào)度算法.從式(9)以及式(11)-(14),可以得出如下結(jié)果:

令π1,π2i和π3i,i ∈{1,2}分別表示PM1,PM2和PM3完成一枚晶圓所需的時間.然后,基于式(9)以及式(11)-(14),可以得到下列這些表達(dá)式:

注意到,φ1和η1是已知常數(shù).因此,按照上面的表達(dá)式,要決定π1,π21,π22,π31和π32就是要調(diào)節(jié)φ2,η2,φ3和η3,也就是要調(diào)節(jié)機械手在庫所qij的等待時間.從圖2所示的PN模型及其演化規(guī)則可知,當(dāng)機械手的等待時間確定之后,所有機械手的操作任務(wù)均已確定.這就意味著,系統(tǒng)的調(diào)度可以通過調(diào)節(jié)機械手的等待時間,也只需通過確定機械手的等待時間實現(xiàn).問題的關(guān)鍵在于如何調(diào)節(jié)機械手等待時間使得對所有的PM約束(1)滿足,同時系統(tǒng)的生產(chǎn)率最高.

從前面的表達(dá)式還可知,通過調(diào)節(jié)機械手的等待時間可以在某種程度上改變晶圓在PM的駐留時間而保證晶圓可以加工完畢.下面討論通過調(diào)節(jié)機械手等待時間使得系統(tǒng)總保持在合法狀態(tài)空間內(nèi)的條件及相應(yīng)的調(diào)度算法.以下的結(jié)果來自文獻(xiàn)[24],由于篇幅所限,這里只給出結(jié)論不提供證明,有興趣的讀者可以參考文獻(xiàn)[24].

定理1 如果通過調(diào)節(jié)機械手的等待時間求得ψ使 得:1)π1=π21+π22=π31+π32=ψ;2)a1≤τ1≤a1+δ1,a2≤τ2i≤a2+δ2和a3≤τ3i≤a3+δ3,i ∈{1,2}.那么,對這里討論的組合設(shè)備調(diào)度問題可以求得一個單晶圓穩(wěn)態(tài)調(diào)度使得系統(tǒng)不會出現(xiàn)非法狀態(tài).

在定理1的條件下,調(diào)節(jié)機械手等待時間使得每一個PM完成一枚晶圓的時間相等,因此,需要將ψ2表達(dá)的等待時間合理地進行分配.要使非法狀態(tài)不會出現(xiàn),π1,π2i和π3i,i ∈{1,2},應(yīng)該在一個允許的區(qū)間內(nèi),這一區(qū)間的下界ΠiL和上界ΠiU可表達(dá)為

注意到每一枚晶圓都要訪問PM2和PM3兩次,令Πmax=max{Π1L,2Π2L,2Π3L},基于定理1,算法1可以求得相應(yīng)的可行調(diào)度.

調(diào)度算法1 如果[Π1L,Π1U]∩[2Π2L,2Π2U]∩[2Π3L,2Π3U]?=?以及η1≤Πmax/2成立,那么一個可行調(diào)度可以通過以下步驟決定機械手的等待時間獲得

1)ω12=ωg22=ωl22=ωg32=ωl32=0;

可以證明,由算法1獲得的解,有π21=π22=π31=π32,以及π1=π21+π22=π31+π32=Πmax=ψ,也就是說定理1的條件1)滿足.此時,系統(tǒng)的節(jié)拍是Πmax.下面的定理保證由算法1獲得的解滿足定理1中的條件2).

定理2 假設(shè)1)[Π1L,Π1U]∩[2Π2L,2Π2U]∩

[2Π3L,2Π3U]?=?;2)η1≤Πmax/2;3)機械手等待時間由算法1確定.那么,所獲得的調(diào)度對所有的PM均滿足約束(1).

如果某些條件滿足,下面給出的調(diào)度算法2也可求得可行的調(diào)度,從而保證非法狀態(tài)不會出現(xiàn).

定理3 假設(shè)1)Πmax/2<η1≤ΠiU,i∈{2,3};2)η1≤Π1U/2;3)機械手等待時間由算法2確定.那么,所獲得的調(diào)度對所有的PM均滿足約束(1).

定理3要求η1≤ΠiU,i ∈{2,3}以及η1≤Π1U/2.這就提出一個問題,如果η1>ΠiU,i ∈{2,3}或者η1>Π1U/2,是否可行解存在.下面的定理證明,如果η1>ΠiU,i ∈{2,3},系統(tǒng)不存在可行調(diào)度.

定理4 假設(shè)?i,i ∈{2,3}使得ΠiU<η1,那么系統(tǒng)沒有可行的單晶圓穩(wěn)態(tài)調(diào)度.

但是,在某些條件下,當(dāng)Π1U/2<η1成立時,系統(tǒng)仍可以求得單晶圓穩(wěn)態(tài)調(diào)度.下面的定理給出了其條件.

定理5 假設(shè)1)Πmax/2<η1≤ΠiU,i ∈{2,3};2)Π1U/2<η1;3)η1+max{Π2L,Π3L,φ1}≤Π1U;4)機械手等待時間由算法2確定.那么,所獲得的調(diào)度對所有的PM均滿足約束(1).

以上的討論要求[Π1L,Π1U]∩[2Π2L,2Π2U]∩[2Π3L,2Π3U]?=?,但是[Π1L,Π1U]∩[2Π2L,2Π2U]∩[2Π3L,2Π3U]=?情況可能發(fā)生.在此情況下,令

定理8 對于這里討論的組合設(shè)備的調(diào)度問題,一個由算法1至算法3求得的單晶圓穩(wěn)態(tài)調(diào)度在生產(chǎn)率的意義上是最優(yōu)的.

至此,基于本文的應(yīng)用對象,介紹了基于控制理論的調(diào)度新方法的建模、解的存在性分析和求解算法的全過程.在文獻(xiàn)[24]中,提供了應(yīng)用的例子以顯示如何應(yīng)用所提出的方法,有興趣的讀者可以參考文獻(xiàn)[24].需要指出的是,就上面討論的應(yīng)用問題來說,分析了所有可能可行解存在的情況.也就是說,上面的可行調(diào)度存在性分析攬括了整個可行解空間,因此所獲得的解是最優(yōu)的.

5 討論

眾所周知,與本文前面討論的對象一樣,生產(chǎn)過程本質(zhì)上包含了離散事件過程,相應(yīng)的調(diào)度問題是離散優(yōu)化問題,涉及到組合爆炸的難題.因此,沒有一般性的有效求精確最優(yōu)解方法.特別是在有嚴(yán)格工藝約束的條件下,啟發(fā)式算法和元啟發(fā)式算法難于應(yīng)用,系統(tǒng)的調(diào)度問題是嚴(yán)峻的挑戰(zhàn).為此,人們不得不應(yīng)用數(shù)學(xué)規(guī)劃建模和求解,但由于計算復(fù)雜性,難于在實際中應(yīng)用.實際上,在半導(dǎo)體制造組合設(shè)備的調(diào)度中,除了本文的研究團隊外,其他研究人員基本上應(yīng)用數(shù)學(xué)規(guī)劃方法進行研究,通過POPN建模,然后建立整數(shù)規(guī)劃模型求解[15-19].由于整數(shù)規(guī)劃求解指數(shù)增長的計算復(fù)雜性,其研究成果很難在實際中應(yīng)用.

需要指出的是,當(dāng)生產(chǎn)過程存在著嚴(yán)格工藝約束的時候,一定會存在著沒有可行解的情況.因此,如果應(yīng)用數(shù)學(xué)規(guī)劃的方法,不僅求解困難,當(dāng)求不出可行解時,還難于找出無解的原因.另外,一個離散調(diào)度問題,盡管用一般性方法求解面臨著組合優(yōu)化的難題,但并不意味著沒有有效的方法可以求解.在某些情況下,根據(jù)問題的特征,有可能簡單求解.

就半導(dǎo)體制造中組合設(shè)備的調(diào)度問題而言,應(yīng)用基于離散事件系統(tǒng)控制理論的新方法,本文成功地將一個離散優(yōu)化問題轉(zhuǎn)換為決定機械手等待時間的問題,它是一個典型的連續(xù)優(yōu)化問題.并且利用了其特點,使得最優(yōu)解可以非常簡單地求得.應(yīng)用所提出的方法,解決了一系列半導(dǎo)體制造中組合設(shè)備的調(diào)度問題[25-36].

生產(chǎn)系統(tǒng)中的擾動是不可避免的,一個有效的調(diào)度系統(tǒng)需要對擾動快速和正確的響應(yīng).對此,基于數(shù)學(xué)規(guī)劃的方法很難做到.應(yīng)用本文提出的基于離散事件系統(tǒng)控制理論的新方法,半導(dǎo)體制造中組合設(shè)備的擾動可以有效地處理,并能保證其可行性[37-39].

組合設(shè)備是半導(dǎo)體芯片制造的關(guān)鍵裝備,從前面的討論可知,其加工過程是通過調(diào)度裝備內(nèi)部的機械手的動作實現(xiàn)的.這種調(diào)度不是芯片制造廠家完成的,而是裝備制造商將算法寫入到裝備的控制器.因此,其調(diào)度算法是芯片制造裝備研發(fā)的關(guān)鍵之一.由于,基于離散事件系統(tǒng)控制理論調(diào)度算法的優(yōu)越性,本文研究團隊正在與半導(dǎo)體芯片制造裝備開發(fā)商合作進行相關(guān)裝備的研發(fā).

相對于半導(dǎo)體芯片制造組合設(shè)備的調(diào)度問題,石油化工生產(chǎn)過程的規(guī)模極其巨大、約束更多、需要優(yōu)化的目標(biāo)很多,因此其生產(chǎn)調(diào)度問題更為復(fù)雜、更為困難.基于離散事件系統(tǒng)控制理論的調(diào)度新方法成功地應(yīng)用于煉油生產(chǎn)過程的調(diào)度問題,使得對于規(guī)模巨大的實際應(yīng)用問題能夠有效地求解[41-51].

本文所提出的方法的應(yīng)用范圍是一個需要進一步探索的問題.比如說什么類型工藝約束下的調(diào)度問題可以應(yīng)用,用什么模型建?？梢赃_(dá)到此目的.這需要根據(jù)實際應(yīng)用問題進行分析,也是今后需要探索的方向.另一個問題是,可行性分析可能會損失某些可行解,導(dǎo)致可行解空間的壓縮,從而降低解的最優(yōu)性.對這一問題,一方面,可以通過對系統(tǒng)的深入分析,提高可行性分析的質(zhì)量,從而提高解的質(zhì)量.另一方面,在問題非常復(fù)雜并無法精確求得最優(yōu)可行解的情況下,求得一個滿意的次優(yōu)可行解也是十分重要的.實際上,啟發(fā)式算法、進化計算等方法都是為了解決計算復(fù)雜性而求次優(yōu)解的方法.在啟發(fā)式算法、進化計算等方法不能應(yīng)用的情況下,本文的方法是一個很好的補充.

6 結(jié)論

盡管調(diào)度問題是一個經(jīng)典的研究問題,并且人們認(rèn)為相關(guān)的理論已經(jīng)基本成熟.但是,一方面由于當(dāng)今面對的系統(tǒng)越來越復(fù)雜,新的調(diào)度問題層出不窮,現(xiàn)有的理論和方法面臨著挑戰(zhàn).另一方面,由于信息化的需要和工業(yè)4.0的提出,需要實現(xiàn)對系統(tǒng)的自動化管理和控制,對調(diào)度的有效性提出了更高的要求.

具有嚴(yán)格工藝約束的生產(chǎn)調(diào)度問題是目前面臨的許多復(fù)雜調(diào)度問題中的重要一類.對這類問題已有的精確求解方法難于解決計算復(fù)雜性問題,不能滿足實際的應(yīng)用需求.而啟發(fā)式算法和元啟發(fā)式算法又不能保證調(diào)度的可行性,在很多情況下元啟發(fā)式算法也不滿足實時性要求.面對這一挑戰(zhàn),本團隊在離散事件系統(tǒng)控制理論的框架下研究了半導(dǎo)體芯片制造組合設(shè)備、石化煉油過程、生化物質(zhì)高速篩選系統(tǒng)的調(diào)度問題,提出了有效的求解方法.本文是這些方法的總結(jié)和提煉,并通過半導(dǎo)體芯片制造組合設(shè)備的調(diào)度問題進行介紹.接下來的工作是致力于將這一方法推廣到更多的應(yīng)用領(lǐng)域.同時,也將與相關(guān)的企業(yè)合作,努力將所獲得的成果實現(xiàn)轉(zhuǎn)化.