彭 菁，段 程，李益兵

(武漢理工大學(xué) 機電工程學(xué)院,湖北 武漢 430070)

有限緩沖批量調(diào)度問題是基于批量流水線調(diào)度提出的一類問題：每個加工批次在一臺機器上完工后，先進入緩沖區(qū)暫存，等到下臺機器空余時，再進入下一道工序進行加工，否則會發(fā)生阻塞。目前對于批量調(diào)度問題的研究約束條件越來越復(fù)雜，其中采用有限緩沖批量調(diào)度方式能夠更加貼近實際存儲設(shè)備的約束下的生產(chǎn)環(huán)境，進而解決決策目標。因此，關(guān)于有限緩沖批量流水車間調(diào)度問題(limited buffer flow shop scheduling problem，LBFSSP)的研究具備學(xué)術(shù)價值以及實際意義。

目前，已有多種方法被應(yīng)用于研究批量流水線調(diào)度問題，如遺傳算法、粒子群算法、蟻群算法、人工蜂群算法、和聲算法和布谷鳥算法等[1-6]，這些算法在一定程度上取得了較好的效果。

隨著對流水線調(diào)度問題不斷地深入研究，針對存在有限緩沖區(qū)的流水線調(diào)度問題，學(xué)者提出各種智能優(yōu)化算法來解決。其中，張培文[7]提出有效的混合人工蜂群算法，結(jié)合WPFE(weighted profile fitting based on NEH)啟發(fā)式算法和遺傳算法改進人工蜂群算法，用來解決最大完工時間為目標的有限緩沖區(qū)流水車間調(diào)度問題。韓玉艷[8]采用離散NSGA(non-dominated sorting genetic algorithm)-Ⅱ算法進化求解帶有限緩沖區(qū)的多目標批量流水線調(diào)度問題，所提算法充分利用非支配解的信息引導(dǎo)種群進化。Liang[9]設(shè)計了一種自適應(yīng)差分進化算法(differential evolution,DE)，用于解決有限緩沖區(qū)的多目標流水車間調(diào)度問題。

由于在零等待和零空閑的批量流水車間的問題方面，等批量劃分方式比一致子批劃分策略所獲得的最大完工時間更短[10]，大部分文獻對批量流水線問題的研究建立在等量分批且批量劃分方案已知的模型上，而缺乏對非等量分批調(diào)度問題的探究。針對有限緩沖區(qū)的批量調(diào)度問題，筆者基于批量劃分方案未知且非等量分批的分批方式，以總的提前懲罰和延期懲罰為評價指標建立了針對存在有限緩沖區(qū)的一致子批[11]調(diào)度模型，并使用改進算法驗證了相應(yīng)結(jié)果。

1 改進布谷鳥算法

1.1 標準布谷鳥算法

布谷鳥搜索算法(cuckoo search algorithm，CS)是基于對布谷鳥尋窩產(chǎn)卵的行為進行模擬，以此提出了一種全新的搜索算法。該算法具有簡單、參數(shù)少、高效等優(yōu)點，并且多次成功應(yīng)用于工程優(yōu)化問題中，逐漸在群智能算法領(lǐng)域中嶄露頭角[12]。

布谷鳥算法模擬了布谷鳥為尋找適合的產(chǎn)卵鳥巢而隨機游走的尋窩過程。算法設(shè)定3個理想條件作為基礎(chǔ)：①布谷鳥每次隨機選擇一個鳥窩來產(chǎn)卵，每次只產(chǎn)一個卵；②在所有的鳥窩中，適應(yīng)度最好的鳥巢會保留到下一代；③每代產(chǎn)生的鳥巢數(shù)量是一定的，其中布谷鳥卵被發(fā)現(xiàn)的概率為Pα。在上述3個理想狀態(tài)的基礎(chǔ)上，算法產(chǎn)生新的候選解的更新公式:

(1)

1.2 編碼規(guī)則的設(shè)計

