考慮工序序列動(dòng)態(tài)時(shí)間緊迫度的逆序貪婪綜合調(diào)度算法

曹望成 謝志強(qiáng) 裴莉榕

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

②(牡丹江師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 牡丹江 157011)

1 引言

調(diào)度優(yōu)化問(wèn)題的典型實(shí)例有制造車(chē)間中工序[1]的排序優(yōu)化問(wèn)題，網(wǎng)格計(jì)算中工作流[2–4]的費(fèi)用優(yōu)化問(wèn)題和云計(jì)算中云服務(wù)工作流應(yīng)用程序[5,6]或MapReduce任務(wù)[7]的排序優(yōu)化問(wèn)題。

智能制造已作為核心專(zhuān)項(xiàng)工程納入《中國(guó)制造2025》實(shí)施戰(zhàn)略。全國(guó)“兩會(huì)”政府工作報(bào)告[8]、《中國(guó)制造2025》和國(guó)務(wù)院關(guān)于積極推進(jìn)“互聯(lián)網(wǎng)＋”行動(dòng)的指導(dǎo)意見(jiàn)中均明確指出我國(guó)將大力發(fā)展產(chǎn)品個(gè)性化定制。消費(fèi)者對(duì)產(chǎn)品多元化及個(gè)性化需求的不斷增加，促使產(chǎn)品類(lèi)型趨向多品種、小批量。當(dāng)制造多品種、小批量產(chǎn)品，特別是單件復(fù)雜結(jié)構(gòu)產(chǎn)品時(shí)，如果按照傳統(tǒng)的先分步加工調(diào)度最后整體裝配調(diào)度的生產(chǎn)模式排產(chǎn)，必將割裂加工工序和裝配工序可并行處理的關(guān)系，降低復(fù)雜單產(chǎn)品生產(chǎn)效率。

謝志強(qiáng)等人[9–11]提出了第3類(lèi)產(chǎn)品制造調(diào)度模式：加工工序和裝配工序一同處理的綜合調(diào)度，簡(jiǎn)稱(chēng)綜合調(diào)度。綜合調(diào)度是智能制造的核心組成部分，更是實(shí)現(xiàn)中國(guó)制造2025和工業(yè)4.0[12]的重要手段，學(xué)者針對(duì)綜合調(diào)度問(wèn)題的算法優(yōu)化做了大量研究工作。針對(duì)單車(chē)間一般綜合調(diào)度問(wèn)題，謝志強(qiáng)等人[13,14]提出的考慮串行工序緊密度的擇時(shí)綜合調(diào)度算法[13]和考慮后續(xù)工序的擇時(shí)綜合調(diào)度算法[14]，存在以下缺點(diǎn)：

(1)文獻(xiàn)[13]的擇時(shí)綜合調(diào)度策略為每道工序選擇當(dāng)前完工總用時(shí)最小的方案，忽略了該道工序?qū)儆谕还ば蛐蛄械暮罄m(xù)串行工序的影響，導(dǎo)致算法出現(xiàn)局部最優(yōu)而影響產(chǎn)品調(diào)度結(jié)果的弊端；

(2)文獻(xiàn)[14]的工序排序策略與文獻(xiàn)[13]相同，在應(yīng)用擇時(shí)綜合調(diào)度策略調(diào)度工序時(shí)不能總是優(yōu)先處理對(duì)生產(chǎn)周期有較大影響的工序序列上的工序，必須回溯調(diào)整[15]，導(dǎo)致算法復(fù)雜度偏高。

