謝志強(qiáng) 王 茜

(哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150000)

1 引言

傳統(tǒng)的生產(chǎn)制造過(guò)程，將加工[1,2]和裝配[3,4]作為兩個(gè)獨(dú)立的階段，對(duì)問(wèn)題的研究主要針對(duì)零部件的批量加工，例如針對(duì)大批量生產(chǎn)環(huán)境的flow shop調(diào)度問(wèn)題[5,6]和針對(duì)多品種小批量生產(chǎn)環(huán)境的job-shop調(diào)度問(wèn)題[7,8]。隨著社會(huì)多元化需求的增加，多品種小批量的訂單逐漸增多，在這種多元化需求環(huán)境的驅(qū)動(dòng)下，需要一種新的生產(chǎn)調(diào)度模式，滿(mǎn)足人民個(gè)性化定制型產(chǎn)品的需求。這樣，綜合調(diào)度[9]應(yīng)運(yùn)而生，它將產(chǎn)品的加工過(guò)程和裝配過(guò)程統(tǒng)一為加工過(guò)程，將復(fù)雜產(chǎn)品映射為虛擬加工樹(shù)。由于同時(shí)考慮了工序間的順序約束和裝配約束，綜合調(diào)度問(wèn)題在縮短產(chǎn)品制造周期、提高生產(chǎn)系統(tǒng)效率方面，具有重要的研究意義和實(shí)際應(yīng)用價(jià)值。另外，隨著加工技術(shù)、自動(dòng)化技術(shù)的發(fā)展，柔性制造系統(tǒng)和數(shù)控加工中心等帶有一定柔性的生產(chǎn)系統(tǒng)在實(shí)際企業(yè)生產(chǎn)中扮演著越來(lái)越重要的角色，柔性作業(yè)車(chē)間調(diào)度問(wèn)題更加符合實(shí)際生產(chǎn)問(wèn)題。因此，本文研究具有柔性設(shè)備選擇的樹(shù)狀結(jié)構(gòu)產(chǎn)品綜合調(diào)度問(wèn)題。

柔性綜合調(diào)度問(wèn)題較傳統(tǒng)的車(chē)間調(diào)度問(wèn)題和一般的綜合調(diào)度問(wèn)題更為復(fù)雜，也是一類(lèi)典型的NP難問(wèn)題[10]。目前，對(duì)綜合調(diào)度問(wèn)題研究的文獻(xiàn)還相對(duì)較少，且主要求解單車(chē)間一般綜合調(diào)度問(wèn)題[11,12]等。 針對(duì)柔性綜合調(diào)度問(wèn)題，在基于啟發(fā)式規(guī)則的相關(guān)解決方案中，謝志強(qiáng)等人[13]提出了一種考慮設(shè)備無(wú)關(guān)延遲約束的綜合柔性調(diào)度算法。謝志強(qiáng)等人[14]從設(shè)備找工序的角度出發(fā)，提出了一種基于設(shè)備驅(qū)動(dòng)的綜合柔性調(diào)度沖突調(diào)解算法。Birgin等人[15]提出了一種基于鏈表的柔性綜合調(diào)度算法，并且在此基礎(chǔ)上進(jìn)一步提出了一種基于集束搜索的柔性綜合調(diào)度算法。謝志強(qiáng)等人[16]提出了一種設(shè)備驅(qū)動(dòng)和實(shí)質(zhì)路徑的動(dòng)態(tài)并行綜合柔性調(diào)度算法，該算法兼顧了設(shè)備驅(qū)動(dòng)和動(dòng)態(tài)實(shí)質(zhì)短路徑策略的優(yōu)點(diǎn)，提高了設(shè)備利用率和并行處理效率。針對(duì)柔性綜合調(diào)度問(wèn)題，在基于智能優(yōu)化算法的相關(guān)解決方案中，趙詩(shī)奎等人[17]提出了一種基于虛擬零部件級(jí)別分區(qū)編碼的產(chǎn)品綜合調(diào)度算法。該算法將產(chǎn)品的各零部件設(shè)置級(jí)別，按級(jí)別進(jìn)行分區(qū)編碼，該種編碼方式保證了初始解的可行性，但其編碼方式存在缺點(diǎn)，即有遺漏最優(yōu)解的風(fēng)險(xiǎn)。Lei等人[18]提出了一種基于工序關(guān)系矩陣表的綜合調(diào)度算法，該算法首先為產(chǎn)品建立一個(gè)工序關(guān)系矩陣表，隨后基于該表設(shè)計(jì)了相應(yīng)的編碼規(guī)則和進(jìn)化算子。由于綜合調(diào)度問(wèn)題中復(fù)雜優(yōu)先順序約束條件的存在，導(dǎo)致已有的各種編碼方法和進(jìn)化算子均已失效，進(jìn)而使得智能優(yōu)化算法在綜合調(diào)度問(wèn)題中的應(yīng)用受限?？傮w來(lái)說(shuō)，研究柔性綜合調(diào)度問(wèn)題的相關(guān)文獻(xiàn)還相對(duì)較少。

