基于五維調(diào)度算法的并行設(shè)備車間調(diào)度方法

劉 琴， 陳 進

(江南大學 機械工程學院，江蘇 無錫214122)

一般柔性數(shù)控加工車間，對提高設(shè)備利用率和及時完成給定的任務(wù)有很高的需求。在此需求下，應(yīng)該將任務(wù)的每道工序都分配到合適的設(shè)備上加工。每個任務(wù)中的每道工序都可以在多臺不同的設(shè)備上加工完成。設(shè)備可分為3 種［1］:有相同功能完全相同的平行設(shè)備，功能不同但加工時間相同的同類設(shè)備，以及功能和加工時間都不相同的不相關(guān)設(shè)備。

在有n 個任務(wù)、m 臺設(shè)備的調(diào)度問題中，每個任務(wù)都有規(guī)定的工藝路線，每道工序都可以由一組具有相同或不同特點的設(shè)備來完成。其中最關(guān)鍵的問題就是為每道工序選擇合適的設(shè)備，使加工成本最低。

目前，國內(nèi)外就此研究方法主要有圖論法、動態(tài)規(guī)劃法、線性規(guī)劃法以及遺傳算法等。Gupta 等［2］將同類并行設(shè)備的車間調(diào)度問題納入考慮范疇，并為最小最大延遲設(shè)計了2 種啟發(fā)式算法，但并沒有考慮到設(shè)備利用率問題。Kang 等［3］提出了一種用于處理包括返工概率、交貨日期以及根據(jù)工藝路線設(shè)置時間的并行設(shè)備調(diào)度方法，但此方法是以假定每臺設(shè)備上每個任務(wù)的返工概率是可以通過設(shè)備上的歷史數(shù)據(jù)采集為基礎(chǔ)的。Ozlen 等［4］則考慮到重新規(guī)劃的問題，當一組任務(wù)已經(jīng)分配給不相關(guān)的并行設(shè)備時，他們提出可以指數(shù)次算法來生成所需的有效解決方案，并使特定功能運算達到最優(yōu)化，但其運算過程較為復雜，運算周期較長。

文中研究的主要問題是，在滿足作業(yè)車間相關(guān)約束和規(guī)范的前提下，找到加工一組任務(wù)的最優(yōu)序列。作業(yè)車間調(diào)度［5］主要需要解決的便是如何提高設(shè)備利用率問題，而車間作業(yè)調(diào)度應(yīng)有實時性，如調(diào)度時間過長，會影響其運作效率。因此，文中所提算法著重于提高設(shè)備的利用率，減少調(diào)度時間，使車間作業(yè)成本達到最低化。

1 五維調(diào)度算法

1.1 五維調(diào)度算法介紹

問題為:在有同類并行設(shè)備的車間加工中，在保證訂單按時完成的前提下，找出使設(shè)備利用率最高的一組加工序列，并加快運算速度。為此，提出五維調(diào)度算法(FDA)。FDA 中包含5 個獨立的參數(shù)，分別代表工件的交貨期與當前時間的差值、本工序之后本工件的剩余加工時間、本工序之后當前設(shè)備的剩余加工時間、本工件已排最晚時間與當前設(shè)備已排最晚時間之差的絕對值、當前工序的加工時間。

問題的條件為:某加工車間有m 臺設(shè)備、n 個需要加工的任務(wù)，每個任務(wù)都有已定的工藝路線，且每道工序的預計工時都是確定的，并有z 臺可用設(shè)備［6］。

問題的變量為:i 是任務(wù)編號，i = 1，2，…，n。j是設(shè)備編號，j = 1，2，…，m。g 是任務(wù)i 當前調(diào)度到工序的工序序號。則五維調(diào)度算法的5 個獨立參數(shù)可描述為