綜上所述，本文提出串行工序序列的時(shí)間緊迫度(TUD)定義，應(yīng)用所提工序排序策略得到工序隊(duì)列，再結(jié)合所提逆序貪婪調(diào)度策略，以工序?yàn)閱挝唤⑵涔ば蛘{(diào)度方案，最后一道工序的調(diào)度方案即為產(chǎn)品調(diào)度方案。

2 問(wèn)題模型描述

為便于綜合調(diào)度，將加工工序和裝配工序統(tǒng)一定義為工序，加工設(shè)備和裝配設(shè)備統(tǒng)一定義為設(shè)備。復(fù)雜單產(chǎn)品進(jìn)行綜合調(diào)度時(shí)需滿(mǎn)足以下要求。(1)所有工序的加工時(shí)間已知而且與其加工順序無(wú)關(guān)，產(chǎn)品工序間的約束關(guān)系事先已知。(2)每道工序只能由一臺(tái)設(shè)備加工，某時(shí)刻每臺(tái)設(shè)備只能加工一道工序，工序一旦開(kāi)始被加工則直至加工結(jié)束不能被間斷。(3)允許工序之間等待，允許設(shè)備在工序到達(dá)之前空閑。(4)當(dāng)工序無(wú)緊前工序或其緊前工序均被加工完畢時(shí)，該工序才能被加工。(5)車(chē)間內(nèi)不存在相同設(shè)備。

個(gè)性化定制復(fù)雜結(jié)構(gòu)單產(chǎn)品(如飛行器)的加工工藝拓?fù)潢P(guān)系結(jié)構(gòu)圖呈樹(shù)狀結(jié)構(gòu)，結(jié)點(diǎn)間有向邊的方向與樹(shù)結(jié)構(gòu)中相反，稱(chēng)為產(chǎn)品加工工序樹(shù)，簡(jiǎn)稱(chēng)工序樹(shù)。為方便敘述，文中“結(jié)點(diǎn)”等價(jià)于他所表示的“工序”。

定義1 逆序工序樹(shù)。將工序樹(shù)中有向邊的方向取反之后所得到的樹(shù)型結(jié)構(gòu)。

定義2 工序序列(Process Sequence, PS)。逆序工序樹(shù)中，從根結(jié)點(diǎn)或者某叉點(diǎn)孩子結(jié)點(diǎn)a開(kāi)始，沿有向邊的方向遍歷結(jié)點(diǎn)，直到葉結(jié)點(diǎn)b為止，彼此之間具有串行偏序關(guān)系的結(jié)點(diǎn)序列，稱(chēng)為工序a到 工序b的工序序列，記為P Sab。特別地，當(dāng)工序序列只包含單個(gè)工序c時(shí)，此工序序列記為P Scc。

定義3 工序序列長(zhǎng)度。工序序列中全部結(jié)點(diǎn)所代表工序的加工時(shí)間之和。

定義4 結(jié)點(diǎn)的路徑。逆序工序樹(shù)中，從根結(jié)點(diǎn)開(kāi)始沿有向邊的方向遍歷到當(dāng)前結(jié)點(diǎn)，所得到的有序結(jié)點(diǎn)序列稱(chēng)為當(dāng)前結(jié)點(diǎn)的路徑。

定義5 結(jié)點(diǎn)的路徑長(zhǎng)度。結(jié)點(diǎn)的路徑上全部結(jié)點(diǎn)的加工時(shí)間之和。

定義6 關(guān)鍵路徑。當(dāng)前逆序工序樹(shù)中，長(zhǎng)度最長(zhǎng)的葉結(jié)點(diǎn)的路徑，若不唯一，選擇包含工序數(shù)多的路徑為關(guān)鍵路徑，若仍不唯一，任選其一。

定義7 工序隊(duì)列。用于存放初始逆序工序樹(shù)中的全部結(jié)點(diǎn)按照工序排序策略所得到的排序結(jié)果，為方便描述，隊(duì)列中的結(jié)點(diǎn)簡(jiǎn)寫(xiě)為該結(jié)點(diǎn)所代表的工序名稱(chēng)。

定義8 準(zhǔn)調(diào)度時(shí)間點(diǎn)。根據(jù)工藝約束關(guān)系，某工序的緊前工序加工結(jié)束時(shí)間點(diǎn)之后其對(duì)應(yīng)的設(shè)備上所有空閑時(shí)間段的開(kāi)始時(shí)刻都是該工序的準(zhǔn)調(diào)度時(shí)間點(diǎn)。

定義12 工序調(diào)度方案。設(shè)工序隊(duì)列中第k道工序試調(diào)度共產(chǎn)生X個(gè)準(zhǔn)調(diào)度方案，它們構(gòu)成準(zhǔn)調(diào)度方案集Pk(X) ， 從Pk(X)中選擇完工時(shí)間最小的方案為工序調(diào)度方案，記為Pk，若不唯一，則從中選擇使該道工序盡早開(kāi)始加工的方案。