標準布谷鳥搜索算法的編碼方式是連續(xù)的，而流水線車間的調(diào)度問題是離散的，因此，首先需要將布谷鳥的連續(xù)編碼進行離散化，如圖1所示。

圖1 編碼規(guī)則

在編碼模型中，每一維表示一個鳥巢，每個鳥巢將編碼分為兩段[10]，前一段編碼將每個加工批次分成多個不等量的子批次，后一段用來給作業(yè)批次排序。

1.3 動態(tài)適應(yīng)的淘汰概率

標準布谷鳥算法中，種群通過萊維飛行產(chǎn)生新解后，種群當中的每個解都會產(chǎn)生隨機值，與淘汰概率Pα相比，如果隨機數(shù)大于淘汰概率，則保留該解，如果隨機數(shù)小于淘汰概率，則對這部分解淘汰并產(chǎn)生新解。隨著迭代次數(shù)Giter的增加，后期解的變化會變得不明顯，容易陷入局部最優(yōu)。因此參考文獻[13-14]，設(shè)計了一個動態(tài)適應(yīng)的淘汰概率來替代固定的淘汰概率。

(2)

式中:Pmax為設(shè)定的最大淘汰概率；Gmax為設(shè)定的最大迭代次數(shù)。

通過動態(tài)適應(yīng)的淘汰機制，算法前期以較小概率搜索種群，提高搜索效率，在后期以較大概率更新種群，加快收斂速度，提升算法性能。

1.4 基于關(guān)鍵路徑的局部搜索

關(guān)鍵路徑是指對某一特定的加工順序中決定最大完工時間的作業(yè)批次的序列，而每一個批次的加工時長被稱為關(guān)鍵塊。關(guān)鍵路徑上任何操作的變化都是影響最大完工時間的關(guān)鍵因素，也是構(gòu)建鄰域結(jié)構(gòu)的重要因素。因此，針對布谷鳥算法存在后期收斂速度慢、局部搜索能力弱和易早熟收斂等缺點，在調(diào)度順序確定的情況下改變子批量的分批數(shù)量，避免算法陷入局部最優(yōu)，從而獲得更優(yōu)解。

1.4.1 分批數(shù)目的局部搜索

首先要確定關(guān)鍵路徑，統(tǒng)計各個子批次在每個工序開始加工之前的阻塞時間，選擇阻塞時間最長的子批次作為局部搜索的關(guān)鍵批次。

如圖2所示，以3個作業(yè)批次為例，每個作業(yè)批次均分作2個子批次。圖2中陰影是有限緩沖區(qū)約束導(dǎo)致的子批次阻塞，加粗的黑色子批次塊所組成的路徑是關(guān)鍵路徑。

圖2 關(guān)鍵路徑的兩種領(lǐng)域結(jié)構(gòu)

局部搜索策略基于關(guān)鍵路徑的兩種鄰域結(jié)構(gòu)N1、N2，具體解釋如下：

N1：如果關(guān)鍵塊內(nèi)的首個子批次和下個子批次是同一作業(yè)批次，則首個批次與下一個子批次互換；關(guān)鍵塊的末子批次如果和上一個批次是同一作業(yè)批次，則末子批次和上一個子批次互換。這種領(lǐng)域結(jié)構(gòu)能夠改變關(guān)鍵塊的生產(chǎn)順序從而有機會縮小生產(chǎn)阻塞。

N2：關(guān)鍵塊的首個子批次在分批次范圍允許的情況下，將首個子批次均等分成兩個子批次。這種鄰域結(jié)構(gòu)通過改變關(guān)鍵塊的大小來改變關(guān)鍵路徑的生產(chǎn)狀況。

1.4.2 調(diào)度排序的局部搜索

