基于改進候鳥遷徙優化的多目標批量流混合流水車間調度

湯洪濤， 王丹南， 邵益平， 趙文彬， 江偉光， 陳青豐

(浙江工業大學 機械工程學院， 杭州 310023)

批量流混合流水車間調度問題(LS-HFSP)是批量流問題與混合流水車間調度問題(HFSP)的結合，廣泛存在于煉鋼、食品加工、制藥等工業領域，近年來得到了學者的廣泛關注[1-4].根據給定拆分子批大小是否相同，可以將批量流問題分為相等批量流問題與不相等批量流問題.相等批量流混合流水車間調度問題是目前研究較多的LS-HFSP問題，相等批量拆分是解決批量流問題的最簡單、最直接的方法，一旦確定了子批數量，就可以確定每個子批的大小.但相等批量拆分只能優化子批的數量，無法優化每個子批的大小，并且在生產實際中大多為不相等批量流問題.對于不相等批量流混合流水車間調度問題，不僅要優化加工順序，還要優化子批的數量和大小，從而大大增加了計算的復雜度.

近年來，國內外已經有學者在ILS-HFSP領域做了大量研究，但這些工作具有一定的局限性，現有研究以單目標優化[5-10]為主.文獻[7]以最小化最大完工時間為目標，研究了柔性作業車間不相等批量拆分調度問題.文獻[8]以最小化總延遲時間為目標，研究了K階段不可混流的 ILS-HFSP問題.文獻[9]以最小化最大完工時間為目標，研究了只在最后階段具有多臺并行機的K階段不可混流的ILS-HFSP問題.文獻[10]以最小化最大完工時間為目標，研究了考慮批量流與換模時間的柔性生產線調度問題.

目前關于多目標ILS-HFSP問題研究較少.文獻[11]針對存在隨機擾動的相等批量流混合流水車間調度問題，提出了多目標候鳥遷徙算法，解決了最小化總加工時間與子批開工時間偏差的多目標優化問題.文獻[12]以減少平均停滯時間、能源消耗及提前和延遲造成損失為目標，研究了可變批次的批量流混合流水車間調度問題.文獻[13]以最小化最大完工時間與最小延期為目標，研究了多目標批量流水車間問題.關于在制品的流水車間調度問題，研究也較少.文獻[14]提出使用過濾算法，研究了卷煙生產中的在制品堆積及有限產能的動態調度問題.文獻[15]以最優緩存區容量為目標優化生產排程，提高了瓶頸資源的利用率.文獻[16]研究生產機組的訂單序列，建立了數學模型優化生產速率、在制品數量和生產周期3個目標.

ILS-HFSP是個NP難問題，通常采用啟發式算法來解決.候鳥遷徙優化(MBO)算法是一種最新發展的啟發式算法，由文獻[17]在2012年首次提出.該算法模擬以V形編隊飛行的鳥類遷徙行為，每一只鳥都代表一種可行解.在該算法中，鳥群中個體的數量、要考慮的鄰域解數、跟隨解共享的鄰域解數以及領導解更換后鳥群的迭代次數是影響其性能的4個重要參數，具有較強的局部搜索能力和簡單的結構，已成功應用于二次分配、流水車間調度、信用卡欺詐等不同的研究領域[6-7,18-20].

上述研究表明，對于以最小化在制品數量為目標的多目標ILS-HFSP的研究尚處空白，而減少在制品數量對于降低企業成本、提高企業的管理能力有著重要意義，也是實現精益生產的必由之路.此外，目前研究以批量流混合流水車間調度理論研究為主，其機器階段數和各階段機器數量不固定，結合實際研究背景及固定形式的混合流水車間研究較少.因此，本文以最小化完工時間與最小平均在制品數量為目標，結合工程實際研究了三階段混合流水車間的多目標ILS-HFSP，針對MBO算法各算子在算法運行不同階段改進概率具有差異的特點，提出了一種基于變鄰域搜索的自適應候鳥遷徙優化(AMBO)算法，并提出時間窗算子以加快算法的收斂速度.本文研究可為以最小化在制品數量與最大化生產速率的多目標ILS-HFSP問題提供理論依據.

1 問題描述

1.1 問題背景