定義13 產(chǎn)品調(diào)度方案。產(chǎn)品的全部n道工序試調(diào)度后產(chǎn)生的最佳調(diào)度方案，用P表示。

假設(shè)復(fù)雜單產(chǎn)品包含n道工序，需要m臺(tái)設(shè)備。Ai表 示編號(hào)為i(1≤i ≤n)的 工序，sij表 示Ai在設(shè)備Mj(1≤j ≤m) 上 的加工開(kāi)始時(shí)間，tij表示其在設(shè)備Mj上的連續(xù)加工時(shí)間。工序隊(duì)列中第1道工序?yàn)楦Y(jié)點(diǎn)工序，其加工開(kāi)始時(shí)刻為0，對(duì)應(yīng)的工序調(diào)度方案為P1。 設(shè)工序隊(duì)列中第k道工序的工序調(diào)度方案為Pk，則Pn即 為P，一般綜合調(diào)度問(wèn)題的目標(biāo)函數(shù)及約束條件描述為

3 策略設(shè)計(jì)

本文中工序、設(shè)備和方案的結(jié)構(gòu)描述如下。

(1)用鏈表存儲(chǔ)產(chǎn)品初始逆序工序樹(shù)，工序隊(duì)列存儲(chǔ)經(jīng)排序后的全部結(jié)點(diǎn)，鏈表和隊(duì)列中元素的結(jié)構(gòu)為：Node- Aid :{int} /Mid:int /T:int /L:int/F:Node*/Q:Node*[]/Tb:int /Te:int。A id是結(jié)點(diǎn)表示的工序名， M id 是工序?qū)?yīng)的設(shè)備名，T是工序在機(jī)器M id 上的加工時(shí)間，L是結(jié)點(diǎn)的路徑長(zhǎng)度，F(xiàn)是指向其緊前工序的指針，Q是指向結(jié)點(diǎn)緊后工序的指針集合， Tb 是工序?qū)嶋H開(kāi)始加工時(shí)刻，Te是工序的加工結(jié)束時(shí)刻。

(2)調(diào)度方案的設(shè)備列表中設(shè)備結(jié)構(gòu)為：M?Mid:int/NodeList:Node?/finishtime:int。

Mid 是設(shè)備名；N odeList 是設(shè)備上已試調(diào)度的工序鏈表，工序按加工開(kāi)始時(shí)刻由小到大排序；finishtime是當(dāng)前設(shè)備完工時(shí)間的最大值。

(3)調(diào)度方案結(jié)構(gòu)為：P ?Pid:int/MachineList:M ?/totaltime:int。

Pid 是方案名；M achineList是方案對(duì)應(yīng)的設(shè)備列表；t otaltime是方案中所有設(shè)備完工時(shí)間的最大值。

3.1 工序排序策略

3.1.1 工序排序策略分析

定義14 工序序列的時(shí)間緊迫度(Time Urgency Degree, TUD)。 Ai表示當(dāng)前逆序工序樹(shù)關(guān)鍵路徑上的叉點(diǎn)，Li(j)表 示以 Ai的 第j個(gè)孩子為起點(diǎn)的唯一最長(zhǎng)工序序列的長(zhǎng)度，將Li(j)減 去以 Ai為緊前工序的最長(zhǎng)工序序列的長(zhǎng)度max(Li(x)),(x= 1,2,...,j,...)的差值定義為以 Ai為 緊前工序的第j個(gè)工序序列的時(shí)間緊迫度，記為T(mén) Pi(j) =Li(j)?max(Li(x))。

將 TPi(j)大 小作為判斷以第j個(gè)工序序列為關(guān)鍵路徑的子樹(shù)的完工時(shí)間對(duì)當(dāng)前逆序工序樹(shù)完工時(shí)間影響程度的基本依據(jù)。工序序列時(shí)間緊迫度越大表明其所屬子樹(shù)對(duì)當(dāng)前逆序工序樹(shù)的完工總時(shí)間影響越大，子樹(shù)上工序?qū)υO(shè)備的需求緊迫度越大，為縮短產(chǎn)品生產(chǎn)周期，優(yōu)先調(diào)度該子樹(shù)上的工序。工序序列由若干加工時(shí)間不等的工序組成，隨著時(shí)間緊迫度值大的工序序列上的某道或某些工序加工完畢，由該工序序列剩余工序所組成的工序序列的時(shí)間緊迫度值將會(huì)發(fā)生變化，即工序序列的時(shí)間緊迫度是動(dòng)態(tài)變化的。

