基于混合迭代貪婪算法的分布式車間調(diào)度研究

杜松霖,仵大奎,時(shí)宗勝,陳 曦,周文舉

(1.上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院，上海 200444；2.江蘇中天互聯(lián)科技有限公司，江蘇 南通 204550； 3.新疆金風(fēng)科技股份有限公司，新疆 烏魯木齊 830026)

0 引言

調(diào)度問題廣泛地存在于實(shí)際加工制造的流程控制過程中，如儀器儀表、線纜、風(fēng)力發(fā)電機(jī)等產(chǎn)品的設(shè)計(jì)、生產(chǎn)、物流、管理等環(huán)節(jié)。調(diào)度方法及策略的研究一直是智能制造系統(tǒng)增效、節(jié)能、減排、降耗的核心與關(guān)鍵[1]。同時(shí)，隨著經(jīng)濟(jì)全球化與生產(chǎn)國(guó)際化進(jìn)程的加快，分布式協(xié)同制造模式也逐漸成為國(guó)際智能制造的主要方式之一[2-3]。分布式協(xié)同生產(chǎn)過程需要考慮多條分布式生產(chǎn)線及各條生產(chǎn)線內(nèi)部的協(xié)同制造。因此，相較于傳統(tǒng)單一流水線的生產(chǎn)模式，工件以及機(jī)器分配、工件排序造成的大規(guī)模、強(qiáng)耦合性是難以實(shí)現(xiàn)高效全局優(yōu)化的難點(diǎn)與痛點(diǎn)之一[4]。

當(dāng)前以不同約束條件下分布式協(xié)同制造系統(tǒng)各生產(chǎn)線之間工件的分配、生產(chǎn)線內(nèi)部的機(jī)器指派以及工件排序等痛點(diǎn)問題為驅(qū)動(dòng)，借助不同智能優(yōu)化算法實(shí)現(xiàn)多個(gè)耦合子問題的解耦，確保生產(chǎn)調(diào)度方案的高度可行，以實(shí)現(xiàn)各種決策量的協(xié)同優(yōu)化與全局優(yōu)化。這有效解決了許多分布式生產(chǎn)調(diào)度問題，如分布式置換流水車間調(diào)度[5]、分布式零空閑流水車間調(diào)度[6]、分布式零等待流水車間調(diào)度[7]和分布式阻塞流水車間調(diào)度[8]等。

本文以總裝配時(shí)間為優(yōu)化目標(biāo)，提出一種混合迭代貪婪(hybrid iterative greedy,HIG)算法，以求解分布式裝配阻塞流水車間調(diào)度問題(distributed assembly blocking flow-shop scheduling problem,DABFSP)。

1 DABFSP研究現(xiàn)狀

以分布式協(xié)同生產(chǎn)為背景，越來(lái)越多的制造企業(yè)不再是單純地生產(chǎn)最終交付產(chǎn)品，而是同時(shí)具備生產(chǎn)定制產(chǎn)品或相應(yīng)零件的能力。由供應(yīng)鏈上游企業(yè)生產(chǎn)的零部件被轉(zhuǎn)移到組裝流水線進(jìn)行統(tǒng)一組裝，待所有的部件組裝完成后對(duì)最終產(chǎn)品進(jìn)行儲(chǔ)存或市場(chǎng)投放。這一模式催生出分布式裝配生產(chǎn)。屬于同一產(chǎn)品的不同零部件在不同工廠的流水線上分別加工。各加工工廠能夠更加充分地利用自身優(yōu)勢(shì)，選擇更加科學(xué)、綠色、合理、高效的方式進(jìn)行生產(chǎn)。各加工流水線之間的協(xié)同生產(chǎn)，以及組裝流水線與加工流水線之間的協(xié)作運(yùn)營(yíng)，使得上述各類相關(guān)企業(yè)在降低生產(chǎn)成本的前提下，能夠科學(xué)規(guī)避企業(yè)生產(chǎn)、運(yùn)營(yíng)風(fēng)險(xiǎn)，從而滿足其長(zhǎng)遠(yuǎn)發(fā)展的戰(zhàn)略目標(biāo)。這也使得協(xié)調(diào)生產(chǎn)更加適應(yīng)經(jīng)濟(jì)全球化、生產(chǎn)國(guó)際化、制造智能化綠色化的大環(huán)境。因此，基于多個(gè)協(xié)同生產(chǎn)中心的分布式裝配調(diào)度問題受到業(yè)界越來(lái)越多的關(guān)注。