在上述求解柔性綜合調(diào)度問(wèn)題的相關(guān)算法中，均考慮正向調(diào)度，即從葉節(jié)點(diǎn)開(kāi)始調(diào)度，直至根節(jié)點(diǎn)調(diào)度完畢，則代表產(chǎn)品調(diào)度加工完成。在正向調(diào)度的解決方案中，當(dāng)某一工序有多個(gè)緊前工序時(shí)，難以合理安排這些相關(guān)工序，進(jìn)而影響產(chǎn)品總加工時(shí)間。因此，本文采用逆序調(diào)度的思想，從根節(jié)點(diǎn)開(kāi)始調(diào)度，這樣可以簡(jiǎn)化某一工序存在多緊前工序的約束條件，便于合理安排各工序。最終將調(diào)度產(chǎn)生的逆序調(diào)度方案轉(zhuǎn)換為正序調(diào)度方案。

2 問(wèn)題描述

在傳統(tǒng)的柔性Job-shop調(diào)度問(wèn)題中，工序間的總體約束結(jié)構(gòu)呈線(xiàn)狀，而柔性綜合調(diào)度問(wèn)題中調(diào)度對(duì)象的總體工藝結(jié)構(gòu)圖呈樹(shù)狀結(jié)構(gòu)，這使得在樹(shù)狀結(jié)構(gòu)產(chǎn)品柔性綜合調(diào)度問(wèn)題的調(diào)度過(guò)程中，需要考慮工序間的協(xié)調(diào)和同步問(wèn)題，從而使問(wèn)題的目標(biāo)函數(shù)得到優(yōu)化。在該問(wèn)題中，某產(chǎn)品的工藝加工樹(shù)如圖1所示，每個(gè)工序由3部分構(gòu)成，即工序名、加工設(shè)備集以及對(duì)應(yīng)的加工時(shí)間，箭頭的指向規(guī)定了工序間的加工順序。樹(shù)狀結(jié)構(gòu)產(chǎn)品柔性綜合調(diào)度問(wèn)題的數(shù)學(xué)模型可以描述為：由n道工序 {oi}1≤i≤n構(gòu)成的樹(shù)狀結(jié)構(gòu)復(fù)雜單產(chǎn)品，需要在m臺(tái)設(shè)備上進(jìn)行加 工，工 序oi的 可 加 工 設(shè) 備 集 為{Mi}1≤i≤n ?{1,2,...,m}并 且Mi ?=?，pik為 工 序oi在 設(shè) 備k ∈Mi上的加工時(shí)間。si和ci分別表示工序oi的開(kāi)始加工時(shí)間和完工時(shí)間。xli=1表示工序ol是工序oi的工藝緊前工序；yik=1表示工序oi在設(shè)備k∈Mi上進(jìn)行加工；zij=1表示在同設(shè)備上加工的工序oi和oj，工序oi為工序oj的設(shè)備緊前工序，即工序oj在工序oi加工完成之后才開(kāi)始加工。因此本問(wèn)題的數(shù)學(xué)描述為

圖1 產(chǎn)品A加工工藝樹(shù)

其中，本問(wèn)題的調(diào)度目標(biāo)是合理安排各工序以使產(chǎn)品的完工時(shí)間盡可能短，目標(biāo)函數(shù)如式(1)所示。式(2)表示每道工序要被分配到某1臺(tái)且只能1臺(tái)機(jī)器上進(jìn)行加工；式(3)表示工序oi的加工時(shí)間，式(4)為工序oi的開(kāi)工時(shí)間，即工序oi要在合理的條件下盡早開(kāi)始加工；式(5)為工序oi的完工時(shí)間。式(6)表示同一臺(tái)設(shè)備上連續(xù)加工的兩道工序，后一道工序的開(kāi)工時(shí)間不能早于前一道工序的完工時(shí)間。

3 算法設(shè)計(jì)

對(duì)于一棵產(chǎn)品工藝加工樹(shù)，由于根節(jié)點(diǎn)加工完畢代表整個(gè)產(chǎn)品加工完畢，即根節(jié)點(diǎn)工序加工完成為最終加工目的。首先加工葉節(jié)點(diǎn)最后加工根節(jié)點(diǎn)會(huì)導(dǎo)致加工過(guò)程中工序有多個(gè)緊前約束條件，而首先加工根節(jié)點(diǎn)，可減少相關(guān)工序節(jié)點(diǎn)的加工約束。本文采用逆序調(diào)度的思想，即首先加工根節(jié)點(diǎn)，直到葉節(jié)點(diǎn)加工完畢，該產(chǎn)品調(diào)度結(jié)束。為了便于算法描述以及后續(xù)相關(guān)策略的設(shè)計(jì)，本文首先給出如下定義：

定義1 目標(biāo)工序：調(diào)度過(guò)程中，將當(dāng)前正在安排的某一工序稱(chēng)為目標(biāo)工序。

定義2 待調(diào)度工序集：即將調(diào)度的某一層工序組成的集合。

