周 偉 謝志強(qiáng)

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

1 引言

調(diào)度問題作為制造系統(tǒng)的關(guān)鍵環(huán)節(jié)，一直受到學(xué)術(shù)界的廣泛關(guān)注。高效的調(diào)度系統(tǒng)既可以降低產(chǎn)品制造的各項(xiàng)成本，又可以提高企業(yè)的經(jīng)濟(jì)效益、社會(huì)效益等。隨著計(jì)算機(jī)技術(shù)的發(fā)展和社會(huì)需求的變化，制造行業(yè)的產(chǎn)品調(diào)度也隨之改變[1–15]。例如，王卓昊等人[1]構(gòu)建了一套分布式抽取、轉(zhuǎn)換再加載的任務(wù)調(diào)度框架，優(yōu)化了復(fù)雜任務(wù)的調(diào)度執(zhí)行時(shí)間；胡致遠(yuǎn)等人[2]提出了非工作保持型的多節(jié)點(diǎn)聯(lián)合調(diào)度模型，保障了業(yè)務(wù)確定的可達(dá)性需求；王萍等人[3]針對動(dòng)態(tài)負(fù)載環(huán)境下的高效分布式資源分配問題，提出了一種預(yù)留—重用聯(lián)合的Q學(xué)習(xí)型半持續(xù)調(diào)度算法等。但是產(chǎn)品制造的多樣化和人們需求的個(gè)性化，使得小批量、復(fù)雜工藝的產(chǎn)品調(diào)度問題日益突出。不同于傳統(tǒng)工業(yè)中的流水調(diào)度(flow-shop)和車間調(diào)度(job-shop)問題，謝志強(qiáng)[16]提出了第3類產(chǎn)品制造調(diào)度模式，即在具有樹形復(fù)雜結(jié)構(gòu)的多品種、小批量產(chǎn)品中，將產(chǎn)品加工和裝配進(jìn)行同步處理的綜合調(diào)度，并針對綜合調(diào)度開展了深入研究，已取得了較豐富的成果[17–26]。

例如，文獻(xiàn)[17]針對柔性集成調(diào)度問題，提出了基于網(wǎng)絡(luò)設(shè)備協(xié)作的改進(jìn)人工蜂群算法；為解決綜合調(diào)度智能優(yōu)化算法中，編碼方式遺漏最優(yōu)解的問題，文獻(xiàn)[18]提出了動(dòng)態(tài)優(yōu)先級約束表的編碼方法，保證了初始種群個(gè)體的可行性和完備性；文獻(xiàn)[19]為解決資源服務(wù)器狀態(tài)動(dòng)態(tài)變化對工作流的調(diào)度問題，基于時(shí)間窗曲線模型和平均利用率模型提出了考慮資源狀態(tài)動(dòng)態(tài)反饋的算法等。

但是，在以“工序”為優(yōu)化對象的研究中，如果算法以長路徑為研究主線，那么當(dāng)相同設(shè)備出現(xiàn)短路徑上葉節(jié)點(diǎn)工序較早開始加工的情況時(shí)，首次適用調(diào)度策略就會(huì)失效，會(huì)在工序之間產(chǎn)生不可利用的空閑時(shí)間；在以后續(xù)工序排序?yàn)橹骶€的算法中，加工工序較多的設(shè)備上會(huì)形成工序序列間的眾多加工空隙；在以設(shè)備驅(qū)動(dòng)并行為主線的算法中，當(dāng)后續(xù)工序路徑長度相同時(shí)，如果兩個(gè)工序都是葉節(jié)點(diǎn)工序，那么短用時(shí)策略就會(huì)失效，縱向優(yōu)化調(diào)度效果不佳，加工工序較多的設(shè)備上也會(huì)出現(xiàn)很多空閑時(shí)間段。