首先明確作業(yè)批次調(diào)度的關(guān)鍵作業(yè)批次。統(tǒng)計各個作業(yè)批次停滯在機器上的非加工時間的長短，選擇阻塞時間最長的作業(yè)批次作為關(guān)鍵作業(yè)批次。局部搜索[2,8]的方式如圖3所示，K1和K2分別指代編碼上兩個不同位置的標志。以10個作業(yè)批次為例，交換機制指的是在確定關(guān)鍵作業(yè)批次在調(diào)度序列中的位置值K1后，另外選擇在除關(guān)鍵作業(yè)批次外的位置隨機產(chǎn)生一個位置值K2，然后交換它們位置上的編碼。插入機制指的是在調(diào)度排序部分之間隨機產(chǎn)生一個位置K2，將K1位置的關(guān)鍵作業(yè)批次編碼插入到K2位置之前，形成新解。

圖3 局部搜索的兩種方式

2 數(shù)據(jù)仿真與分析

以某醫(yī)療器械公司實際工況下的批量流水車間調(diào)度問題為研究對象，每批工件的加工總數(shù)和最大分批數(shù)目、緩沖區(qū)最大存儲區(qū)數(shù)目如表1所示，另外，每個作業(yè)批次在每臺機器上的加工時間如表2所示。

表1 每批作業(yè)批次工件總數(shù)、最大分批數(shù)和緩沖區(qū)最大存儲工件數(shù)

表2 作業(yè)批次與相應(yīng)工序加工時長的關(guān)系 min

測試案例在雙核CPU主頻1.8 GHz，內(nèi)存為8 GB，處理器為intel(R)Core(TM)i5-3337U，操作系統(tǒng)為Window8，開發(fā)環(huán)境為MatlabR2016b的電腦上運行。

參考文獻[5]，算法的相關(guān)參數(shù)設(shè)置如表3所示。另外，在引入的基于關(guān)鍵路徑的局部搜索機制中，局部搜索產(chǎn)生的概率為0.1。作業(yè)批次數(shù)目n分別為3、5、7，機器數(shù)目分別為3、5、7，已設(shè)置一定權(quán)重的提前懲罰和延期懲罰作為評價算法的標準。

表3 算法參數(shù)設(shè)置

通過實驗?zāi)M，改進前后的布谷鳥算法執(zhí)行10次后的結(jié)果如表4所示。改進前后布谷鳥算法評價目標的箱線圖如圖4所示。

表4 標準布谷鳥算法(CS)和改進后布谷鳥算法(ICS)結(jié)果比較

圖4 改進前后布谷鳥算法評價目標的箱線圖

從表4可知，改進布谷鳥算法得到的最優(yōu)評價目標的均值小于標準布谷鳥算法，證明了改進布谷鳥算法可得到更優(yōu)的目標解。

由圖4可知，改進后布谷鳥的四分位間距幾乎是改進前的一半，證明求解的評價目標數(shù)值更加集中。改進前布谷鳥算法有50%的解的評價目標小于6.97，而改進算法有50%的解小于5.63，評價目標降低了19.2%。并且未改進算法75%的解的評價目標小于21.14，而改進后算法75%的解的評價目標小于12.38，評價目標降低了41.4%，證明該優(yōu)化算法普遍獲得了更優(yōu)解，并且解的范圍更加集中，算法的質(zhì)量得到了明顯改善。

3 結(jié)論

筆者考慮了大批量流水車間的實際生產(chǎn)狀況，構(gòu)建了存在有限緩沖區(qū)的批量流水車間模型，模型采用一致子批的分批方式，綜合考慮了提前評價和延期評價作為目標函數(shù)。另外，在標準布谷鳥搜索算法的基礎(chǔ)上，提出一種動態(tài)的淘汰機制來替代不變的淘汰概率，優(yōu)化了算法的搜索策略，又引入基于關(guān)鍵路徑的局部搜索，能夠高效地獲得更優(yōu)解。仿真實驗和算法比較結(jié)果顯示，改進后的布谷鳥算法比標準布谷鳥算法具有更優(yōu)秀的綜合能力，在收斂速度和尋優(yōu)能力兩方面都更出色。該結(jié)果也表明，所研究的改進布谷鳥算法在解決存在有限緩沖區(qū)的流水車間調(diào)度問題上具有明顯優(yōu)勢。