定義3 擬加工時(shí)間：對(duì)于可在超過(guò)3臺(tái)設(shè)備上加工的工序，本文去掉最長(zhǎng)加工時(shí)間和最短加工時(shí)間，然后計(jì)算剩余加工時(shí)間的平均加工時(shí)間作為該工序的擬加工時(shí)間；對(duì)于可在少于兩臺(tái)設(shè)備上加工的工序，直接計(jì)算該時(shí)間集的平均加工時(shí)間作為該工序的擬加工時(shí)間。

定義4 偽緊前工序：由于本文采用逆序調(diào)度，原本某一工序的緊后工序成為該工序的緊前工序，稱(chēng)為偽緊前工序。

定義5 偽緊后工序：由于本文采用逆序調(diào)度，原本某一工序的緊前工序成為該工序的緊后工序，稱(chēng)為偽緊后工序。

定義6 偽緊后路徑長(zhǎng)度：按擬加工時(shí)間計(jì)算時(shí)，由目標(biāo)工序的所有偽緊后工序加工到葉節(jié)點(diǎn)的總時(shí)間的最大值。

定義7 偽緊前路徑長(zhǎng)度：由根節(jié)點(diǎn)工序開(kāi)始加工，目標(biāo)工序的偽緊前工序的實(shí)際完工時(shí)間。

定義8 總路徑長(zhǎng)度：目標(biāo)工序的偽緊前路徑長(zhǎng)度，偽緊后路徑長(zhǎng)度以及擬加工時(shí)間之和。

定義9 子孫節(jié)點(diǎn)：工序的后代子孫節(jié)點(diǎn)，例如工序A15的子孫節(jié)點(diǎn)為工序A9，A10，A3，A4，A1。

對(duì)于圖1所示的復(fù)雜產(chǎn)品柔性工藝加工樹(shù)，按照上述定義，我們計(jì)算其擬加工時(shí)間和偽緊后路徑長(zhǎng)度如圖2所示，例如對(duì)于工序A15，其擬加工時(shí)間為20，偽緊后路徑長(zhǎng)度為70。

圖2 圖1所示產(chǎn)品各工序擬加工時(shí)間和偽緊后路徑長(zhǎng)度

3.1 逆序?qū)觾?yōu)先策略

本文提出逆序?qū)觾?yōu)先的策略，對(duì)各工序按層進(jìn)行調(diào)度。首先，為每個(gè)工序設(shè)置其所在的層數(shù)，即規(guī)定根節(jié)點(diǎn)所在的層為第1層，隨著后續(xù)工序其深度每增加1層，所在層數(shù)加1。然后，將第i層上的所有工序放入工序集合Oi中作為第i層的待調(diào)度工序集，例如O4={A8, A9, A10, A11, A12, A13}。最后，按照層數(shù)遞增的順序，依次對(duì)各層工序集進(jìn)行調(diào)度。由于本文采用逆序調(diào)度加工的思想，緩解了正序調(diào)度時(shí)，某一工序存在多個(gè)緊前工序，難以確定目標(biāo)工序開(kāi)工時(shí)間的問(wèn)題。另外，同層工序優(yōu)先調(diào)度，可以最大化的使同層工序并行加工。

3.2 動(dòng)態(tài)擬長(zhǎng)路徑策略

對(duì)于某層待調(diào)度工序集Oi={o1, o2, ···, on}，設(shè)其偽緊前工序集為Pi={p1, p2, ···, pn}，偽緊前工序的結(jié)束時(shí)間即偽緊前路徑長(zhǎng)度為PEi={pe1, pe2,···, pen}，擬加工時(shí)間集合為A_Ti={a_t1, a_t2,···, a_tn}，偽緊后工序集為Si={s1, s2, ···, sn}，偽緊后路徑長(zhǎng)度Ri={r1, r2, ···, rn}，計(jì)算第i層待調(diào)度工序集中各工序的總路徑長(zhǎng)度Ti=PEi+A_Ti+Ri，例如第j個(gè)工序的總路徑長(zhǎng)度為pej+a_tj+rj。

由于本文采用逆序調(diào)度的思想，目標(biāo)工序的偽緊前工序的結(jié)束時(shí)間，為目標(biāo)工序最早可加工時(shí)間，在不考慮設(shè)備占用的情況下，本文以各工序的總路徑長(zhǎng)度，來(lái)估計(jì)目標(biāo)工序子孫節(jié)點(diǎn)的最終完工時(shí)間，路徑長(zhǎng)度越大，說(shuō)明其對(duì)應(yīng)的子孫節(jié)點(diǎn)的完工時(shí)間越晚，所對(duì)應(yīng)的產(chǎn)品完工時(shí)間越晚。因此，本文優(yōu)先調(diào)度路徑長(zhǎng)度大的目標(biāo)工序，由于目標(biāo)工序的偽緊前工序的結(jié)束時(shí)間不同，導(dǎo)致每次計(jì)算總路徑長(zhǎng)度時(shí)所得結(jié)果不同，因此稱(chēng)該策略為動(dòng)態(tài)擬長(zhǎng)路徑策略。