近年來綜合調(diào)度中以“設(shè)備”為優(yōu)化對象的相關(guān)研究較少，只有文獻(xiàn)[24]的關(guān)鍵設(shè)備工序緊湊調(diào)度算法和文獻(xiàn)[25]的關(guān)鍵設(shè)備工序緊湊的動(dòng)態(tài)調(diào)度算法。二者的相同之處是：均將加工用時(shí)最長的設(shè)備定義為關(guān)鍵設(shè)備，然后在關(guān)鍵設(shè)備上應(yīng)用擬關(guān)鍵路徑方法，最后應(yīng)用最佳適應(yīng)方法在設(shè)備空閑時(shí)間段插入獨(dú)立工序。不同之處在于：在文獻(xiàn)[24]的算法中關(guān)鍵設(shè)備和關(guān)鍵路徑是固定的，而文獻(xiàn)[25]的算法中關(guān)鍵設(shè)備和關(guān)鍵路徑是根據(jù)部分工序加工完成情況動(dòng)態(tài)調(diào)整的。但是，當(dāng)關(guān)鍵設(shè)備上加工工序的前序工序不是獨(dú)立工序時(shí)，兩種算法都會(huì)在關(guān)鍵設(shè)備上產(chǎn)生很多無法利用的空閑時(shí)間段，進(jìn)而拉長了串行工序之間的空隙。

針對目前多品種、小批量復(fù)雜產(chǎn)品綜合調(diào)度中，加工工序較多的設(shè)備在調(diào)度時(shí)出現(xiàn)較多空閑段的問題，本文提出了考慮多工序設(shè)備權(quán)重的資源協(xié)同算法。本文的主要貢獻(xiàn)有：

(1)在綜合調(diào)度領(lǐng)域中拓展了特殊設(shè)備的定義范疇：在柔性設(shè)備、批處理設(shè)備、關(guān)鍵設(shè)備、加工中心之外，定義了多工序設(shè)備；

(2)算法全面考慮了綜合調(diào)度領(lǐng)域中的相關(guān)因素，如復(fù)雜產(chǎn)品工藝樹結(jié)構(gòu)、工序自身屬性、工序之間的約束關(guān)系、設(shè)備加工情況等，在此基礎(chǔ)上，提出了權(quán)重值策略和最佳調(diào)度時(shí)刻策略；

(3)算法以“多工序設(shè)備”作為優(yōu)化對象，優(yōu)先調(diào)度多工序設(shè)備上競爭相對緊張的工序，既提高了多工序設(shè)備上工序連續(xù)加工的力度，又聯(lián)動(dòng)其緊后工序及后續(xù)工序的盡早開始加工，有效地減少了產(chǎn)品的加工時(shí)間，進(jìn)而優(yōu)化了綜合調(diào)度的整體效果。

2 問題及建模

假設(shè)綜合調(diào)度系統(tǒng)中有m臺(tái)加工設(shè)備，共需加工完成復(fù)雜產(chǎn)品的n道工序，每個(gè)工序自身加工用時(shí)已知，記為di，具體要求如下：

(1)每個(gè)工序具有工序序號、對應(yīng)加工設(shè)備序號和自身加工用時(shí)的屬性；

(2)設(shè)備加工工序時(shí)，具有時(shí)間確定性和加工連續(xù)性；

(3)除了葉節(jié)點(diǎn)工序，其他任何一道工序可以被加工的充分必要條件是其所有緊前工序均加工完畢；

(4)所有設(shè)備上最后一道工序加工完成的時(shí)間為產(chǎn)品的總加工用時(shí)。

綜合調(diào)度的優(yōu)化目標(biāo)為合理調(diào)度各個(gè)設(shè)備上的工序，最小化復(fù)雜產(chǎn)品最大加工用時(shí)；約束條件為除了葉節(jié)點(diǎn)工序具有緊后工序、根節(jié)點(diǎn)工序具有緊前工序以外，其他所有節(jié)點(diǎn)工序均存在緊前緊后工序約束關(guān)系。

建立問題模型如下：

優(yōu)化目標(biāo)

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

3.1 相關(guān)定義

定義1 工序優(yōu)先級。根據(jù)“減少并行工序加工時(shí)間”的原則，文獻(xiàn)[26]針對復(fù)雜產(chǎn)品工藝樹中的加工工序提出了工序優(yōu)先級問題，即將工序調(diào)度的優(yōu)先順序定義為工序的優(yōu)先級[26,27]。假設(shè)產(chǎn)品加工工藝樹有n層，則將根節(jié)點(diǎn)工序的優(yōu)先級定義為1；根節(jié)點(diǎn)工序的所有后裔節(jié)點(diǎn)工序的優(yōu)先級定義為2，同層工序節(jié)點(diǎn)作為兄弟節(jié)點(diǎn)；以此類推，直到第n層的所有節(jié)點(diǎn)的優(yōu)先級定義為n。定義根節(jié)點(diǎn)工序的優(yōu)先級最低，第n層上工序的優(yōu)先級最高。