某鋁鍋制造企業A現有一條混合流水線，如圖1所示.其中：該生產線由拉伸段、內噴涂段與包裝段組成，M11、M12為拉伸段內的兩臺相同拉伸機，M21為內噴涂段內的一臺內噴涂機，M31為包裝段內的一臺包裝機，B1、B2為緩存區.兩臺拉伸機的產能均為450個/h，內噴涂段的產能為900個/h，包裝段的產能為800個/h.由于鋁鍋的型號規格眾多，機器切換生產不同型號規格的產品時需要換模，每種型號規格的產品只配備一套模具以降低模具成本.此外, 產品的訂單數量變化較大，排程方案需考慮將大訂單拆分成若干個小訂單以防止產線堵塞.訂單經排程后形成包含產線可執行信息的工單，產線依據工單順序依次生產.

圖1 A公司鋁鍋產線構型圖Fig.1 Configuration diagram of the aluminum pot production line of A Company

該混合流水線的每臺拉伸機與內噴涂機同一時刻只能生產一種產品，拉伸機與內噴涂機需加工完當前工單后才能切換生產下一個工單.內噴涂機M21一次只能生產一種產品，拉伸機M11與拉伸機M12生產的不同產品需要根據加工順序依次進入內噴涂機M21，尚未進行內噴涂的產品需在緩存區B1中等待.內噴涂段生產速率大于包裝段，緩存區B2用以暫存未能及時包裝的產品.

通過分析各機器生產速率可知，產線的生產瓶頸在于包裝段，其最大生產速率總計為800個/h，而產線其他機器的產能有剩余.此外訂單的產品數量差別較大，生產小批量訂單加上換模時間將使產線的生產速率達不到包裝線的速率引起產能損失；若一直生產大批量訂單又可能導致在制品堆積問題.如何在最小化完工時間與在制品數量的兩個目標下得到最優調度結果是本研究的主要內容.本研究的基本假設如下：

(1) 原材料不存在缺料情況；

(2) 每臺機器的處理時間為固定值，機器不會出現故障；

(3) 數量較大的訂單會拆分成若干個數量不等的工單；

(4) 拉伸機與內噴涂機的換模時間為固定值；

(5) 包裝線的設置時間非常短，可認定為無換模時間；

(6) 任何兩個訂單的產品規格型號都不相同，無法共用一套模具；

(7) 緩存區為無限容量緩存區.

1.2 問題建模

本文研究一個有4臺機器的三階段不相等批量流混合流水車間調度問題，該三階段不相等批量流混合流水車間調度問題具體描述如下：

(1) 本文的研究對象是一個2+1+1型三階段混合流水車間，由第1階段的兩臺并行(相同)機器和第2、3階段各一臺機器組成.在此混合流水車間中，機器換線生產不同訂單的產品時需換模.第1階段與第2階段、第2階段與第3階段之間各設有一個緩存區.流水線形式及加工路線均滿足1.1節所提出的背景要求.

由問題背景可知，除包裝段外其余機器換線時需要進行換模設置，產線的拉伸段生產速率與內噴涂段的生產速率相同且都大于包裝段的生產速率.為使兩者產能匹配，存在一個最佳批量Q，每個產品以這個批量進行加工能使拉伸機、內噴涂段加工時間加上換模時間與包裝段的加工時間相匹配.

根據上述問題描述以及定義的數學符號，建立如下數學模型：

(9)

目標函數:

(10)

(11)

式(1)表示同一工單在內噴涂機上的開始加工時間與該工單在拉伸機上開始加工時間的約束；式(2)表示每個工單的開始加工時間必須大于等于0；式(3)為機器k上的工單Sij的開始加工時間與完工時間之間的關系；式(4)～(7)分別表示在拉伸機1、拉伸機2、內噴涂機、包裝線上，下一個工單的開始時間與上一個工單完工時間的約束；式(8)表示不同訂單子批次(工單)在拉伸機1、拉伸機2和內噴涂機上是不可混流生產的；式(9)表示拆分后的每個工單的最小產品數；式(10)表示完成所有訂單生產的最小化完工時間；式(11)表示產線的平均在制品數量最小化.

2 自適應候鳥遷徙優化算法

基本的MBO算法是針對二次分配這種連續函數優化問題提出的，不能直接用于處理HFSP這類離散的組合優化問題，需要轉換成離散形式.本文基于候鳥遷徙優化算法，結合ILS-HFSP問題，提出一種AMBO算法，包括批量拆分規則、編碼與解碼機制、鄰域搜索策略、種群初始化、領導解優化、跟隨解優化、領導解替換與算子權重自適應調整等，可有效求解ILS-HFSP問題.