該策略的主要思想是，按待調(diào)度工序集中各工序的總路徑長(zhǎng)度對(duì)各工序進(jìn)行降序排列，優(yōu)先調(diào)度總路徑長(zhǎng)度值大的目標(biāo)工序；當(dāng)總路徑長(zhǎng)度值相同時(shí)，優(yōu)先調(diào)度擬緊后路徑長(zhǎng)度大的工序；當(dāng)擬緊后路徑長(zhǎng)度值相同時(shí)，優(yōu)先調(diào)度擬緊后工序個(gè)數(shù)多的工序；當(dāng)緊后工序個(gè)數(shù)相同時(shí)，優(yōu)先調(diào)度擬加工時(shí)間值大的工序；再相同時(shí)，隨機(jī)選擇某一工序調(diào)度。

3.3 設(shè)備選擇策略

對(duì)于一棵柔性工藝加工樹(shù)，某一工序可能可以在多個(gè)設(shè)備上加工，但不同加工設(shè)備所需加工時(shí)間可能不同。為了盡可能地減少總加工時(shí)間，本文盡量為目標(biāo)工序選擇加工用時(shí)短的設(shè)備進(jìn)行加工。即針對(duì)目標(biāo)工序oj，獲取該工序的偽緊前工序完工時(shí)間，獲取該工序的可加工設(shè)備集并按加工時(shí)間從小到大排序，若可最短加工時(shí)間所對(duì)應(yīng)的設(shè)備在目標(biāo)工序的偽緊前工序完工時(shí)刻空閑，則將目標(biāo)工序分配至該設(shè)備上加工；否則，按序選擇將目標(biāo)工序安排至完工時(shí)間最早的設(shè)備上加工。 若存在多個(gè)設(shè)備加工時(shí)間相同，則優(yōu)先選擇目標(biāo)工序完工時(shí)間早的設(shè)備進(jìn)行加工。由于目標(biāo)工序偽緊后工序是在目標(biāo)工序的基礎(chǔ)上進(jìn)行加工，其偽緊后工序的開(kāi)工時(shí)間由該工序的結(jié)束加工時(shí)間決定，則選擇早結(jié)束方案所對(duì)應(yīng)的設(shè)備加工對(duì)縮短整體加工時(shí)間有利。

3.4 設(shè)備搶占策略

本文采用逆序調(diào)度的思想，從根節(jié)點(diǎn)開(kāi)始，按層序依次調(diào)度每層待調(diào)度工序集中的工序。由于同層工序間，不存在緊前緊后約束關(guān)系，為了充分提高設(shè)備占用率，縮短產(chǎn)品完工時(shí)間，本文考慮設(shè)備搶占情況，以?xún)?yōu)先加工可早加工的目標(biāo)工序。

由于首先調(diào)度根節(jié)點(diǎn)工序，因此，其開(kāi)工時(shí)間我們規(guī)定為0。對(duì)于目標(biāo)工序oj，在確定了加工設(shè)備進(jìn)行調(diào)度時(shí)，若其最早可加工時(shí)刻設(shè)備空閑，則考慮將該工序放置該時(shí)刻進(jìn)行加工，若該時(shí)刻有后續(xù)加工工序，則將其移至目標(biāo)工序完工時(shí)刻進(jìn)行加工。

3.5 基于完工時(shí)間翻轉(zhuǎn)的調(diào)度方案轉(zhuǎn)換策略

由于本文采用逆序調(diào)度的思想，所產(chǎn)生的調(diào)度方案為逆序調(diào)度方案。為了將逆序調(diào)度方案轉(zhuǎn)換為正序調(diào)度方案，即產(chǎn)品的調(diào)度從葉節(jié)點(diǎn)開(kāi)始，本文給出了一種基于完工時(shí)間翻轉(zhuǎn)的調(diào)度方案轉(zhuǎn)換策略。假設(shè)已知待轉(zhuǎn)換方案的產(chǎn)品最終完工時(shí)間，各工序的逆序開(kāi)工時(shí)間和逆序完工時(shí)間。則本文所述的轉(zhuǎn)換策略的具體方法為：首先，將各工序在逆序調(diào)度時(shí)的開(kāi)工時(shí)間和完工時(shí)間分別減去當(dāng)前方案的產(chǎn)品完工時(shí)間；然后，將各工序所對(duì)應(yīng)的結(jié)果取反，即將各個(gè)開(kāi)工時(shí)間和完工時(shí)間值變成非負(fù)數(shù)；最后將各工序?qū)?yīng)的開(kāi)工時(shí)間和完工時(shí)間交換即可獲得正序調(diào)度時(shí)各工序的調(diào)度時(shí)刻表。注意，在轉(zhuǎn)變?yōu)檎蛘{(diào)度方案后，若某一工序的所有緊前工序已加工完成，且當(dāng)前工序開(kāi)始加工時(shí)刻之前存在空閑時(shí)間段，則該工序可以向前移動(dòng)。但是，無(wú)論是在正序調(diào)度方案中還是逆序調(diào)度方案中，產(chǎn)品的最終完工時(shí)間是不變的。因此，本文并沒(méi)有考慮工序的移動(dòng)情況。

3.6 算法總體設(shè)計(jì)

本文所述的基于逆序?qū)觾?yōu)先的柔性綜合調(diào)度算法具體執(zhí)行步驟如下所述，算法總體流程圖如圖3所示。