定義2 設(shè)備優(yōu)先級。假設(shè)綜合調(diào)度系統(tǒng)有m臺(tái)加工設(shè)備序列{M1,M2,...,Mm}，定義加工工序數(shù)量最多的設(shè)備優(yōu)先級最高，加工工序數(shù)量次多的設(shè)備優(yōu)先級次之，以此類推，加工工序數(shù)量最少的設(shè)備優(yōu)先級最低為1，允許存在相同的設(shè)備優(yōu)先級。

定義3 約束度。以某一工序?yàn)橹行?，將與其直接相鄰的所有具有緊前緊后約束關(guān)系的工序數(shù)量之和，定義為此工序的約束度。

定義4 權(quán)重值。將工序的層優(yōu)先級、設(shè)備優(yōu)先級和工序約束度的數(shù)值之和定義為此工序的權(quán)重值。

定義5 最佳調(diào)度時(shí)刻。對于某一工序而言，將其緊前工序(組)加工結(jié)束的時(shí)刻定義為此工序的最佳調(diào)度時(shí)刻。

3.2 算法描述

現(xiàn)有綜合調(diào)度算法的調(diào)度過程多以復(fù)雜產(chǎn)品工藝樹中工序的路徑、是否為葉節(jié)點(diǎn)工序以及工序的加工用時(shí)等因素為考量，較少考慮調(diào)度過程中設(shè)備的制約條件。與其他綜合調(diào)度算法不同，本文充分考慮了多工序設(shè)備的優(yōu)化對綜合調(diào)度總體優(yōu)化效果的重要作用，設(shè)計(jì)了層優(yōu)先級和權(quán)重值的排序策略以及最佳調(diào)度時(shí)刻的調(diào)整策略。

層優(yōu)先級策略是綜合調(diào)度中的經(jīng)典策略，主要作用是通過縮短并行工序加工時(shí)間的方式優(yōu)化調(diào)度效果。優(yōu)勢主要體現(xiàn)在：(1)約束力強(qiáng)的緊前工序具有優(yōu)先調(diào)度的先決條件；(2)以“層”為單位，優(yōu)先調(diào)度的加工工序可以在不同的設(shè)備上同時(shí)加工。

權(quán)重值策略是算法的核心策略，通過提高多工序設(shè)備的利用率帶動(dòng)綜合調(diào)度設(shè)備總體利用率的提高。優(yōu)勢主要體現(xiàn)在：(1)遵循了綜合調(diào)度中“設(shè)備忙”的原則；(2)首次將工序的緊前緊后約束度作為考量因素，提高了多工序設(shè)備上工序的銜接度，促進(jìn)綜合調(diào)度效果的總體優(yōu)化。

最佳調(diào)度時(shí)刻調(diào)整策略，有效地提高了設(shè)備并行處理的力度。優(yōu)勢主要體現(xiàn)在：(1)對于約束度不強(qiáng)的葉節(jié)點(diǎn)工序，具有在對應(yīng)設(shè)備上最早開始加工的優(yōu)勢；(2)對于約束度較強(qiáng)的非葉節(jié)點(diǎn)工序，減少了其在設(shè)備間的串行空隙。

算法具體描述如下：

步驟1 根據(jù)復(fù)雜產(chǎn)品工藝樹的結(jié)構(gòu)特征，確定工藝樹的層序，計(jì)算各個(gè)工序的層優(yōu)先級；

步驟2 根據(jù)復(fù)雜產(chǎn)品工藝樹的屬性特征，計(jì)算各個(gè)工序的設(shè)備優(yōu)先級、約束度和權(quán)重值；

步驟3 確定層優(yōu)先級最高的工序；

步驟4 判斷層優(yōu)先級最高的工序是否唯一，如果是，則直接調(diào)度，如果否，則轉(zhuǎn)步驟5；