2.1 算法具體定義

2.1.1批量拆分規則 對于批量流問題，需要明確訂單的拆分規則.常見的訂單拆分方式為給定一個隨機數，對需要拆分的訂單隨機拆分成該數量個子訂單[5]，隨機數的選取范圍需根據訂單大小與問題特征具體問題具體分析.本研究的批量大小不完全相同，拆分批量的上下限應根據每個訂單的大小進行調整.

CJi2Qmin

CJiQmin

CJi2Qmin, CJiQminé?êêù?úú

2.1.2編碼與解碼機制 ILS-HFSP問題需同時優化訂單拆分問題和作業調度問題，因此編碼應同時考慮這兩個方面，本文采用兩階段編碼方案.用自然數序列代表所有可能的工單排列，編碼分為兩段：第1段表示加工順序；第2段表示待分配的工單編碼，每個工單編碼對應一個加工順序編號.每個工單編碼由一個工單編號與其對應工單的數量組成，工單編號數為4位整數，工單數量為5位整數.例如，工單編號為101，數量為 3 000 的工單的工單編碼為010103000.編碼示例如圖2所示.

圖2 編碼示例Fig.2 Code sample

每個編碼都代表訂單拆分后的工單在內噴涂機上的排程結果，為了進一步得到每個工單在各機器上的加工時間序列，計算每個解的適應度值，需對編碼進行解碼.由于拉伸機1與拉伸機2并行工作，每個工單只能在其中一臺機器上加工，解碼時需要考慮兩個問題：① 所有工單在機器上的開始加工時間與完工時間；② 系統平均在制品數量.其具體過程如下.

假設有b個工單，其在內噴涂機上的加工序列為?=(?1, ?2, …, ?b)，即依次將工單?q從?中取出并執行如下步驟.

步驟1選取具有最先空閑時間的拉伸機，將工單?q分配到該機器上，確定其在該拉伸機上的開始加工時間與完工時間；

步驟2重復步驟1，直到完成所有工單的拉伸機分配；

步驟3根據加工序列與各工單在拉伸機上完工時間依次計算每個工單在內噴涂機上的開始加工時間與完工時間；

步驟4根據每個工單在內噴涂機上的完工時間，計算每個工單在包裝線的開始加工時間與完工時間，得到加工完所有工單的最終完工時間；

步驟5根據解碼所得到的各工單在其對應加工機器上的開始加工時間、結束加工時間、各機器的節拍與換模時間，計算流水車間開始加工到結束加工的平均在制品數量.

2.1.3適應度函數值 在得到解在各機器上的加工時間后，需要評估解的適應度值來完成領導解、跟隨解的排序選擇.本文采用權重和法處理多目標優化問題，由于研究的兩個目標具有不同量綱，需先進行目標歸一化處理，具體過程如下所示：

(12)

(13)

式中：λ1、λ2為2個目標函數的權重.

最小化總加時間與最小化平均在制品數量是本研究的兩個目標，產線優化的首要目標是最大化生產速率使得企業效益最大化，而最小化平均在制品數量是為減少成本，屬于次要目標，取權重λ1=0.6，λ2=0.4.

2.2 改進策略

2.2.1鄰域搜索算子 MBO算法是一種基于鄰域搜索的元啟發式算法，因此有必要為其確定高效的鄰域搜索算子.基于本文所采用的兩階段編碼機制，從文獻[21]中引入4種常見的鄰域算子，分別為插入算子、貪婪插入算子、交換算子、貪婪交換算子.交換算子計算量小但局部搜索能力有限；貪婪算子雖然能提高局部搜索的結果，但會極大增加計算量.為平衡計算量與局部搜索結果，基于最佳批量原則本文提出一種時間窗算子，使其以較短的時間得到較優的解.以上算子都是針對調度子問題，針對批量拆分子問題，本文采用批量調整算子，使各訂單的工單數與工單的產品數隨算法迭代調整.

(1) 時間窗算子.

由于工單產品數量各不相同，首先定義一個推進時間窗W=[tes,tlf]，tes為在內噴涂機處任務的開始時間，tlf為在內噴涂機處任務的結束時間，其是預測時域內包含一定數量工單的時間窗口，而其平均寬度取2Qt3.時間窗為2Q的匹配度較小，因此增加一個寬放系數γ，使時間窗的寬度取為