3.1.2 工序排序策略的算法設(shè)計(jì)

設(shè)置一個(gè)工序隊(duì)列 Queue 、一個(gè)整型變量N、兩個(gè)鏈表L ist0 和L ist1。 Q ueue存放工序排序策略的結(jié)果；N是初始逆序工序樹(shù)的層數(shù)；L ist0存儲(chǔ)初始逆序工序樹(shù)，L ist1保 存排序前的工序樹(shù)L ist0。

算法1：工序排序策略算法

(1) 初始化L ist0 ， L ist1為空；

(2) 創(chuàng)建逆序工序樹(shù)L ist0：根據(jù)輸入產(chǎn)品工序的信息、工序間偏序關(guān)系和設(shè)備信息創(chuàng)建工序結(jié)點(diǎn)，輸入工序?qū)傩灾?，插入逆序工序?shù)，屬性L(fǎng)，Tb和T e初值為0；

(3) 計(jì)算各結(jié)點(diǎn)的路徑長(zhǎng)度和N，確定關(guān)鍵路徑的長(zhǎng)度T′，更新各結(jié)點(diǎn)L屬性值：根結(jié)點(diǎn)的路徑長(zhǎng)度為根結(jié)點(diǎn)的加工時(shí)間，其余結(jié)點(diǎn)的路徑長(zhǎng)度為該結(jié)點(diǎn)的加工時(shí)間加上其緊前工序的路徑長(zhǎng)度；

(4) 初始化Q ueue；

(5) i=0；

(6) 用L ist1備 份L ist0；

(7) 判斷工序樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)是否為1，是轉(zhuǎn)步驟(8)，否則轉(zhuǎn)步驟(9)；

(8)i++， 將葉子結(jié)點(diǎn)入Q ueue，轉(zhuǎn)(11)；

(9) 調(diào)用算法2，對(duì)當(dāng)前逆序工序樹(shù)中葉子結(jié)點(diǎn)排序并依次入Q ueue；

(10)L ist0 復(fù)制L ist1，在工序樹(shù)中刪除所有葉子結(jié)點(diǎn)，轉(zhuǎn)步驟(6)；

(11)判斷入隊(duì)列結(jié)點(diǎn)的指針F是否為空，是轉(zhuǎn)步驟(13)，否則轉(zhuǎn)步驟(12)；

(12)從工序樹(shù)中刪除所有葉子結(jié)點(diǎn)，轉(zhuǎn)步驟(7)；

(13)將Q ueue中的元素逆置；

(14)退出：返回Q ueue，N。

3.1.3 當(dāng)前逆序工序樹(shù)中葉子結(jié)點(diǎn)排序算法設(shè)計(jì)

設(shè)置1個(gè)1維指針數(shù)組a[k](k=0,1,...,n ?2)，1個(gè)1維整型數(shù)組b[k](k=0,1,...,n ?2)， 堆棧Stack1和 S tack2 。排序過(guò)程中，a[k]存放指向以關(guān)鍵路徑上各叉點(diǎn)的孩子結(jié)點(diǎn)作為起點(diǎn)的唯一最長(zhǎng)工序序列的指針，b[k]存 放a[k]元素所指向的各工序序列的時(shí)間緊迫度的數(shù)值，將a[k]中 元素按b[k]中對(duì)應(yīng)數(shù)值由小到大排序；S tack1存放某工序序列所包含的全部叉點(diǎn)；S tack2 存放數(shù)組a[k]從前到后的各個(gè)元素。

算法2：當(dāng)前逆序工序樹(shù)中葉子結(jié)點(diǎn)排序算法

(1) 初 始 化a[k]，b[k] ，S tack1 ，S tack2為 空，j=0；

(2) i++ ；

(3) 確定關(guān)鍵路徑，將其作為初始逆序工序樹(shù)中時(shí)間緊迫度最大的工序序列；

(4)j++，將關(guān)鍵路徑最后一個(gè)結(jié)點(diǎn)存入Queue，qj為指向該工序序列首結(jié)點(diǎn)的指針；