步驟5 判斷工序的權(quán)重值是否相同，如果是，則轉(zhuǎn)步驟6，如果否，則按照權(quán)重值由大到小依次調(diào)度工序；

步驟6 根據(jù)最佳調(diào)度時(shí)刻調(diào)整策略，調(diào)整工序在對應(yīng)設(shè)備上的最佳調(diào)度時(shí)刻；直到根節(jié)點(diǎn)工序調(diào)度結(jié)束，算法框架流程圖如圖1所示。

圖1 算法框架流程圖

3.3 數(shù)據(jù)標(biāo)準(zhǔn)化處理

復(fù)雜產(chǎn)品工藝樹結(jié)構(gòu)可以通過虛擬根節(jié)點(diǎn)的方式構(gòu)造更加復(fù)雜的復(fù)雜產(chǎn)品，因此產(chǎn)品的加工規(guī)模和復(fù)雜程度不盡統(tǒng)一；同時(shí)，由于制造系統(tǒng)中相關(guān)設(shè)備的情況也不盡相同，所以在采用本文算法進(jìn)行權(quán)重值計(jì)算前，需要將工序的層優(yōu)先級、設(shè)備優(yōu)先級和工序約束度的具體數(shù)值進(jìn)行標(biāo)準(zhǔn)化處理，目的是使不同量綱級別的數(shù)據(jù)經(jīng)過計(jì)算后得到的結(jié)果不會(huì)出現(xiàn)偏差。

本文選取在數(shù)據(jù)處理中常用的Z-score標(biāo)準(zhǔn)化方法[28]，如式(4)所示

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

假設(shè)復(fù)雜產(chǎn)品的加工工序數(shù)、加工設(shè)備數(shù)和每道工序的自身加工用時(shí)等信息均已知，分別設(shè)為n,m,di，則本文算法復(fù)雜度分析如下：

4 實(shí)例分析

本文算法具有普適性，對其他算例亦有較好的調(diào)度效果。為便于讀者理解本文算法，現(xiàn)舉例說明，如圖2所示，假設(shè)復(fù)雜產(chǎn)品A加工工藝樹由12道工序組成，分別在4臺(tái)設(shè)備上進(jìn)行加工。

圖2 復(fù)雜產(chǎn)品A加工工藝樹

根據(jù)本文算法，首先計(jì)算各設(shè)備優(yōu)先級，如表2所示。其次分別計(jì)算各個(gè)工序?qū)?yīng)的層優(yōu)先級、約束度、權(quán)重值和最佳調(diào)度時(shí)刻，如表3所示。

表1 考慮多工序設(shè)備權(quán)重的資源協(xié)同綜合調(diào)度算法

表2 復(fù)雜產(chǎn)品A設(shè)備優(yōu)先級統(tǒng)計(jì)

表3 復(fù)雜產(chǎn)品A工序權(quán)重值統(tǒng)計(jì)

調(diào)度過程如表4所示，調(diào)度甘特圖如圖3所示，總加工用時(shí)為30工時(shí)。

圖3 復(fù)雜產(chǎn)品A加工甘特圖30工時(shí)

表4 復(fù)雜產(chǎn)品A調(diào)度過程

5 算法對比分析

5.1 以工序?yàn)檠芯繉ο蟮乃惴▽Ρ确治?/h3>

為闡述本文算法的更優(yōu)性，現(xiàn)選擇文獻(xiàn)[20]中的復(fù)雜產(chǎn)品B作為實(shí)例進(jìn)行分析闡述，如圖4所示。再選擇文獻(xiàn)[20]緊密銜接工序組聯(lián)動(dòng)的算法、文獻(xiàn)[21]考慮串行工序緊密度的擇時(shí)算法與本文算法進(jìn)行對比分析。

圖4 復(fù)雜產(chǎn)品B加工工藝樹

針對復(fù)雜產(chǎn)品B加工工藝圖，采用本文算法工序調(diào)度順序?yàn)閧A3, A2, A1, A4, A10, A5, A11, A12,A6, A18, A7, A8, A13, A20, A19, A21, A9, A10,A15, A22, A24, A23, A7, A25, A17, A26, A27}，調(diào)度甘特圖如圖5所示，總加工用時(shí)為27工時(shí)。