(2-2γ)Qt3≤tlf-tes≤(2+2γ)Qt3

(14)

式中：γ為時間窗的寬放系數，常見的寬放系數為0.05、0.1、0.2等，為盡可能匹配較多的訂單，取寬放系數為0.2.

每次搜索的目標是從當前解中隨機尋找拉伸機編號不相同的兩個未被匹配時間窗的工單，對其進行時間窗匹配，形成一個新的鄰域解，且滿足如下訂單關系式：

(2+2γ)Qt3

(15)

圖3 時間窗算子Fig.3 Time window operation

步驟1將當前鳥中的所有工單輸入到一個搜索集中；

步驟2判斷搜索集是否為空，若為空則采用隨機交換操作形成鄰域解并結束鄰域搜索；

步驟3尋找搜索集中產品數量最大的工單；

步驟4判斷該工單與其后一工單是否能滿足時間窗約束，若滿足時間窗約束則將找到的訂單2加工序號與訂單1后的加工序號交換，若不能則跳到步驟5；

步驟5尋找個體中能與其滿足時間窗約束的工單，若無法找到，則將該工單從搜索集中剔除并重復步驟1～5，若找到則將找到的工單與其后一工單位置進行交換形成新的解.

(2) 批量調整算子.

在工單編碼段任選一個具有兩個以上工單的訂單，選擇其中兩個相鄰的工單對其重新分配：隨機選取其中一工單中隨機數量的產品分配到另一工單中.若重新分配后的工單數量低于最小批量Qmin，則以50%概率將該工單全部分配到另一工單中，并將該工單所屬訂單的工單數減1；以50%的概率使該工單產品數量等于最小批量Qmin，并將其余數量的產品分配給另一工單.例如，一個 1 300 與 4 400 的工單組合，隨機調整成 1 600 與 4 100 的組合.批量調整算子示意圖如圖4所示.

圖4 批量調整算子示意圖Fig.4 Diagram of batch adjustment operation

上述鄰域搜索算子分別針對不同的子問題，如果只采用其中一種很難找到全局最優解.為了有效地聯合兩個子問題，提出了以下混合結構.

(1) 混合結構1：首先執行插入算子，然后執行批量調整算子.

(2) 混合結構2：首先執行貪婪插入算子，然后執行批量調整算子.

(3) 混合結構3：首先執行交換算子，然后執行批量調整算子.

(4) 混合結構4：首先執行貪婪交換算子，然后執行批量調整算子.

(5) 混合結構5：首先執行時間窗算子，然后執行批量調整算子.

2.2.2鄰域算子權重自適應調整 本文采用了4種常見的鄰域算子、時間窗算子、批量調整算子以及5種混合結構共計11種算子.為有效利用所采用的11種不同鄰域算子，采用變鄰域搜索策略使各算子的鄰域得到充分探索.本文采用輪盤賭的方法，給每個算子以一個權重，在每次進行鄰域搜索操作時根據每個算子權重隨機選擇鄰域搜索算子得到鄰域解.

鄰域搜索的每個算子在算法的不同階段對解的改進效果各不相同，例如在算法求解的初始階段應優先選擇全局搜索能力強的算子，在后期調整階段應優先選擇局部搜索能力強的算子.因此本文引入自適應調整策略[22]，使每個鄰域算子權重隨算法迭代自動調整，其具體計算如下.

(16)

式中：πO為算子O經過m次迭代后的得分累計情況，其初始值為0，若表現比最優解好，則取πO=πO+1，對其余算子取原值；θO為算子O經過一個權重調整周期時算子O使用的次數；r為反應因子，控制權重調整規則對啟發式方法的效率變化作出反應的速度與權重調整幅度.如果r為0，那么將完全不使用分數，而是保持初始權重.如果r設置為1，則在最后一代中獲得的分數決定權重.本文取r為0.5，在反應速度與調整幅度之間保持平衡.設每個算子的初始權重為1，當算法完成一個迭代周期m后更新每個算子被選擇的概率P，并重新將算子的權重設為1.