(5) 判斷指針qj指向的結(jié)點(diǎn)是否為叉點(diǎn)，是轉(zhuǎn)步驟(6)，否則轉(zhuǎn)步驟(7)；

(6) 叉點(diǎn)入S tack1；

(7) 指針后移指向下一結(jié)點(diǎn)；

(8) 判斷指針?lè)駷榭?，是轉(zhuǎn)步驟(9)，否則轉(zhuǎn)步驟(5)；

(9) 從工序樹(shù)中刪除此時(shí)間緊迫度最大的工序序列中的工序；

(10)判斷S tack1是否為空，是轉(zhuǎn)步驟(16)，否則轉(zhuǎn)步驟(11)；

(11) S tack1出棧，在逆序工序樹(shù)森林中，為出棧結(jié)點(diǎn)的各緊后工序找到以其為起點(diǎn)的一個(gè)長(zhǎng)度最長(zhǎng)的工序序列，若不唯一，選擇工序數(shù)多的，用a[k++]保存指向各最長(zhǎng)工序序列的首結(jié)點(diǎn)的指針；

(12)依次計(jì)算各工序序列的時(shí)間緊迫度并存入b[k++]：為便于計(jì)算，方法是用各工序序列葉結(jié)點(diǎn)的路徑長(zhǎng)度減去初始工序樹(shù)關(guān)鍵路徑長(zhǎng)度；

(13)判斷S tack1是否為空，是轉(zhuǎn)步驟(14)，否則轉(zhuǎn)步驟(11)；

(14)將a[k]中 元素按b[k]中對(duì)應(yīng)數(shù)值由小到大排序，數(shù)值相等時(shí)按工序序列所包含的工序數(shù)由小到大排序；

(15)將a[k]元 素從前到后依次入S tack2保存，清空a[k]和b[k]；

(16)判斷S tack2是否為空，是轉(zhuǎn)步驟(18)，否則轉(zhuǎn)步驟(17)；

(17) S tack2出棧，出棧指針?biāo)腹ば蛐蛄凶鳛槠渌鶎僮訕?shù)的時(shí)間緊迫度最大的工序序列，轉(zhuǎn)步驟(4)；

(18)退出。

3.2 逆序貪婪調(diào)度策略

3.2.1 逆序貪婪調(diào)度策略分析

工序隊(duì)列中第1個(gè)元素為根結(jié)點(diǎn)，安排其在所需設(shè)備上的“0”時(shí)刻試調(diào)度形成唯一的P1。試調(diào)度工序隊(duì)列中序號(hào)為i(i ≥2)的工序時(shí)，其緊前工序已被試調(diào)度完畢，因此序號(hào)為i的工序的準(zhǔn)調(diào)度時(shí)間點(diǎn)已知，設(shè)Q T中 元素個(gè)數(shù)為X，可形成X個(gè)工序準(zhǔn)調(diào)度方案，從中選擇結(jié)束時(shí)間最小的準(zhǔn)調(diào)度方案，若不唯一，選擇使該工序最早開(kāi)始加工的方案作為Pi，依次類(lèi)推，直到序號(hào)為n的 工序試調(diào)度結(jié)束，Pn即 為P。

逆序貪婪調(diào)度的優(yōu)點(diǎn)有3個(gè)：(1)因?yàn)槭前从筛饺~的順序試調(diào)度各工序，在試調(diào)度Q ueue中序號(hào)為i(i ≥2)的工序時(shí)，約束關(guān)系被破壞的已試調(diào)度工序數(shù)量少，只需考慮序號(hào)小于等于i?1的同設(shè)備工序；(2)當(dāng)序號(hào)為i?1的 工序試調(diào)度結(jié)束，序號(hào)為i的工序的“準(zhǔn)調(diào)度時(shí)間點(diǎn)”便隨之確定，算法效率高；(3)逆序貪婪調(diào)度以單個(gè)工序?yàn)閱挝贿M(jìn)行試調(diào)度，形成Pi時(shí) 即實(shí)現(xiàn)了前i道工序的充分并行處理。

3.2.2 逆序貪婪調(diào)度策略算法設(shè)計(jì)

4 算法設(shè)計(jì)與復(fù)雜度分析

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