采用文獻(xiàn)[20]緊密銜接工序組聯(lián)動(dòng)的算法，工序的調(diào)度順序?yàn)閧A10, A12, A1, A2, A3, A4, A5, A7,A6, A8, A9, A11, A13, A14, A15, A18, A19, A20, A21,A22, A23, A24, A25, A16, A17, A26, A27}，調(diào)度甘特圖如圖6所示，總加工用時(shí)為28工時(shí)。

采用文獻(xiàn)[21]考慮串行工序緊密度的擇時(shí)算法，初始調(diào)度方案為{A27, A26, A17, A16, A15,A9, A8, A6, A4, A3, A1}，在此基礎(chǔ)上按照{(diào)A25,A23, A21, A20, A18, A14, A13, A11, A10, A24,A22, A7, A2, A12, A19, A5}的順序進(jìn)行調(diào)整。因算法采用逆序調(diào)度，在保證各工序約束條件的前提下，逆序調(diào)整調(diào)度甘特圖如圖7所示，總加工用時(shí)為31工時(shí)。

5.2 算法結(jié)果對比分析

針對復(fù)雜產(chǎn)品B加工工藝圖，本文算法的總加工用時(shí)最少，之所以本文算法更優(yōu)，主要是因?yàn)椋?/p>

文獻(xiàn)[20]的算法優(yōu)先調(diào)度“緊密銜接工序(組)中的工序”，忽略了約束度不高的工序(組)的相對位置對調(diào)度結(jié)果的影響，因而在工序串行調(diào)度過程中產(chǎn)生了空閑時(shí)間段。例如在圖6中，設(shè)備M2在t=17～t=24時(shí)刻出現(xiàn)較長時(shí)間的空閑，設(shè)備M2在整個(gè)加工過程中共計(jì)有10個(gè)工時(shí)的空閑，多于圖5中設(shè)備M2的7個(gè)工時(shí)的空閑。

文獻(xiàn)[21]算法在用擇時(shí)調(diào)度策略確定工序加工開始時(shí)間點(diǎn)時(shí)，沒有充分考慮到多工序設(shè)備的加工和利用情況，因而影響了整體調(diào)度效果。例如在圖7中，設(shè)備M2在t=0～t=2, t=5～t=7和t=14～t=18,t=19～t=24時(shí)刻一直處于空閑狀態(tài)；而在圖5中，工序A2, A3, A8, A24, A25比圖7中的開始加工時(shí)間分別提前了7個(gè)工時(shí)、8個(gè)工時(shí)、8個(gè)工時(shí)、10個(gè)工時(shí)和6個(gè)工時(shí)，不僅提高了多工序設(shè)備M2上工序連續(xù)加工的緊密度，而且設(shè)備利用率也提高了14.6%。

圖5 本文算法調(diào)度復(fù)雜產(chǎn)品B工藝樹甘特圖27工時(shí)

圖6 文獻(xiàn)[20]算法調(diào)度復(fù)雜產(chǎn)品B甘特圖28工時(shí)

圖7 文獻(xiàn)[21]算法調(diào)度復(fù)雜產(chǎn)品B逆序甘特圖31工時(shí)

5.3 以設(shè)備為研究對象的算法對比分析

下面再將本文算法分別與同類代表性論文—文獻(xiàn)[24]和文獻(xiàn)[25]的算法進(jìn)行對比分析，結(jié)果同樣證明了本文算法的更優(yōu)性。

(1)與文獻(xiàn)[24]關(guān)鍵設(shè)備工序緊湊的算法對比。在文獻(xiàn)[24]中，將加工工序用時(shí)最長的設(shè)備定義為關(guān)鍵設(shè)備，在本文中，將加工工序數(shù)量最多的設(shè)備定義為多工序設(shè)備。那么，本文有必要針對多工序設(shè)備上工序(組)總加工用時(shí)(下述簡稱前者)與關(guān)鍵設(shè)備上工序(組)總加工用時(shí)(下述簡稱后者)的3種不同情況進(jìn)行詳細(xì)對比分析。