圖3 算法總體流程圖

步驟1 輸入設(shè)備和產(chǎn)品加工信息，計(jì)算工序擬加工時(shí)間，偽緊后路徑長(zhǎng)度等屬性信息。

步驟2 執(zhí)行逆序?qū)觾?yōu)先策略，為各工序設(shè)計(jì)層優(yōu)先級(jí)，并按其所在的層數(shù)將其加入至不同的層待調(diào)度工序集，并將集合按層序升序排列，假設(shè)一共有m層工序，則最終一共產(chǎn)生m個(gè)工序集，i=1。

步驟3 判斷i是否大于m，若是則執(zhí)行步驟4；否則，執(zhí)行步驟5。

步驟4 執(zhí)行基于完工時(shí)間翻轉(zhuǎn)的調(diào)度方案轉(zhuǎn)換策略，將逆序調(diào)度方案，轉(zhuǎn)換為正序調(diào)度方案，算法結(jié)束。

步驟5 假設(shè)當(dāng)前待調(diào)度工序集為Oi，則執(zhí)行動(dòng)態(tài)擬長(zhǎng)路徑策略，將待調(diào)度工序集中各工序排序。

步驟6 判斷待調(diào)度工序集是否為空，若為空，則i=i+1，跳轉(zhuǎn)至步驟3；否則，執(zhí)行步驟7。

步驟7 獲取待調(diào)度工序中的首個(gè)工序作為目標(biāo)工序，并將其在待調(diào)度工序集中移除。

步驟8 按設(shè)備選擇策略為目標(biāo)工序確定加工設(shè)備。

步驟9 按設(shè)備搶占策略確定目標(biāo)工序開(kāi)工時(shí)間，跳轉(zhuǎn)至步驟6。

4 復(fù)雜度分析

設(shè)工序總數(shù)為n，可加工設(shè)備總數(shù)為m。初始時(shí)，算法需要計(jì)算工序擬加工時(shí)間以及其偽緊后路徑長(zhǎng)度，在計(jì)算目標(biāo)工序擬加工時(shí)間時(shí)，需要執(zhí)行m次操作，一共有n道工序，因此其時(shí)間復(fù)雜度為O(n×m)。計(jì)算工序偽緊后路徑長(zhǎng)度時(shí)，首先獲取其偽緊后工序的路徑長(zhǎng)度，然后加上當(dāng)前工序的擬加工時(shí)間，共有n道工序，因此，其時(shí)間復(fù)雜度為O(n)。本算法主要執(zhí)行以下操作：

(1) 逆序?qū)觾?yōu)先策略。該操作需要遍歷所有工序，將各工序加入不同的逆序待調(diào)度工序集，需要執(zhí)行n次操作，因此，逆序?qū)觾?yōu)先策略的時(shí)間復(fù)雜度為O(n)。

(2) 動(dòng)態(tài)擬長(zhǎng)路徑策略。對(duì)于當(dāng)前逆序?qū)哟{(diào)度工序集Oi，設(shè)其工序個(gè)數(shù)為ni，對(duì)于每道工序我們需要計(jì)算其總路徑長(zhǎng)度，即執(zhí)行兩次加法操作，總共執(zhí)行2×ni次操作，時(shí)間復(fù)雜度為O(ni)。然后需要按總路徑長(zhǎng)度對(duì)當(dāng)前工序集工序進(jìn)行排序，時(shí)間復(fù)雜度為O(nilog2ni)。最壞情況下，ni=n，因此，動(dòng)態(tài)擬長(zhǎng)路徑策略的時(shí)間復(fù)雜度為O(nlog2n)。

(3) 設(shè)備選擇策略。對(duì)目標(biāo)工序來(lái)說(shuō)，在為其選擇加工設(shè)備時(shí)，最壞情況下需要考慮所有可加工設(shè)備，即執(zhí)行m次操作。因此設(shè)備選擇策略的時(shí)間復(fù)雜度為O(n×m)。

(4) 設(shè)備搶占策略。確定目標(biāo)工序開(kāi)工時(shí)刻的時(shí)候需要確定其最早可加工時(shí)刻是否空閑，若空閑則搶占至該時(shí)刻進(jìn)行加工，總共需要判斷n次，因此時(shí)間復(fù)雜度為O(n)。

(5) 基于完工時(shí)間翻轉(zhuǎn)的調(diào)度方案轉(zhuǎn)換策略。在轉(zhuǎn)換過(guò)程中，需要將各工序在逆序調(diào)度時(shí)的開(kāi)工時(shí)間和完工時(shí)間分別減去當(dāng)前方案的產(chǎn)品完工時(shí)間；然后，將各工序所對(duì)應(yīng)的結(jié)果取反變成非負(fù)數(shù)；最后將各工序?qū)?yīng)的開(kāi)工時(shí)間和完工時(shí)間交換即可獲得正序調(diào)度時(shí)各工序的調(diào)度時(shí)刻表。因此，該策略的時(shí)間復(fù)雜度為O(n)。