分布式裝配阻塞流水車間生產(chǎn)過程可分為協(xié)同加工過程和統(tǒng)一裝配過程[9]。

協(xié)同加工過程主要負(fù)責(zé)產(chǎn)品零部件的生產(chǎn)或加工。該過程在分布式協(xié)同加工工廠內(nèi)部完成。同時(shí)，協(xié)同加工過程遵循具有阻塞約束的流程式加工工藝。因此，該加工過程涉及零部件的分配，以及在每條流水線上零部件的生產(chǎn)調(diào)度，需要解決的關(guān)鍵性問題帶有非線性與強(qiáng)約束性。至今，有不少研究學(xué)者提出了各類求解算法試圖有效解決此類問題，如分散搜索算法[5]、迭代參考貪婪算法[10]等。

統(tǒng)一裝配過程則主要負(fù)責(zé)將各種生產(chǎn)完成的產(chǎn)品零部件組裝成最終可以流向市場(chǎng)的待售產(chǎn)品。該過程在單一組裝流水線上完成。統(tǒng)一裝配過程同樣滿足流程式組裝工藝，同時(shí)又與前一階段的分布式協(xié)同生產(chǎn)過程密不可分、互相制約，與分布式調(diào)度問題相比更具挑戰(zhàn)性。

2 DABFSP描述

分布式裝配阻塞流水車間調(diào)度過程如圖1所示。

圖1 分布式裝配阻塞流水車間調(diào)度過程示意圖Fig.1 Distributed assembly blocking flow-shop scheduling process diagram

DABFSP包括1個(gè)帶有阻塞約束的分布式協(xié)同加工過程及1個(gè)單機(jī)的流程式組裝過程。

DABFSP的優(yōu)化目標(biāo)Cmax(π)的計(jì)算過程如下。

①計(jì)算所有工件的加工完成時(shí)間。

②根據(jù)組成每個(gè)產(chǎn)品最后完工零件的結(jié)束時(shí)間,確定各產(chǎn)品的最早開始組裝時(shí)間。

③根據(jù)組裝流程工藝約束,計(jì)算所有產(chǎn)品最終的裝配完成時(shí)間。

表1列舉了1個(gè)DABFSP實(shí)例。

表1 DABFSP實(shí)例

表1實(shí)例包含8個(gè)待加工工件、5臺(tái)機(jī)器、4個(gè)加工工廠和4件產(chǎn)品。假設(shè)調(diào)度順序?yàn)棣?=[6,5]、π2=[7,1]、π3=[4,3]、π4=[8,2]。

①由加工序列和每個(gè)產(chǎn)品的加工時(shí)間,可得每個(gè)工件的加工完成時(shí)間。

步驟①的計(jì)算結(jié)果如表2所示。

表2 步驟①的計(jì)算結(jié)果

②由表2可知:組成產(chǎn)品P1的最后一個(gè)加工完成的工件是工件J5;組成產(chǎn)品P2的最后一個(gè)加工完成的工件是工件J1;組成產(chǎn)品P3的最后一個(gè)加工完成的工件是工件J3;組成產(chǎn)品P4的最后一個(gè)加工完成的工件是工件J2。因此，組成產(chǎn)品P4的所有工件率先進(jìn)入裝配過程，其開始時(shí)間為254 ms，然后依次是產(chǎn)品P2、P1、P3。