(2)前者小于后者的對比分析。在復(fù)雜產(chǎn)品B加工工藝樹中，本文算法中的多工序設(shè)備為M2，設(shè)備M2對應(yīng)加工的8個(gè)工序(組)為{A2, A3, A8, A11,A12, A21, A24, A25}，總用時(shí)15工時(shí)；文獻(xiàn)[24]算法中關(guān)鍵設(shè)備為設(shè)備M1，對應(yīng)加工的6個(gè)工序(組)為{A1, A6, A13, A20, A22, A27}，總用時(shí)16工時(shí)。

采用文獻(xiàn)[24]的算法，工序調(diào)度順序?yàn)閧A1,A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12,A13, A14, A15, A16, A17, A18, A20, A19, A21,A22, A23, A24, A25, A26, A27}，調(diào)度甘特如圖8所示，總加工用時(shí)41工時(shí)。

圖8 文獻(xiàn)[24]算法調(diào)度復(fù)雜產(chǎn)品B甘特圖41工時(shí)

當(dāng)多工序設(shè)備上工序(組)總加工用時(shí)小于關(guān)鍵設(shè)備上工序(組)總加工用時(shí)，本文算法更優(yōu)。

對比分析甘特圖圖5和圖8：在圖5中，設(shè)備M4上的總加工用時(shí)為18工時(shí)、設(shè)備M3上的總加工用時(shí)為25工時(shí)、多工序設(shè)備M2上的總加工用時(shí)為22工時(shí)、設(shè)備M1上的總加工用時(shí)為27工時(shí)；在圖8中，設(shè)備M4上的總加工用時(shí)為21工時(shí)、設(shè)備M3上的總加工用時(shí)為39工時(shí)、設(shè)備M2上的總加工用時(shí)為38工時(shí)、關(guān)鍵設(shè)備M1上的總加工用時(shí)為41工時(shí)。在圖8中設(shè)備M2上在加工過程中出現(xiàn)了共計(jì)23個(gè)工時(shí)的空閑，明顯多于圖5中的7個(gè)工時(shí)的空閑時(shí)間段。設(shè)備利用率對比分析如表5所示，本文算法設(shè)備總體利用率相對提高率提高了20.6%。

表5 前者小于后者時(shí)兩種算法的設(shè)備利用率對比分析

(3)前者大于等于后者的對比分析。由關(guān)鍵設(shè)備的判定條件可知，當(dāng)前者大于等于后者時(shí)，對于同一復(fù)雜產(chǎn)品工藝樹而言，多工序設(shè)備和關(guān)鍵設(shè)備為同一個(gè)設(shè)備。下面，本文以圖9所示的復(fù)雜產(chǎn)品C工藝樹為例進(jìn)行對比分析。

圖9 復(fù)雜產(chǎn)品C加工工藝樹

在復(fù)雜產(chǎn)品C加工工藝圖中，因設(shè)備M3加工工序數(shù)量最多：6個(gè)，所以多工序設(shè)備為M3，又因設(shè)備M3上加工工序(組)的加工用時(shí)最長：160工時(shí)，所以在本例中，設(shè)備M3既是多工序設(shè)備又是關(guān)鍵設(shè)備。

采用本文算法工序調(diào)度順序?yàn)閧A19, A18,A17, A11, A13, A14, A12, A15, A16, A8, A5, A6,A9, A10, A7, A3, A4, A2, A1}，調(diào)度甘特圖如圖10所示，總加工用時(shí)為200工時(shí)。

圖10 本文算法調(diào)度復(fù)雜產(chǎn)品C甘特圖200工時(shí)

采用文獻(xiàn)[24]的算法工序調(diào)度順序?yàn)閧A19,A17, A11, A12, A5, A6, A2, A18, A14, A15, A8,A13, A7, A9, A3, A16, A10, A4, A1}，調(diào)度甘特圖如圖11所示，總用時(shí)240工時(shí)。

圖11 文獻(xiàn)[24]算法調(diào)度復(fù)雜產(chǎn)品C甘特圖240工時(shí)

當(dāng)多工序設(shè)備上工序(組)總加工用時(shí)大于等于關(guān)鍵設(shè)備上工序(組)總加工用時(shí)，本文算法更優(yōu)。