2.2.3擾動機制 MBO算法的鄰域搜索機制過度關注了算法的局部搜索能力，為平衡算法的全局搜索和局部搜索能力，將擾動機制引入到MBO算法中.記g為擾動機制觸發周期，如果領導解連續g次迭代沒有更新，則擾動機制觸發.在基本的擾動機制中，防止解陷入局部搜索的方法是用隨機產生的新解將其替換.完全隨機的方法會影響到算法的執行效率，為提高算法的執行效率，在連續第g次領導解沒有更新時，以領導解為種子，引入Glover操作產生兩個解分別替換領導解的左右跟隨解.Glover操作將解序列拆分成z個子解序列，每個子序列以z為步長依次從原解序列中挑選組成，然后將z個子序列重新組合成擾動后的解序列.Glover操作的優勢在于可以從種子解進行發散產生新解，并且新解繼承舊解的序列信息，有利于提高算法的執行效率，已被文獻[5,23-24]等用于防止算法陷入局部最優解中，取得了良好的效果，并根據文獻[5]采用z=3作為Glover操作的參數.

2.3 AMBO算法實現

AMBO算法包含以下幾個步驟：種群初始化、領導解改進、跟隨解改進、領導解替換與算子權重更新、循環迭代與擾動機制.具體流程如圖5所示.

圖5 AMBO算法流程圖Fig.5 Flowchart of AMBO algorithm

步驟1初始化種群.首先，設置AMBO算法的6個控制參數，包括鳥(解)群中個體的數量(α)，要考慮的鄰域解數(β)，跟隨解共享的鄰域解數(χ)，領導解更換后鳥群的迭代次數(ω)，算子權重自適應調整周期(m)、擾動機制觸發周期(g).然后根據批量拆分規則對所需排程的訂單任務拆分后對每個工單賦以隨機加工順序生成一個可行解，重復此過程生成α個解，選取適應度最優的解作為領導解，并將其余解隨機安置在V形種群結構上形成初始種群.

步驟2領導解改進.根據各算子的初始權重得到相應被選擇概率，采用輪盤賭方法圍繞領導解生成β個鄰域解.首先，對所得到的鄰域解根據解碼結果評估其適應度值，如果鄰域解中最優解的適應度值優于領導解，那么領導解將被替換；否則，領導解保持不變.然后，將未使用的鄰域根據其適應度值選取最優的2χ個解，分別形成包含χ個鄰域解的左、右共享鄰域集.

步驟3跟隨解改進.改進過程是沿著尾巴進行的.對于左(右)隊列中的跟隨解(例如X)，根據各鄰域算子權重以輪盤賭方式產生β個鄰域解.所產生的β個鄰域解和左(右)共享鄰域集中的解被視為X的鄰域集，對所得的鄰域集根據解碼結果評估其適應度值.如果最佳鄰域解比X具有更好的適應性，則替換X；否則將保持跟隨解不變.隨后，在未使用的鄰域中選擇最優的χ個解，用來重建左(右)共享鄰域集.重復上述過程，直到遍歷完左隊列和右隊列中的所有跟隨解為止.

步驟4領導解替換與算子權重更新.在執行第3步ω次后，若追隨解中的最優解比領導解適應值更優，則將最優追隨解與當前最優解相互交換以更新領導解，否則解將保持不變.根據不同算子對解的改進情況更新其算子權重，并判斷是否達到鄰域搜索算子權重更新周期，若達到鄰域搜索算子權重更新周期，依據鄰域算子權重自適應調整式(16)分別更新每個算子的權重，并依據權重更新每個算子被選擇的概率.

步驟5循環迭代與擾動機制.為了防止算法陷入局部最優，采用Glover 操作對g次迭代后未更新的領導解進行擾動，取兩個新解分別替換領導解后的左、右跟隨解.算法在若干次迭代后如果達到最大迭代次數，則算法終止；否則，重復步驟2～5直到滿足算法終止條件.

3 仿真實驗研究

3.1 算例產生規則

A企業的訂單統計分析后具有以下特征，產品數量在3×103以下、3×103～1×104與1×104～2×104的訂單分別占據其所有訂單數的80%、15%與5%，產品總數量分別占所有訂單的產品數總和的50%、30%與20%.出于A企業接單能力、成本、效率等因素的考慮，最大訂單數量不超過2×104，最小訂單數量不小于103，即Qmin=103.設定所有訂單的產品數量都能被10整除，訂單的數量特征如表1所示.

表1 訂單產品的數量特征Tab.1 Quantity characteristics of product orders