③由于產(chǎn)品P4的開始組裝時(shí)間為289 ms、裝配時(shí)間為48 ms，因此裝配完成時(shí)間為289+48=337 ms。此時(shí)，組成產(chǎn)品P2的所有工件均已加工完畢(即337>293)，則產(chǎn)品P2的開始組裝時(shí)間為377 ms，裝配時(shí)間為187 ms，裝配完成時(shí)間為337+187=524 ms。以此類推，經(jīng)計(jì)算可得按照加工序列π1=[6,5]、π2=[7,1]、π3=[4,3]、π4=[8,2]進(jìn)行產(chǎn)品的加工和裝配時(shí)的最大裝配完成時(shí)間為289+48+187+183+190=897 ms。

3 迭代貪婪算法

迭代貪婪(iterated greedy,IG)算法最初是為了解決置換流水車間調(diào)度問題而產(chǎn)生的經(jīng)典算法。其主要步驟包括初始化、破壞-重構(gòu)、局部搜索以及接收準(zhǔn)則。DABFSP是一類典型的離散問題，求解的時(shí)候不能直接使用解決連續(xù)問題的優(yōu)化方法。因此,本研究提出的HIG算法中包含的各種機(jī)制均是在基于工件序列編碼的基礎(chǔ)上，充分融合DABFSP的問題特征實(shí)現(xiàn)的。

3.1 初始化

初始化第一步是根據(jù)待加工工件的總處理時(shí)間，對(duì)屬于同一產(chǎn)品的各個(gè)工件進(jìn)行降序排列。因此，優(yōu)先加工的是總處理時(shí)間較大的工件。重復(fù)該過程，直到考慮所有待加工工件為止。結(jié)合表1中的實(shí)例，算法初始化第一步計(jì)算結(jié)果如表3所示。

表3 初始化第一步計(jì)算結(jié)果

初始化第二步是以第一步產(chǎn)生的工件序列為輸入，逐個(gè)將每個(gè)產(chǎn)品的所有工件在分布式協(xié)同加工工廠中分別加工，計(jì)算工件在所有可能的鄰域位置中的加工完成時(shí)間并選擇加工完成時(shí)間最小的位置插入。待組成此產(chǎn)品的所有工件均插入最優(yōu)的鄰域位置后，可確定此產(chǎn)品的工件加工初始序列。重復(fù)上述過程，直到考慮所有產(chǎn)品。算法初始化第二步計(jì)算結(jié)果如表4所示。

表4 初始化第二步計(jì)算結(jié)果

由以上步驟可得初始化加工序列為{4,3,6,5,7,1,8,2}。初始化第一步的主要目的是確定屬于每個(gè)產(chǎn)品的所有工件加工的順序。該順序是以工件為單位，在產(chǎn)品內(nèi)部進(jìn)行排序。初始化第二步的主要目的則是確定整個(gè)分布式協(xié)同加工階段加工產(chǎn)品的順序，是以產(chǎn)品為單位，在整個(gè)序列中進(jìn)行排序。由上述2個(gè)步驟可以初步得出整個(gè)分布式協(xié)同加工階段所執(zhí)行的可行調(diào)度序列。

3.2 破壞-重構(gòu)

在初始化序列中，由于所得初始解是結(jié)合問題特征由特定排序方式，即啟發(fā)式方法產(chǎn)生的構(gòu)造解，故排序方式直接影響著該解的質(zhì)量。為了使算法在面臨不同問題時(shí)依然能夠有效求解，本研究在破壞和重構(gòu)過程中考慮使用基于工件的交換和插入操作，通過破壞初始序列的結(jié)構(gòu)以產(chǎn)生更高質(zhì)量的新的重構(gòu)序列，從而使算法適應(yīng)不同類型的問題。

基于工件的交換和插入破壞-重構(gòu)如圖2所示。圖2中，深色方塊表示當(dāng)前被操作的工件。由圖2可知，HIG算法在初始化操作完成以后，對(duì)初始解隨機(jī)選擇交換或者插入操作進(jìn)行破壞-重構(gòu)，并以此提高算法求解問題時(shí)的穩(wěn)定性。HIG算法是基于單解的優(yōu)化算法。因此在執(zhí)行此操作時(shí)，HIG算法對(duì)初始化產(chǎn)生的序列中的1個(gè)隨機(jī)的工件，進(jìn)行隨機(jī)的交換或插入。