對比分析調(diào)度甘特圖圖10和圖11：在圖10中，多工序設(shè)備M3的總加工用時(shí)為175工時(shí)，工序A13作為葉節(jié)點(diǎn)工序使用本文算法的最佳調(diào)度時(shí)刻調(diào)整策略，在t=20時(shí)刻開始加工，因此其緊后工序A7較圖11中的開始加工時(shí)刻提前了90個(gè)工時(shí)；同時(shí)設(shè)備M3也僅僅在t=135時(shí)刻到t=150時(shí)刻之間出現(xiàn)了15個(gè)工時(shí)的空閑時(shí)間段。在圖11中，關(guān)鍵設(shè)備M3的總加工用時(shí)為215工時(shí)，設(shè)備M3在t=135時(shí)刻到t=190時(shí)刻的55個(gè)工時(shí)內(nèi)，一直處在空閑狀態(tài)。而在設(shè)備利用率方面，文獻(xiàn)[24]設(shè)備總體利用率為59.6%，本文算法設(shè)備總體利用率為72.4%，相對提高了12.8%。

(4)與文獻(xiàn)[25]關(guān)鍵設(shè)備工序緊湊的動(dòng)態(tài)調(diào)度算法對比。文獻(xiàn)[25]算法的主要特點(diǎn)是“動(dòng)態(tài)”，即在“擬關(guān)鍵路徑+最佳適應(yīng)調(diào)度時(shí)刻”的基礎(chǔ)上，將最先確定的關(guān)鍵產(chǎn)品部分加工后，再根據(jù)設(shè)備上對應(yīng)工序總加工用時(shí)的長短動(dòng)態(tài)調(diào)整關(guān)鍵產(chǎn)品和關(guān)鍵設(shè)備。下面，本文以文獻(xiàn)[25]中的復(fù)雜產(chǎn)品A和B實(shí)例為例，如圖12所示，與本文算法進(jìn)行對比分析。結(jié)果同樣表明，本文算法更優(yōu)。

圖12 文獻(xiàn)[25]原文實(shí)例復(fù)雜產(chǎn)品A和B加工工藝樹

采用本文算法，工序調(diào)度順序?yàn)閧A1, A4, A3,B1, A2, A5, B2, B3, A6, A7, B4, B5, A9, A8,A10, B6, B7, B8, A11}，調(diào)度甘特圖如圖13所示，總加工用時(shí)為235工時(shí)。

由文獻(xiàn)[25]原文可知，在t=55時(shí)刻動(dòng)態(tài)調(diào)整關(guān)鍵設(shè)備，在t=130時(shí)刻動(dòng)態(tài)調(diào)整關(guān)鍵產(chǎn)品，在t=55時(shí)刻調(diào)度效果達(dá)到最佳，調(diào)度甘特圖如圖14所示，總加工用時(shí)為255工時(shí)。

對比分析調(diào)度甘特圖13和圖14：在圖13中，多工序設(shè)備M2上的總加工用時(shí)為235工時(shí)，在t=0時(shí)刻，設(shè)備M1、設(shè)備M2和設(shè)備M3均開始加工工序；在圖14中關(guān)鍵設(shè)備M2上的總加工用時(shí)為255工時(shí)，設(shè)備M1從t=0時(shí)刻t=20時(shí)刻處在空閑狀態(tài)。本文算法中葉節(jié)點(diǎn)工序B2在圖13中在t=0時(shí)刻開始加工，那么與工序B2具有緊后約束關(guān)系的工序(組)也較早開始加工，例如工序B3在圖13中較在圖14中提前了100個(gè)工時(shí)，所以本文算法通過優(yōu)先調(diào)度多工序設(shè)備上的葉節(jié)點(diǎn)工序，聯(lián)動(dòng)了其具有較高緊后約束關(guān)系的工序(組)也實(shí)現(xiàn)了較早開始加工，進(jìn)而減少了復(fù)雜產(chǎn)品的總加工用時(shí)。設(shè)備利用率對比分析如表6所示，本文算法較文獻(xiàn)[25]算法的設(shè)備總體利用率相對提高了10.3%。

表6 本文算法和文獻(xiàn)[25]算法設(shè)備利用率對比分析

圖13 本文算法加工文獻(xiàn)[25]原文實(shí)例甘特圖235工時(shí)