文獻[5]指出，目前關于批量流水車間調度問題沒有基準算例，為此本文根據表1的訂單產品數量特征，隨機產生不同規模的訂單任務作為算例來評估算法性能.各機器的生產速率以及問題背景保持一致：拉伸機1與拉伸機2的生產速率為4.5×102個/h，內噴涂機的生產速率為9×102個/h，包裝段的生產速率為8×102個/h.拉伸機1、拉伸機2與內噴涂機的換模時間都為30 min，可以得到最佳加工批量Q=3.6×103.

3.2 參數設置

參數設置通常在元啟發式算法的有效性中起到重要作用.為了得到AMBO算法的最優參數，采用實驗設計(DOE)方法設計了田口實驗.AMBO算法中有6個控制因素，包括了α、β、χ、ω、m、g.由于β≥2χ+1，所以參數β、χ不滿足實驗設計要求.本文采用文獻[17]建議的參數β=3、χ=1，將α、ω、m、g這4個參數作為實驗因子，以一組訂單數量為20的30個隨機案例的平均值來測試在算法運行100 s時的平均最優結果值，通過Minitab17設計并運行分析最佳參數配置.

參考文獻[5-6]中的因子水平，設計了4因子3水平的L9型正交田口實驗，其各因子的3個水平取值分別為α{α1=25，α2=51，α3=81}、ω{ω1=5，ω2=10，ω3=15}、m{m1=5，m2=10，m3=15}、g{g1=10，g2=20，g3=30}，表2為所設計的L9正交實驗及相應的實驗平均值.在Minitab17中分析后得到均值的主效應圖如圖6所示，其中：μ為每種參數的平均響應值.均值響應表如表3所示，其中：Δ為每個因子最大平均值減去最小平均值.從圖6中可以得到，α=51、ω=10、m=10、g=10的參數組合下，AMBO算法將具有更好的性能.因此，將α=51、β=3、χ=1、ω=10、m=10、g=10作為AMBO算法的初始化參數.

表2 正交矩陣及響應值Tab.2 Orthogonal matrices and response values

圖6 均值主效應圖Fig.6 Mean main effects plot

表3 均值響應表Tab.3 Mean response table

3.3 算法測試

為驗證AMBO算法求解問題的有效性，將其與基本MBO、遺傳(GA)算法對比.因為問題的NP難特性，不能保證得到問題的最優解.因此，以多次重復實驗所得到的最優解的平均值作為衡量算法求解精度，采用最優解的標準偏差評價算法的穩定性.因為訂單隨機性的影響，為了能夠得到更多可靠的數據，算法在不同訂單規模下隨機生成30個訂單任務，再對每個訂單任務重復運行30次，得到每個任務的最優解平均值與標準偏差，分別對所得到的30個訂單任務的最優解平均值與標準偏差取平均值，即得到所評價算法在該規模下的最優解平均值與標準偏差.