式中，di指任務(wù)i 的計劃交貨期與當前時間的差值，差值越小，說明任務(wù)越緊急，則應(yīng)優(yōu)先排產(chǎn);是任務(wù)i 根據(jù)其工藝路線，在第g 道工序后的所有工序加工所需的時間之和，即是指任務(wù)i的剩余需加工工時，任務(wù)的剩余工時越少，則越應(yīng)優(yōu)先安排加工，可減少車間任務(wù)堆積，并保證任務(wù)按時完成;Aj是所有需在設(shè)備j 上加工的工序工時總和是指在設(shè)備j 上已排工序的加工時間總和，其中Θ 是指在設(shè)備j 上已排的所有任務(wù)的集合，q 是指任務(wù)u 在設(shè)備j 加工的工序序號;(Aj－)指設(shè)備j 的剩余可加工時間，因為車間有同類并行設(shè)備，同一道工序有多臺設(shè)備可供選擇，所以設(shè)備剩余加工時間越短，越可在此設(shè)備上優(yōu)先安排加工，可有效地提高設(shè)備利用率;yj*(－1)，i，g－1指任務(wù)i 在其g －1 道工序上已排的計劃結(jié)束時間指設(shè)備j 已排的最晚計劃結(jié)束時間;指兩者之差的絕對值，該差值越小，任務(wù)加工越緊湊，可保證訂單按時完成［7］;tj，i，g指任務(wù)i 在第g 道工序加工工時，加工工時越大，則越先排產(chǎn)，可提高設(shè)備利用率。

綜上所述，最小化的前4 項及最大化的后1 項，構(gòu)成了最小的評價指標，即V 值，其所屬任務(wù)在所屬設(shè)備上優(yōu)先排產(chǎn)。

1.2 五維調(diào)度算法運算步驟

首先介紹五維調(diào)度算法運算步驟中用到的5 個矩陣(m 為設(shè)備總數(shù)，n 為任務(wù)總數(shù)):

tj，i，g:任務(wù)i 在第g 道工序上的加工時間，i = 1，2，…，n。t 為時間矩陣，g 是任務(wù)i 的工序序號。另外，tj，i，g= tc，i，g，即工序g 可在不同的設(shè)備上加工，且加工時間相同，j 和c 是設(shè)備編號，j ≠c。則T 矩陣為:Ts=(tj，i，s)m×n。

rj，i，s:根據(jù)工藝路線任務(wù)i 在設(shè)備j 上加工的工序序號，i = 1，2，…，n;j = 1，2，…，m。s 是任務(wù)i 可以在設(shè)備j 上加工的工序數(shù)。如果任務(wù)i 的第g 道工序以及第f 道工序都可以在設(shè)備j 上加工完成，設(shè)備j 在任務(wù)i 上就有2 個角色，則s = 1，2，rj，i，1= g，rj，i，2=f。假設(shè)每臺設(shè)備在同一個任務(wù)中都可扮演z個不同的角色，也就是說，每臺設(shè)備都可加工同一任務(wù)中的z 道工序，而且加工每道工序都有z 臺設(shè)備可供選擇。則R 矩陣為:Rs= (rj，i，s)m×n。

eg，i，s:任務(wù)i 在加工其第g 道工序可供選擇的第s 臺設(shè)備。很明顯，R 和E 是一一對應(yīng)，可以交換的。則E 矩陣為:Es= (eg，i，s)m×n。

xjig:任務(wù)i 的第g 道工序在設(shè)備j 上加工的計劃開始時間，i = 1，2…，n;j = 1，2，…m。X 是一個三維的狀態(tài)矩陣。g 是任務(wù)i 的工序序號。則狀態(tài)矩陣，即X 矩陣為:Xs= (xg，i，s)m×n。

yjig:任務(wù)i 的第g 道工序在設(shè)備j 上加工的計劃結(jié)束時間，i = 1，2，…，n;j = 1，2，…，m。Y 是一個三維的輸出矩陣。則輸出矩陣，即Y 矩陣為

五維調(diào)度算法的優(yōu)化調(diào)度步驟:

1)準備T 矩陣、R 矩陣和E 矩陣。