首先應(yīng)用算法1對(duì)全部工序進(jìn)行排序，形成工序隊(duì)列；其次對(duì)工序隊(duì)列中序號(hào)為1的根結(jié)點(diǎn)進(jìn)行調(diào)度，形成P1， 再對(duì)序號(hào)為i(2≤i ≤n)的工序應(yīng)用算法3建立Pi；最后形成甘特圖并輸出。

算法4：考慮工序序列動(dòng)態(tài)時(shí)間緊迫度的逆序貪婪綜合調(diào)度算法

(1) 應(yīng)用算法1對(duì)工序排序，得到包含n(n ≥1)個(gè)工序的Q ueue；

(2) 試調(diào)度根結(jié)點(diǎn)工序，形成P1；

(3) i=2；

(4) 判斷i≤n是否成立，是轉(zhuǎn)步驟(5)，否則轉(zhuǎn)步驟(7)；

(5) 應(yīng)用算法3建立Pi；

(6)i++，轉(zhuǎn)步驟步驟(4)；

(7) 形成甘特圖并輸出；

(8) 退出。

4.2 算法復(fù)雜度分析

假設(shè)產(chǎn)品的工序數(shù)為n， 有m臺(tái)設(shè)備，逆序工序樹(shù)的層數(shù)為N。

文中算法4是總算法，在算法4中調(diào)用1次算法1和循環(huán)n ?1次調(diào)用算法3。算法1調(diào)用了算法2。因而算法4的時(shí)間復(fù)雜度為總的時(shí)間復(fù)雜度，即算法1和循環(huán)n?1次調(diào)用算法3的時(shí)間復(fù)雜度之和。

4.2.1 算法1的時(shí)間復(fù)雜度

算法1主要包括以下4個(gè)操作：

(1)建立逆序工序樹(shù)

建立逆序工序樹(shù)是根據(jù)輸入的產(chǎn)品工序信息、工序間的偏序關(guān)系及設(shè)備信息建立鏈表的過(guò)程，為鏈表中的n個(gè)結(jié)點(diǎn)的屬性賦初值，時(shí)間復(fù)雜度為n的整數(shù)倍，時(shí)間復(fù)雜度為O(n)。

(2)計(jì)算工序路徑長(zhǎng)度和工序樹(shù)的層數(shù)

計(jì)算工序路徑長(zhǎng)度和工序樹(shù)的層數(shù)只需要對(duì)逆序工序樹(shù)由根開(kāi)始進(jìn)行1次遍歷，時(shí)間復(fù)雜度為O(n)。

(3)調(diào)用算法2

影響算法2時(shí)間復(fù)雜度的核心操作可簡(jiǎn)單地描述為以下4個(gè)步驟：

(a)獲取當(dāng)前逆序工序樹(shù)中的葉子結(jié)點(diǎn)；

(b)對(duì)步驟1中得到的葉子結(jié)點(diǎn)進(jìn)行排序，將排序后的結(jié)點(diǎn)追加到工序隊(duì)列的末端；

(c)刪除當(dāng)前逆序工序樹(shù)的葉子結(jié)點(diǎn)，得到新的當(dāng)前逆序工序樹(shù)；

(d)重復(fù)步驟(a)，步驟(b)，步驟(c)，直到所有的結(jié)點(diǎn)都進(jìn)入工序隊(duì)列。

4個(gè)步驟中對(duì)前3個(gè)步驟的循環(huán)次數(shù)為初始逆序工序樹(shù)的層數(shù)N，分析前3個(gè)步驟的時(shí)間復(fù)雜度。

步驟(a)只需要對(duì)當(dāng)前逆序工序樹(shù)進(jìn)行1次遍歷，設(shè)工序樹(shù)中結(jié)點(diǎn)個(gè)數(shù)為ni(i=1,2,...,N)，顯然有ni

步驟(b)每次進(jìn)行排序的葉子結(jié)點(diǎn)數(shù)平均為n/N，進(jìn)行排序的時(shí)間復(fù)雜度為O((n/N)2)，循環(huán)N次的時(shí)間復(fù)雜度為O(N×(n/N)2)=O(n2/N)。