3種算法編碼規則完全一致，其中遺傳算法參數為種群規模為500，交叉概率Pc=0.8，交叉算子選用順序交叉，變異概率Pm=0.1，變異算子選用插入算子與批量調整算子；AMBO算法參數為鳥群中個體的數量α=51，要考慮的鄰域解數β=3，跟隨鳥共享的鄰域解數χ=1，領導鳥更換后鳥群的迭代次數ω=10，算子權重自適應調整周期m=10，擾動機制觸發周期g=10；基本MBO算法的參數引自文獻[17]：鳥群中個體的數量α=51，要考慮的鄰域解(β=3，跟隨鳥共享的鄰域解數χ=1，領導鳥更換后鳥群的迭代次數ω=10，鄰域算子采用插入算子、交換算子與批量調整算子.將算法終止條件統一設置為連續迭代100次最優值不變；采用MATLAB 2014b編程，測試環境為Windows 10系統，CPU為i7-7700k、內存為16 GB.隨機生成30個訂單總數為20的任務，每個任務進行30次重復實驗，得到的平均值與其標準偏差(SD)結果如表4所示.

3種算法實驗所得的最優解均值、解的標準偏差、平均收斂迭代次數及算法平均運行時間的結果如表5所示，并根據算法迭代過程繪制了3種算法的平均收斂過程圖如圖7所示.其中：ξ為迭代次數；κ為每次迭代中30次重復的多目標最優值.

圖7 3種算法收斂效果圖Fig.7 Convergence effect diagram of three algorithms

由表4、表5和圖7可知，GA算法收斂較快，但易陷入局部最優，求解精度差；而基本MBO算法雖然有一定的局部搜索能力，但其搜索能力有限，收斂速度慢且容易陷入局部最優，無法使候鳥集中在最優值附近；而本文提出的AMBO算法，采用了自適應算子權重與變鄰域搜索，加快收斂速度且增強了局部搜索能力，較其他兩種算法其求解精度更高，穩定性更好，求解時間與MBO算法較為接近，說明了AMBO算法的有效性.

表4 算法結果對比Tab.4 Comparison of algorithm results

表5 3種算法的實驗結果Tab.5 Experimental results of three algorithms

進一步驗證算法的有效性與穩定性，用3種算法對不同任務量求解.表6分別為訂單總數為30、40、50的3種不同任務規模隨機重復平均實驗結果.

由表6可以看出，在小規模算例中，隨著任務規模的增大，最優解均值會增加，算法運行時間將明顯增加，算法平均收斂次數增加也十分明顯.GA算法在收斂速度上有一定的優勢，但其缺點在于容易陷入局部最優.MBO算法在運行時間上比GA慢，但其全局搜索結果比GA更好.AMBO算法的求解時間相比于GA算法較長，與MBO算法較接近，但其求解精度與解的標準偏差均優于MBO算法與GA算法.

表6 3種算法在不同規模下的實驗結果

上述測試算例規模較小，為進一步測試算例規模對算法的影響，選取任務規模為60、80、100的大規模案例，以最大CPU運行時間為終止條件，每個任務規模隨機重復30次，以相對百分比增加率[6](RPI)值與其標準差測試各算法尋優能力.最大CPU運行時間正比于量規模，因此設定CPU運行時間為n×ρ，n為訂單總數，即排產任務規模，ρ為設置的常數，隨著算法規模的增加，算法的測試時間也將增加，為了綜合比較算法的性能，設置三種不同的ρ分別為10、20、30 s，在ρ=30時所對比算法大部分已達到收斂狀態.RPI值計算公式如下：

(17)

表7 當ρ=10，20，30時，GA、MBO與AMBO算法RPI值比較Tab.7 Comparison of RPI among GA, MBO, and AMBO algorithms at ρ=10，20， and 30

表8 當ρ=10，20，30時，AMBO與對比算法的T檢驗結果比較

由表7和8可知，當ρ=10，任務規模為60的測試實例中，AMBO算法均優于MBO算法與GA算法；任務規模為80的測試實例中，AMBO算法GA算法無顯著差異，但優于MBO算法；任務規模為100的測試實例中，AMBO算法劣于GA算法但優于MBO算法.當ρ=20，30時，AMBO算法能在所有測試實例中優于MBO算法與GA算法.AMBO算法為了保證精度而犧牲了求解速度，在大規模算例中，盡管AMBO算法在分配較少的時間(ρ=10)時劣于GA，但在分配更多CPU時間(ρ=20,30)后，AMBO仍優于GA算法.因此，在大規模算例下，AMBO算法總體上優于MBO算法與GA算法.

從上述測試結果可以看出，AMBO算法在任務規模為50以下的小規模算例中，其求解精度與穩定性均優于MBO算法與GA算法；在大規模算例中，AMBO算法的尋優能力優于MBO算法，雖然在較少CPU時間內會劣于GA算法，但總體優于GA算法，故能說明AMBO算法的有效性.

4 結語

針對2+1+1型三階段混合流水車間的ILS-HFSP，提出了基于變鄰域搜索的AMBO算法，解決了最小化完工時間與最小化系統平均在制品數量的多目標優化問題.所設計的算法借鑒了自適應大鄰域搜索算法，在鄰域算子處設計了時間窗算子與算子權重隨算法的迭代自適應調整策略，提高了算法的全局搜索能力與求解精度.通過對不同規模任務的30次隨機重復實驗，表明所建立的調度數學模型及改進的候鳥遷徙優化算法是可行有效的，AMBO算法相比于MBO算法與GA算法，具有求解質量更高、最優解標準偏差更小的優點.本研究可以降低混合流水車間的平均在制品數量，填補了ILS-HFSP問題關于最小化完工時間與最小化在制品數量多目標優化研究的空白，也更符合工廠實際生產.未來將結合緩存區配置優化與動態排程等方面進行進一步研究.