2)搜索最低評價指標，其范圍是任務(wù)i 從1 到n取值，工序序號g 從1 到m 取值，p(i)= g 記錄當前任務(wù)排產(chǎn)到的位置。以上5 因素評價指標V 值越小，則代表越可優(yōu)先加工。搜索最低評價指標有兩個步驟:(1)從當前計算的工序所有可用設(shè)備中選擇V值最小的設(shè)備，假設(shè)設(shè)備編號是j;(2)將Vj，i，g代入，與其它所有任務(wù)的V 值進行比較，選擇V 值最小的任務(wù)，將其固定在當前加工位置上。在此道工序排完之后，p(i)= g +1。

3)計算在設(shè)備j 上任務(wù)的狀態(tài)矩陣和輸出矩陣:

4)繼續(xù)從2)開始，直到所有的任務(wù)都完成排產(chǎn)。

2 計算實驗

為了驗證五維調(diào)度算法的有效性，設(shè)計并實施了一系列的計算實驗。實驗的目的是揭示不同的算法在相同條件基礎(chǔ)上的相對表現(xiàn)和不同的結(jié)構(gòu)公式。

實驗平臺是一個帶有2 GHzCPU 和2 GB RAM的個人電腦，程序是用C ++ builder 來編程。工時t和工序順序矩陣是從均勻離散時間中隨機畫出的［8］。

遺傳算法(GA)是建立在生物進化模型上強大的搜索技術(shù)，已被許多用戶應(yīng)用于作業(yè)車間調(diào)度領(lǐng)域［9］，文中也使用這個方法來解決類似例子。其中，遺傳算法的相關(guān)參數(shù)設(shè)置［10］如下:

群體大小= 50;終止進化代數(shù)= 100;交叉概率= 0.85;變異概率= 0.01。

文中做了3 組實驗:第1 組設(shè)定任務(wù)數(shù)為10，設(shè)備數(shù)為10，平均每個任務(wù)的總工序數(shù)為10;第2 組設(shè)定任務(wù)數(shù)為50，設(shè)備數(shù)為25，平均每個任務(wù)的總工序數(shù)為25;第3 組任務(wù)數(shù)為100，設(shè)備數(shù)為50，平均每個任務(wù)的總工序數(shù)為50(見表1)。每組實驗中的每道工序都有1 ～5 臺設(shè)備可供選擇，且每臺設(shè)備每天的可利用時間都假設(shè)為24 h。每個實驗結(jié)果都是5 次相同條件下實驗得到結(jié)果的平均值，以保證結(jié)果的準備性。

表1 實驗的級別及相關(guān)因素Tab.1 Level and related factors of Experiments

3 結(jié)果與討論

通過比較計算時間及排產(chǎn)完成后的設(shè)備利用率來比較GA、FDA 兩種算法的優(yōu)化程度。

首先，比較兩種算法計算時間的差異。如表2 所示，設(shè)備數(shù)為10、任務(wù)數(shù)為10 的條件下，GA 的計算時間為50 s，F(xiàn)DA 的計算時間為4 s;設(shè)備數(shù)為25、任務(wù)數(shù)為50 的條件下，GA 的計算時間為220 s，F(xiàn)DA的計算時間為35 s;設(shè)備數(shù)為50，任務(wù)數(shù)為100 的條件下，GA 的計算時間為450 s，F(xiàn)DA 的計算時間為110 s。顯而易見，在計算時間上FDA 是優(yōu)于GA 的。

在實際生產(chǎn)中，每天需要加工的任務(wù)數(shù)一般都大于100 個，因此計算時間會相對更長。而生產(chǎn)中，當然是不希望把過多時間花在做計劃上，尤其是生產(chǎn)周期較短且容易有插單等狀況的企業(yè)，如果用GA進行計算，時間冗長，會影響生產(chǎn)進度，顯然是不切實際的。因此，在此方面FDA 有很大優(yōu)勢。

表2 實驗計算時間對比Tab.2 Contrast of calculation time

然后，再從設(shè)備利用率角度來比較兩種算法。由于數(shù)據(jù)較龐大，以10 × 10 為例計算設(shè)備利用率，其它兩組實驗的設(shè)備利用率通過甘特圖［5］可以直觀形象地顯示出來。