步驟(c)刪除當(dāng)前逆序工序樹(shù)的葉子結(jié)點(diǎn)只需要對(duì)當(dāng)前工序樹(shù)進(jìn)行1次遍歷，循環(huán)N次總的時(shí)間復(fù)雜度與步驟(a)相同，最大為O(n2)。

因此調(diào)用算法2的時(shí)間復(fù)雜度為O(n2)。

(4)將工序隊(duì)列Q ueue中的元素逆置

借助一個(gè)堆棧即可實(shí)現(xiàn)工序隊(duì)列 Q ueue 中n個(gè)元素的逆置，時(shí)間復(fù)雜度為O(n)。

綜合分析，算法1的時(shí)間復(fù)雜度為以上4個(gè)操作的時(shí)間復(fù)雜度之和，即為O(n2)。

4.2.2 循環(huán)調(diào)用算法3的時(shí)間復(fù)雜度

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

本文提出的算法是基于理論分析，不針對(duì)任何具體實(shí)例，具有普遍意義，為了方便讀者了解該算法，下面借助產(chǎn)品調(diào)度實(shí)例進(jìn)一步說(shuō)明。設(shè)制造企業(yè)的單件訂單產(chǎn)品 A包含37道工序，需要4臺(tái)設(shè)備，產(chǎn)品的逆序工序樹(shù)如圖1所示。逆序工序樹(shù)中結(jié)點(diǎn)用長(zhǎng)方框表示，長(zhǎng)方框內(nèi)的信息是對(duì)應(yīng)工序4個(gè)屬性的簡(jiǎn)寫(xiě)：工序名的編號(hào)i|設(shè)備名的編號(hào)j|工序的加工時(shí)間|結(jié)點(diǎn)的路徑長(zhǎng)度，其中加工時(shí)間為單位時(shí)間(h)。

圖1 產(chǎn)品A的逆序工序樹(shù)

應(yīng)用文獻(xiàn)[11]的策略確定產(chǎn)品 A中工序的調(diào)度次 序 為： A37 ，A 34 ，A 36 ，A 35 ，A 32 ，A 29，A33 ，A31 ，A30 ，A25 ，A26 ，A27 ，A24 ，A21，A20 ，A28 ，A22 ，A23 ，A19 ，A16 ，A15 ，A17，A18 ，A 12 ，A 9 ，A 13 ，A 14 ，A 10 ，A 11 ，A 8，A7 ，A 6 ， A2， A4 ，A 5，A 3 ， A1。同 設(shè) 備 工 序A17 與A 18的路徑長(zhǎng)度分別為9和8，加工時(shí)間都是1 h，A 18所在的路徑為關(guān)鍵路徑，文獻(xiàn)[11] 只關(guān)注工序的路徑長(zhǎng)度，忽略了工序所在分支對(duì)產(chǎn)品周期的整體影響，優(yōu)先處理工序 A17造成調(diào)度結(jié)果欠佳，產(chǎn)品生產(chǎn)周期為26 h。

應(yīng)用文獻(xiàn)[13]的工序序列排序策略將產(chǎn)品 A的10個(gè)工序序列按路徑長(zhǎng)度由大到小排序。調(diào)度過(guò)程中，以關(guān)鍵路徑形成的初始調(diào)度方案為基礎(chǔ)，每調(diào)度1道工序形成多個(gè)準(zhǔn)調(diào)度方案，從中選擇當(dāng)前最佳調(diào)度方案，容易使算法陷入局部最優(yōu)。比如在調(diào)度工序 A4 時(shí)， A4的4個(gè)準(zhǔn)調(diào)度時(shí)間點(diǎn)分別為2，6，11，17，文獻(xiàn)[13]選擇在時(shí)間點(diǎn)11調(diào)度 A4，雖然當(dāng)前方案總用時(shí)最少，但使得設(shè)備 M3上 A1與A 7,A7與A 23之 間出現(xiàn)了空閑時(shí)間段，且 A4所在工序序列的完成時(shí)間滯后，整體調(diào)度結(jié)果欠佳，產(chǎn)品生產(chǎn)周期為32 h。應(yīng)用文獻(xiàn)[11]和文獻(xiàn)[13]，調(diào)度甘特圖如圖2和圖3所示。

圖2 使用文獻(xiàn)[11]算法調(diào)度產(chǎn)品A所得調(diào)度甘特圖

