杜松霖,仵大奎,時宗勝,陳 曦,周文舉

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

0 引言

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

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

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

1 DABFSP研究現(xiàn)狀

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

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

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

統(tǒng)一裝配過程則主要負責將各種生產(chǎn)完成的產(chǎn)品零部件組裝成最終可以流向市場的待售產(chǎn)品。該過程在單一組裝流水線上完成。統(tǒng)一裝配過程同樣滿足流程式組裝工藝，同時又與前一階段的分布式協(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個帶有阻塞約束的分布式協(xié)同加工過程及1個單機的流程式組裝過程。

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

①計算所有工件的加工完成時間。

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

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

表1列舉了1個DABFSP實例。

表1 DABFSP實例

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

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

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

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

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

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

3 迭代貪婪算法

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

3.1 初始化

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

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

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

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

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

3.2 破壞-重構(gòu)

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

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

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

3.3 局部搜索

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

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

圖3中，深色方塊表示當前被插入的工件。

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

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

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

3.4 算法流程

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

①開始。

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

③t=1。

④while (t

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

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

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

⑧t=t+1。

⑨end while。

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

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

4.1 試驗設(shè)置

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

(1)

試驗使用了蒙特卡洛試驗方法。所有實例均獨立運行21次。試驗結(jié)果對比如圖4所示。

圖4 試驗結(jié)果對比圖Fig.4 Comparison of test results

4.2 結(jié)果分析

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

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

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

此外，試驗對比了不同工件數(shù)量、機器數(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ōu)的。此試驗結(jié)果同樣具有統(tǒng)計學意義。

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

表5 Wilcoxon試驗結(jié)果

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

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

表6 Friedman試驗結(jié)果

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

5 結(jié)論

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

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

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