綜上所述，本文所提算法的時(shí)間復(fù)雜度取上述各項(xiàng)操作的最大值，即所提算法的時(shí)間復(fù)雜度為O(nlog2n)。

5 實(shí)例對(duì)比分析

本文所述算法不針對(duì)任何具體產(chǎn)品，對(duì)所有算例均實(shí)用。為了進(jìn)一步闡述上述算法的執(zhí)行步驟，本節(jié)對(duì)圖1所示產(chǎn)品工藝加工樹(shù)進(jìn)行調(diào)度加工，并將調(diào)度方案與已有的主流的解決柔性綜合調(diào)度問(wèn)題的算法進(jìn)行對(duì)比。

計(jì)算各工序相關(guān)屬性信息，例如擬加工時(shí)間、偽緊后工序徑長(zhǎng)度等。

初始時(shí)，第1層待調(diào)度工序集為O1={A21}，僅包含一個(gè)元素，即根節(jié)點(diǎn)工序A21，其偽緊前工序集P1={}為空，因此，該層工序最早可加工時(shí)刻為PE1={0}，加工時(shí)間為t1={(M1,M2,M4)/(20,25, 15)}，擬加工時(shí)間集合A_T1={20}，由設(shè)備選擇策略為其選擇用時(shí)最短的設(shè)備M4進(jìn)行加工，其完工時(shí)間為時(shí)刻15，第1層待調(diào)度工序集調(diào)度結(jié)束，第1層工序結(jié)束時(shí)間為e1={A21/15}。

第2層待調(diào)度工序集為O2={A18, A19, A20}，其偽緊前工序集P2={A21, A21, A21}，最早可開(kāi)始加工時(shí)刻為PE2={15, 15, 15}，其加工時(shí)間集t2={(M1, M3, M4)/(20, 15, 25), (M2, M3,M4)/(15, 20, 25), (M3, M4)/(20, 20)}，擬加工時(shí)間集合A_T2={20, 20, 20}，偽緊后工序集合為S2={(A14, A15), (A16), (A17)}，當(dāng)前層待調(diào)度工序集的偽緊后路徑長(zhǎng)度集為R2={90, 77.5, 62.5}，則當(dāng)前待調(diào)度工序集各工序所對(duì)應(yīng)總路徑長(zhǎng)度為O2= PE2+A_T2+R2={A18/125, A19/112.5,A20/97.5}，對(duì)O2按其所對(duì)應(yīng)的總路徑長(zhǎng)度按降序進(jìn)行排列的并按序進(jìn)行調(diào)度，最終調(diào)度順序?yàn)閧A18, A19, A20}。對(duì)于工序A18，按設(shè)備選擇策略中短用時(shí)優(yōu)先原則，將其分配至設(shè)備M3進(jìn)行加工；對(duì)于工序A19，按設(shè)備選擇策略中短用時(shí)優(yōu)先原則，將其分配至設(shè)備M2上進(jìn)行加工；對(duì)于工序A20，按設(shè)備選擇策略中最早結(jié)束時(shí)間原則，確定其加工設(shè)備為M4。第2層待調(diào)度工序調(diào)度完成，其結(jié)束時(shí)間集e2={ A18/30, A19/30, A20/35}。

第3層待調(diào)度工序集為O3={A14, A15, A16,A17}，其偽緊前工序集P3={A18, A18, A19,A20}，最早可開(kāi)始加工時(shí)刻為PE3={30, 30, 30,35}，其加工時(shí)間集t3={(M1, M3, M4)/(20, 20,15), (M1, M3, M4)/(20, 15, 25), (M2, M4)/(20,40), (M2, M4)/(15, 20)}，擬加工時(shí)間集合A_T3={20, 20, 30, 17.5}，偽緊后工序集合為S3={(A8), (A9, A10), (A11), (A12, A13)}，當(dāng)前待調(diào)度工序?qū)拥膫尉o后路徑長(zhǎng)度為R3={25, 70,47.5, 45}，則當(dāng)前待調(diào)度工序集各工序所對(duì)應(yīng)總路徑長(zhǎng)度為O3= PE3+A_T3+R3={A14/75,A15/120, A16/107.5, A17/97.5}，對(duì)O3按其所對(duì)應(yīng)的總路徑長(zhǎng)度按降序排列并按序進(jìn)行調(diào)度，最終調(diào)度順序?yàn)閧A15, A16, A17, A14}。對(duì)于工序A15，按設(shè)備選擇策略中短用時(shí)優(yōu)先原則，確定其加工設(shè)備為M3；對(duì)于工序A16，按設(shè)備選擇策略中短用時(shí)優(yōu)先原則，確定其加工設(shè)備為M2；對(duì)于工序A17，按設(shè)備選擇策略中最早結(jié)束時(shí)間原則，其加工設(shè)備為M4；對(duì)于工序A14，按設(shè)備選擇策略中最早結(jié)束時(shí)間策略，其加工設(shè)備為M1。第3層待調(diào)度工序調(diào)度完成，其結(jié)束時(shí)間集e3={A14/50,A15/45, A16/50, A17/55}。

