劉 琴， 陳 進(jìn)

(江南大學(xué) 機(jī)械工程學(xué)院，江蘇 無(wú)錫214122)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

rj，i，s:根據(jù)工藝路線任務(wù)i 在設(shè)備j 上加工的工序序號(hào)，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 個(gè)角色，則s = 1，2，rj，i，1= g，rj，i，2=f。假設(shè)每臺(tái)設(shè)備在同一個(gè)任務(wù)中都可扮演z個(gè)不同的角色，也就是說(shuō)，每臺(tái)設(shè)備都可加工同一任務(wù)中的z 道工序，而且加工每道工序都有z 臺(tái)設(shè)備可供選擇。則R 矩陣為:Rs= (rj，i，s)m×n。

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

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

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

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

1)準(zhǔn)備T 矩陣、R 矩陣和E 矩陣。

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

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

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

2 計(jì)算實(shí)驗(yàn)

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

實(shí)驗(yàn)平臺(tái)是一個(gè)帶有2 GHzCPU 和2 GB RAM的個(gè)人電腦，程序是用C ++ builder 來(lái)編程。工時(shí)t和工序順序矩陣是從均勻離散時(shí)間中隨機(jī)畫出的［8］。

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

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

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

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

3 結(jié)果與討論

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

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

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

表2 實(shí)驗(yàn)計(jì)算時(shí)間對(duì)比Tab.2 Contrast of calculation time

然后，再?gòu)脑O(shè)備利用率角度來(lái)比較兩種算法。由于數(shù)據(jù)較龐大，以10 × 10 為例計(jì)算設(shè)備利用率，其它兩組實(shí)驗(yàn)的設(shè)備利用率通過(guò)甘特圖［5］可以直觀形象地顯示出來(lái)。

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

圖1 10 ×10 甘特圖對(duì)比Fig.1 Contrast of 10 ×10 gantt chart

表3 實(shí)驗(yàn)設(shè)備利用率對(duì)比Tab.3 Contrast of equipment utilization rate

圖2，3 分別為50 ×25，100 ×50 的實(shí)驗(yàn)下兩種算法的甘特圖對(duì)比。

圖2 50 ×25 甘特圖對(duì)比Fig.2 Contrast of 50 ×25 gantt chart

圖3 100 ×50 甘特圖對(duì)比Fig.3 Contrast of 100 ×50 gantt chart

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

4 結(jié) 語(yǔ)

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

［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］楊宏安，孫樹(shù)棟，王蓀馨，等.基于約束滿足的Job Shop 調(diào)度算法研究［J］.計(jì)算機(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)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，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.