圖2 基于工件的交換和插入破壞-重構(gòu)示意圖Fig.2 Schematic diagram of artifact-based swap and insertion destruction-reconstruction

3.3 局部搜索

根據(jù)破壞-重構(gòu)操作產(chǎn)生的候選序列，將序列中的工件逐一插入分布式協(xié)同加工工廠中每個(gè)可能的位置，并選取最小裝配完成時(shí)間的位置作為此工件的最終位置。重復(fù)上述步驟，直到考慮所有的工件。局部搜索操作如圖3所示。

圖3 局部搜索操作Fig.3 Local search operations

圖3中，深色方塊表示當(dāng)前被插入的工件。

HIG算法在執(zhí)行局部搜索操作時(shí)，由破壞-重構(gòu)的序列考慮所有可能的鄰域位置，并選擇優(yōu)化目標(biāo)最小的鄰域位置進(jìn)行插入。此過程不僅能有效降低算法的復(fù)雜程度，而且能夠快速逼近鄰域最優(yōu)解，提升了算法精確度。同時(shí)，本研究使用以下接收準(zhǔn)則確保解的多樣性。

①當(dāng)經(jīng)過局部搜索操作產(chǎn)生的序列比上一次迭代產(chǎn)生的最優(yōu)解序列更優(yōu)，則此代可行解直接保留并進(jìn)入下一次迭代。

②當(dāng)經(jīng)過局部搜索操作產(chǎn)生的序列比上一次迭代產(chǎn)生的最優(yōu)序列差，但是比歷史最差解要好，則此代可行解也進(jìn)入下一次迭代，但不保留。

3.4 算法流程

本研究提出的HIG的偽代碼如下所示。

①開始。

②使用初始化方法構(gòu)造初始化調(diào)度序列。

③t=1。