第4層待調(diào)度工序集為O4={A8, A9, A10, A11,A12, A13}，其偽緊前工序集P4={A14, A15, A15,A 1 6, A 1 7, A 1 7}，最早可開(kāi)始加工時(shí)刻為PE4={50, 45, 45, 50, 55, 55}，其加工時(shí)間集t4={(M1, M2, M3, M4)/(25, 25, 30, 25), (M1, M3,M4)/(20, 20, 45), (M2, M3, M4)/(25, 20, 20),(M1, M2, M4)/(10, 15, 25), (M1, M3, M4)/(15,15, 35), (M1, M2, M4)/(15, 20, 40)}，擬加工時(shí)間集合A_T4={25, 20, 20, 15, 15, 20}，偽緊后工序集合為S4={(), (A3), (A4), (A5), (A6), (A7)}，當(dāng)前待調(diào)度工序?qū)拥膫尉o后路徑長(zhǎng)度為R4={0, 50,20, 32.5, 20, 25}，當(dāng)前待調(diào)度工序集各工序所對(duì)應(yīng)總路徑長(zhǎng)度為O4= PE4+A_T4+R4={A8/75,A9/115, A10/85, A11/97.5, A12/90, A13/100}，對(duì)O4按其所對(duì)應(yīng)的總路徑長(zhǎng)度按降序排列并按序進(jìn)行調(diào)度，最終調(diào)度順序?yàn)閧A9, A13, A11, A12,A10, A8}。對(duì)于工序A9，按設(shè)備選擇策略，確定其加工設(shè)備為M3；對(duì)于工序A13，按設(shè)備選擇策略中短用時(shí)優(yōu)先原則確定其加工設(shè)備為M1；對(duì)于工序A11，按設(shè)備選擇策略中短用時(shí)優(yōu)先原則，確定其加工設(shè)備為M1，由于在先調(diào)度A13時(shí)，設(shè)備M1上將產(chǎn)生5時(shí)間段的空隙，因此，根據(jù)設(shè)備搶占策略，前移調(diào)整工序A11；對(duì)于工序A12，按設(shè)備選擇策略，將其安排至設(shè)備M3上加工；對(duì)于工序A10，按設(shè)備選擇策略，其加工設(shè)備為M4；對(duì)于工序A8，按設(shè)備選擇策略中短用時(shí)優(yōu)先原則，其加工設(shè)備為M2。第4層待調(diào)度工序調(diào)度完成，其結(jié)束時(shí)間集e4={A8/75, A9/65, A10/75, A11/60,A12/80, A13/75}。

第5層待調(diào)度工序集為O5={A3, A4, A5, A6,A7}，其偽緊前工序集P5={A9, A10, A11, A12,A13}，最早可開(kāi)始加工時(shí)刻為PE5={65, 75, 60,80,75}，其加工時(shí)間集t5={( M2, M4)/(30, 30), (M2,M3, M4)/(30, 15, 20), (M1, M2, M4)/(15, 20, 25),(M1, M3, M4)/(20, 20, 20), (M1, M2, M3,M4)/(20, 25, 25, 35) }，擬加工時(shí)間集合A_T5={30, 20, 20, 20, 25}，偽緊后工序集合為S5={ (A1), (), (A2), (), ()}，當(dāng)前待調(diào)度工序?qū)拥膫尉o后路徑長(zhǎng)度為R5={20, 0, 12.5, 0, 0 }，當(dāng)前待調(diào)度工序集各工序所對(duì)應(yīng)總路徑長(zhǎng)度為O5= PE5+A_T5+R5={A3/115, A4/95, A5/92.5, A6/100,A7/100}，對(duì)O5按其所對(duì)應(yīng)的總路徑長(zhǎng)度按降序排列并按序進(jìn)行調(diào)度，最終調(diào)度順序?yàn)閧A3, A7, A6,A4, A5}。對(duì)于工序A3，按設(shè)備選擇策略，確定其加工設(shè)備為M2；對(duì)于工序A7，按設(shè)備選擇策略中短用時(shí)優(yōu)先原則，其加工設(shè)備為M1；對(duì)于工序A6，按設(shè)備選擇策略中短用時(shí)優(yōu)先原則，確定其加工設(shè)備為M3；對(duì)于工序A4，按短用時(shí)原則及最早結(jié)束時(shí)間原則，其加工設(shè)備為M4；對(duì)于工序A5，按設(shè)備選擇策略中短用時(shí)優(yōu)先原則，確定其加工設(shè)備為M1。第5層待調(diào)度工序調(diào)度完成，其結(jié)束時(shí)間集e5={A3/105, A4/95, A5/110, A6/100,A7/95}。