圖14 文獻(xiàn)[25]在t=55時(shí)刻加工甘特圖255工時(shí)

5.4 本文算法、文獻(xiàn)[24]算法和文獻(xiàn)[25]算法結(jié)果對比分析

通過與文獻(xiàn)[24]和文獻(xiàn)[25]的算法對比分析，之所以本文算法更優(yōu)，主要是因?yàn)椋?/p>

(1)本文算法采用了“層優(yōu)先策略”縱橫優(yōu)化的思想，而文獻(xiàn)[24]和文獻(xiàn)[25]的算法均采用的“擬關(guān)鍵路徑”策略是縱向優(yōu)化的思想，從而拉長了串行工序的加工空隙。例如在圖11中，設(shè)備M1在t=0～t=20時(shí)刻、t=40～t=110時(shí)刻，設(shè)備M2在t=20～t=85時(shí)刻，設(shè)備M3在t=135～t=190時(shí)刻，設(shè)備M4在t=120～t=215時(shí)刻均出現(xiàn)了連續(xù)且大段的空閑時(shí)間；在圖14中，工序B2在t=100時(shí)刻才開始加工，比在圖13的開始加工時(shí)刻延遲了100個(gè)工時(shí)。

(2)本文算法采用了“權(quán)重值策略”，在優(yōu)先考慮多工序設(shè)備加工情況的基礎(chǔ)上，又全面考慮了加工工序間的各種約束關(guān)系。而文獻(xiàn)[25]的算法中只考慮了“僅具有唯一緊前、緊后關(guān)系的相關(guān)工序和獨(dú)立工序”，也就是僅考慮了約束度小于等于2的節(jié)點(diǎn)工序情況，這必然會(huì)影響約束性強(qiáng)的工序，導(dǎo)致工序間的緊密銜接性較弱。例如在圖13中，因工序B2的優(yōu)先調(diào)度，既利用了設(shè)備的空隙又使其緊后工序B3較早開始調(diào)度，從而聯(lián)動(dòng)了工序B3的后續(xù)工序(組)也得到了較早的調(diào)度，有效地減少了設(shè)備上的加工空隙，縮短了綜合調(diào)度總體加工用時(shí)。

(3)本文算法采用了“最佳調(diào)度時(shí)刻調(diào)整策略”，首先保證了工序(組)緊前關(guān)系的約束條件，而在設(shè)備空閑時(shí)間段查找并插入相關(guān)工序則是完全利用設(shè)備的調(diào)度空隙，充分彌補(bǔ)了文獻(xiàn)[24]和文獻(xiàn)[25]的算法因加工工序拉伸或者后移而產(chǎn)生的串行工序間的空隙。文獻(xiàn)[24]算法采用的“最佳適應(yīng)調(diào)度”策略，當(dāng)層優(yōu)先級較低的葉節(jié)點(diǎn)工序不是“獨(dú)立工序”時(shí)，“工序緊湊”的策略則會(huì)失效。例如圖11中設(shè)備M3上的葉節(jié)點(diǎn)工序A13，因其不是獨(dú)立工序，不能調(diào)整到最佳時(shí)刻開始加工，因而影響了綜合調(diào)度的整體效果。

6 結(jié)論

本文在綜合調(diào)度中，以多工序設(shè)備為優(yōu)化對象，以最小化復(fù)雜產(chǎn)品總加工用時(shí)和提高設(shè)備整體利用率為優(yōu)化目標(biāo)，在全面考慮制造系統(tǒng)中產(chǎn)品工藝、加工工序、設(shè)備運(yùn)行情況和工序約束關(guān)系等諸多因素基礎(chǔ)上，提出了考慮多工序設(shè)備權(quán)重的資源協(xié)同綜合調(diào)度算法。在縱向優(yōu)化方面，以優(yōu)先級和權(quán)重值為主的排序策略，有效地減少了工序間的加工空隙；在橫向優(yōu)化方面，最佳調(diào)度時(shí)刻策略有效地提高了設(shè)備利用率，因此算法進(jìn)一步優(yōu)化了綜合調(diào)度效果。同時(shí)，也為深入研究復(fù)雜產(chǎn)品的綜合調(diào)度問題拓展了思路，具有一定的理論和實(shí)際意義。