④while (t

⑤使用破壞-重構(gòu)方法更新可行解。

⑥使用局部搜索方法更新可行解。

⑦計(jì)算可行解的適應(yīng)度值，依據(jù)接收準(zhǔn)則選取進(jìn)入下一代的可行解。

⑧t=t+1。

⑨end while。

⑩輸出最優(yōu)解。

4 試驗(yàn)設(shè)置及結(jié)果分析

4.1 試驗(yàn)設(shè)置

為了分析所提出的HIG算法的性能，本文選擇在900個(gè)問題實(shí)例上進(jìn)行試驗(yàn)驗(yàn)證。這些問題實(shí)例由不同的待加工工件數(shù)量、機(jī)器數(shù)量、工廠數(shù)量和產(chǎn)品數(shù)量分別組合而成，且每種組合各有5個(gè)不同值的實(shí)例，共計(jì)900個(gè)。同時(shí)，本研究將HIG與IG[9]、ILS[11]、H11、H12、H21、H22、H31、H32[12]進(jìn)行了比較。本試驗(yàn)考慮平均相對(duì)百分偏差(average relative percent deviation,ARPD)來(lái)評(píng)估調(diào)度序列π的質(zhì)量。其定義為：

(1)

試驗(yàn)使用了蒙特卡洛試驗(yàn)方法。所有實(shí)例均獨(dú)立運(yùn)行21次。試驗(yàn)結(jié)果對(duì)比如圖4所示。

圖4 試驗(yàn)結(jié)果對(duì)比圖Fig.4 Comparison of test results

4.2 結(jié)果分析

為了分析HIG算法在不同類型問題下的性能及與各對(duì)比算法是否存在顯著性差異，對(duì)比HIG算法和各對(duì)比算法在95%置信區(qū)間的差異。95%置信區(qū)間的均值如圖5所示。

圖5 95%置信區(qū)間的均值圖Fig.5 Means plot with 95% confidence interval

圖5中:橫軸為試驗(yàn)中涉及的9種算法；縱軸為各算法在不同問題實(shí)例情況下的ARPD值。由圖5可知，本文提出的HIG算法在95%的置信區(qū)間的ARPD值明顯優(yōu)于其他8種對(duì)比算法。該比較結(jié)果具有統(tǒng)計(jì)學(xué)意義。

此外，試驗(yàn)對(duì)比了不同工件數(shù)量、機(jī)器數(shù)量、產(chǎn)品數(shù)量、工廠數(shù)量劃分情況下9種算法ARPD值的概率圖。95%置信區(qū)間下的概率如圖6所示。

圖6 95%置信區(qū)間下的概率圖Fig.6 Probability with 95% confidence interval

由圖6可知HIG算法的效果：在滿足正態(tài)分布的前提下，HIG算法的均值和方差都是9種試驗(yàn)算法中最優(yōu)的。此試驗(yàn)結(jié)果同樣具有統(tǒng)計(jì)學(xué)意義。

為了將HIG算法與8個(gè)對(duì)比算法進(jìn)行分別比較，在本研究中采用Wilcoxon符號(hào)檢驗(yàn)進(jìn)行試驗(yàn)結(jié)果的統(tǒng)計(jì)學(xué)分析。Wilcoxon試驗(yàn)結(jié)果如表5所示。由表5可知，在90%和95%的置信區(qū)間內(nèi)，p值遠(yuǎn)小于?的值，因此符號(hào)檢驗(yàn)的假設(shè)成立。即，在90%和95%的置信區(qū)間內(nèi)，HIG算法分別顯著優(yōu)于IG、ILS、H11、H12、H21、H22、H31、H32算法。此試驗(yàn)進(jìn)一步論證了本研究所提HIG算法在解決DABFSP時(shí)的優(yōu)越性。

表5 Wilcoxon試驗(yàn)結(jié)果

此外，為了將HIG算法與IG、ILS、H11、H12、H21、H22、H31、H32算法共同比較，本文也采用了Friedman檢驗(yàn)。Friedman檢驗(yàn)是用于確定多個(gè)相關(guān)樣本的顯著性差異的統(tǒng)計(jì)學(xué)檢驗(yàn)方式，可有效反映算法之間的性能差異。

Friedman試驗(yàn)結(jié)果如表6所示。

表6 Friedman試驗(yàn)結(jié)果

由表6可知，解決DABFSP時(shí)，在95%的置信區(qū)間下，HIG算法的性能具有統(tǒng)計(jì)學(xué)意義的顯著性優(yōu)勢(shì)。

5 結(jié)論

本文研究了DABFSP，并以總裝配完成時(shí)間為優(yōu)化目標(biāo)提出了HIG算法。首先，在HIG算法的初始化階段，采用問題驅(qū)動(dòng)的構(gòu)造式方法生成初始解。其次，在HIG算法的破壞-重構(gòu)階段，采用基于鄰域信息的交換策略更新可行解。接著，在HIG算法的局部搜索階段，使用基于鄰域結(jié)構(gòu)的插入操作進(jìn)一步更新可行解。最后，在HIG算法的可行解接收階段，以一定概率接收差解進(jìn)入下一代，從而避免算法早熟收斂。

本文在試驗(yàn)階段選取了以不同工件數(shù)、機(jī)器數(shù)、工廠數(shù)和產(chǎn)品數(shù)為組合的共計(jì)900個(gè)問題實(shí)例，測(cè)試和比較了HIG算法和其他8種先進(jìn)對(duì)比算法的性能。通過針對(duì)于試驗(yàn)結(jié)果的統(tǒng)計(jì)學(xué)分析，能夠得出結(jié)論：HIG算法相較于其他8種對(duì)比算法，在求解DABFSP時(shí)具有顯著性的優(yōu)點(diǎn)。本文提出的HIG算法為解決DABFSP提供了新的方案。

雖然本文提出的算法在求解900個(gè)小規(guī)模DABFSP上具有顯著性的優(yōu)勢(shì)，但是將HIG應(yīng)用于帶有其他約束條件的DABFSP的解決上還具有很大的研究空間。下一步主要研究方向?qū)⒓性趲в衅渌s束條件的DABFSP。