第6層待調(diào)度工序集為O6={A1, A2}，其偽緊前工序集P6={A3, A5}，最早可開(kāi)始加工時(shí)刻為PE6={105, 110}，其加工時(shí)間集t6={ (M1, M2,M4)/(15, 20, 35),(M1, M2)/(10, 15) }，擬加工時(shí)間集合A_T6={20, 12.5}，偽緊后工序集合為S6={(), ()}，當(dāng)前待調(diào)度工序?qū)拥膫尉o后路徑長(zhǎng)度R6={0, 0 }，當(dāng)前待調(diào)度工序集各工序所對(duì)應(yīng)總路徑長(zhǎng)度為O6= PE6+A_T6+R6={A1/125,A2/112.5}，對(duì)O6按其所對(duì)應(yīng)的總路徑長(zhǎng)度按降序排列并按序進(jìn)行調(diào)度，最終調(diào)度順序?yàn)閧A1, A2}。對(duì)于工序A1，按設(shè)備選擇策略中短用時(shí)原則，確定其加工設(shè)備為M1；對(duì)于工序A2，按設(shè)備選擇策略中最早結(jié)束時(shí)間原則，確定其加工設(shè)備為M2。第6 層待調(diào)度工序調(diào)度完成，其結(jié)束時(shí)間集e6={A1/125, A2/125 }。

針對(duì)圖1所示產(chǎn)品工藝加工樹(shù)，經(jīng)過(guò)本文所述算法，逆序調(diào)度甘特圖如圖4所示，產(chǎn)品完工時(shí)間為125工時(shí)，經(jīng)本文所述的基于完工時(shí)間翻轉(zhuǎn)的調(diào)度方案轉(zhuǎn)換策略，正序調(diào)度方案如圖5所示。

圖4 應(yīng)用本文所提算法產(chǎn)生的逆序調(diào)度方案

圖5 應(yīng)用本文所提算法產(chǎn)生的正序調(diào)度方案

為了驗(yàn)證所求調(diào)度方案的優(yōu)越性，本文采用主流的解決柔性綜合調(diào)度問(wèn)題的算法對(duì)圖1所示產(chǎn)品進(jìn)行調(diào)度加工，其中，采用基于設(shè)備驅(qū)動(dòng)的綜合柔性調(diào)度沖突調(diào)解算法[14]所得到的調(diào)度結(jié)果如圖6所示，總加工時(shí)間為140工時(shí)；采用基于設(shè)備驅(qū)動(dòng)和實(shí)質(zhì)路徑的動(dòng)態(tài)并行綜合柔性調(diào)度算法[16]所得到的調(diào)度結(jié)果如圖7所示，總加工時(shí)間為135工時(shí)。采用基于鏈表調(diào)度的柔性綜合調(diào)度算法[15]所得到的調(diào)度結(jié)果如圖8所示，總加工時(shí)間為155工時(shí)。經(jīng)過(guò)對(duì)比可以發(fā)現(xiàn)本文所得完工時(shí)間均優(yōu)于上述算法所得結(jié)果。

圖6 基于設(shè)備驅(qū)動(dòng)的綜合柔性調(diào)度沖突調(diào)解算法調(diào)度結(jié)果甘特圖

圖7 基于設(shè)備驅(qū)動(dòng)和實(shí)質(zhì)路徑的動(dòng)態(tài)并行綜合柔性調(diào)度算法調(diào)度結(jié)果甘特圖

圖8 基于鏈表調(diào)度的柔性綜合調(diào)度算法調(diào)度結(jié)果甘特圖

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

本文針對(duì)解決復(fù)雜產(chǎn)品柔性綜合調(diào)度問(wèn)題時(shí)，正向調(diào)度導(dǎo)致調(diào)度結(jié)果不理想的問(wèn)題，提出了一種基于逆序?qū)觾?yōu)先的柔性綜合調(diào)度算法。首先提出了逆序?qū)觾?yōu)先策略，從根節(jié)點(diǎn)開(kāi)始調(diào)度，減少了多緊前工序的約束條件；其次提出了動(dòng)態(tài)擬長(zhǎng)路徑策略，優(yōu)先調(diào)度對(duì)產(chǎn)品完工時(shí)間影響大的工序；然后提出了設(shè)備選擇策略和設(shè)備搶占策略，盡量為目標(biāo)工序選擇加工用時(shí)短的工序且盡量提前加工，有利于縮短產(chǎn)品完工時(shí)間；最后提出了基于完工時(shí)間翻轉(zhuǎn)的調(diào)度方案轉(zhuǎn)換策略，將逆序調(diào)度方案轉(zhuǎn)換為正序調(diào)度方案，便于實(shí)際調(diào)度。該算法在不提高算法復(fù)雜度的前提下，提高了設(shè)備利用率，縮短了產(chǎn)品完工時(shí)間。