圖3 使用文獻(xiàn)[13]算法調(diào)度產(chǎn)品A所得調(diào)度甘特圖

應(yīng)用本文所提算法調(diào)度產(chǎn)品 A。應(yīng)用算法1對(duì)工序進(jìn)行排序，其中排序第1層葉子結(jié)點(diǎn)時(shí)的工序序列劃分示意圖如圖4所示，工序排序結(jié)果為：A37 ，A34 ，A35 ，A24 ，A32 ，A31 ，A11 ，A21，A28，A 2。

圖4 排序第1層葉子結(jié)點(diǎn)時(shí)的工序序列劃分示意圖

全部工序排序后，將 Queue中的元素逆置，Queue 中 從 前 到 后 為： A1 ，A 3 ，A 7 ， A4 ，A 13，A6 ，A 9，A 18，A 12 ， A 15，A 23 ，A 5，A 17 ，A 8，A20 ，A27 ，A10 ，A22 ，A14 ，A25 ，A33 ，A16，A26 ，A 19 ，A 30 ，A 29 ，A 36 ， A2 ，A 28 ，A 21，A11 ，A31 ，A32 ，A24 ，A35 ，A34 ，A37。Queue 出隊(duì)列，試調(diào)度工序，只有試調(diào)度 A4，A12， A 16 ，A 24 建立P4，P9，P22，P34的過(guò)程中涉及準(zhǔn)調(diào)度時(shí)間點(diǎn)的選取。 A4的準(zhǔn)調(diào)度時(shí)間點(diǎn)為2和6，選擇2； A12的準(zhǔn)調(diào)度時(shí)間點(diǎn)為5和8，選擇5；A16 的準(zhǔn)調(diào)度時(shí)間點(diǎn)為8, 11和15，選擇8；A 24的準(zhǔn)調(diào)度時(shí)間點(diǎn)為14和19，選擇19。4次試調(diào)度過(guò)程如圖5所示，灰色工序?qū)?yīng)的方案作為工序調(diào)度方案。本文算法調(diào)度產(chǎn)品 A的調(diào)度甘特圖如圖6所示，生產(chǎn)周期為24 h。

圖5 4次試調(diào)度工序的過(guò)程示意圖

圖6 使用本文算法調(diào)度產(chǎn)品A所得調(diào)度甘特圖

應(yīng)用文獻(xiàn)[14]和文獻(xiàn)[15]算法調(diào)度產(chǎn)品 A，調(diào)度結(jié)果與本文算法相同，產(chǎn)品生產(chǎn)周期為24 h，但因它們的工序排序策略與文獻(xiàn)[13]相同，不能優(yōu)先調(diào)度時(shí)間緊迫度值大的工序序列上的工序，所以算法復(fù)雜度高于本文。

對(duì)比發(fā)現(xiàn)，應(yīng)用本文算法調(diào)度產(chǎn)品 A 時(shí)，不但可以縮短產(chǎn)品的生產(chǎn)周期而且效率較高。

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

本文主要結(jié)論如下：

(1)工序排序策略，提出工序序列時(shí)間緊迫度的定義，將同層工序按所屬工序序列時(shí)間緊迫度值由大到小的順序確定調(diào)度順序，優(yōu)化了調(diào)度結(jié)果；克服了文獻(xiàn)[13]的排序策略導(dǎo)致調(diào)度結(jié)果易于陷入局部最優(yōu)的缺點(diǎn)；

(2)逆序貪婪調(diào)度策略，每道工序只需考慮在空閑的準(zhǔn)調(diào)度時(shí)間點(diǎn)調(diào)度，算法復(fù)雜度不超過(guò)二次多項(xiàng)式。

綜上所述，本文算法優(yōu)于目前典型的一般綜合調(diào)度算法，工序序列時(shí)間緊迫度概念的提出為進(jìn)一步深入研究綜合調(diào)度問(wèn)題拓展了思路，具有一定的理論和實(shí)際意義。該算法注重縮短橫向同層可調(diào)度工序并行調(diào)度結(jié)束時(shí)間的同時(shí)，更強(qiáng)調(diào)以動(dòng)態(tài)時(shí)間緊迫度值大的工序序列為主的縱向調(diào)度優(yōu)化思想，優(yōu)化了綜合調(diào)度結(jié)果。