圖1 所示為10 ×10 實驗下兩種算法的甘特圖對比。甘特圖的橫軸為時間軸，每一格代表1 h，豎軸為設(shè)備編號，圖中深色部分代表有任務(wù)在加工，淡色部分代表無任務(wù)在加工。因此，通過觀察圖中深色部分占總圖的比例，即可看出其設(shè)備利用率(設(shè)備利用率= 設(shè)備工作時間/設(shè)備可用時間)的大小(見表3)。

圖1 10 ×10 甘特圖對比Fig.1 Contrast of 10 ×10 gantt chart

表3 實驗設(shè)備利用率對比Tab.3 Contrast of equipment utilization rate

圖2，3 分別為50 ×25，100 ×50 的實驗下兩種算法的甘特圖對比。

圖2 50 ×25 甘特圖對比Fig.2 Contrast of 50 ×25 gantt chart

圖3 100 ×50 甘特圖對比Fig.3 Contrast of 100 ×50 gantt chart

由表3 的計算結(jié)果以及3 幅甘特圖的對比可以看出，F(xiàn)DA 所得到排程結(jié)果的設(shè)備利用率比GA 更優(yōu)。在實際生產(chǎn)中，當然希望設(shè)備利用率更高一些，這樣可以盡早完成所需加工的任務(wù)，并且插單情況發(fā)生時，可以及時應(yīng)對。

4 結(jié) 語

文中描述了同類并行設(shè)備的一種新算法，舉例證明了這種算法優(yōu)于現(xiàn)有的GA。在設(shè)備數(shù)量從10到50、任務(wù)數(shù)量從10 到100 的調(diào)度問題上，通過評價兩種算法的計算時間以及設(shè)備利用率，證明FDA的優(yōu)化程度更高。實驗結(jié)果表明，F(xiàn)DA 做生產(chǎn)調(diào)度可得出較優(yōu)的排產(chǎn)結(jié)果，并且運算效率也有很大提高。

［1］CHENG T C E，CHEN Z L.Parallel-machine scheduling problems with earliness and tardiness penalties［J］.The Journal of the Operational Research Society，1994，45(6):685-695.

［2］Gupta J N D，Ruiz-Torres A J，Webster S.Minimizing maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow-time［J］.The Journal of the Operational Research Society，2003，54(12):1263-1274.

［3］KANG Y H，KIM S S，SHIN H J. A dispatching algorithm for parallel machines with rework processes［J］. The Journal of the Operational Research Society，2009，61(1):144-155.

［4］Ozlen M，Azizoglu M. Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria［J］. The Journal of the Operational Research Society，2011，62(1):152-164.

［5］Rojanasoonthon S，Bard J F，Reddy S D.Algorithms for parallel machine scheduling:a case study of the tracking and data relay satellite system［J］.The Journal of the Operational Research Society，2003，54(8):806-821.

［6］WANG C J，XI Y G. Performance analysis of active schedules in identical parallel machine［J］. Journal of Control Theory and Applications，2007，5(3):239-243.

［7］楊宏安，孫樹棟，王蓀馨，等.基于約束滿足的Job Shop 調(diào)度算法研究［J］.計算機工程與應(yīng)用，2003，39(31):36-371.

YANG Hongan，SUN Shudong，WANG Sunxin，et al. A Job Shop scheduling algorithm based on constraint satisfaction problem［J］.Computer Engineering and Applications，2003，39(31):36-37.(in Chinese)

［8］LIN B M T，JENG A A K. Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs［J］.International Journal Production Economics，2004，91(2):121-134.

［9］王立平，曹立明.遺傳算法—理論、應(yīng)用與軟件實現(xiàn)［M］.西安:西安交通大學出版社，2002.

［10］XONG H.Heuristic method for dynamic job shop scheduling problem with operation relativity［J］.Chinese Journal of Mechanical Engineering，2006，42(8):50-55.