基于離散教與學(xué)算法的分布式預(yù)制流水車間調(diào)度研究

曹勁松，熊福力

(西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055)

0 引言

流水車間調(diào)度問題(FSSP, flow shop scheduling problem)已被證明是一個非確定性多項式難(NP-hard)問題[1-2]，問題解空間大，復(fù)雜度高，傳統(tǒng)的精確算法如分支定界[3]在求解該類問題時，很難在合理時間內(nèi)得出問題解。因此，研究人員通常采用啟發(fā)式算法對相關(guān)問題進行求解。潘子肖和雷德明[4]針對分布式低碳并行機調(diào)度問題提出了一種基于問題性質(zhì)的非劣排序遺傳算法-II。Abdel等[5]提出了一種將鯨魚優(yōu)化算法與局部搜索策略相結(jié)合的新算法來解決置換流水車間調(diào)度問題。劉晶晶等[6]根據(jù)柔性作業(yè)車間調(diào)度問題的特點，以最小化完工時間為目標(biāo)提出了一種混合果蠅-遺傳算法，并與遺傳算法對比，證明了所提算法的有效性。近年來，更多的智能方法被應(yīng)用于FSSP，如模擬退火[7]、禁忌搜索[8]、蟻群算法[9]、粒子群優(yōu)化[10]、免疫算法[11]、人工蜂群算法[12]等。

2011年，Rao等[13-15]從實際的教師教學(xué)和學(xué)生的學(xué)習(xí)過程中得到啟發(fā)，提出了一種新型的群智能算法-教與學(xué)優(yōu)化算法(TLBO,teaching-learning based optimization)，該算法具有收斂速度快，能夠屏蔽參數(shù)干擾的優(yōu)點。而后，趙乃剛[16]將其應(yīng)用在求解無約束優(yōu)化問題上。馬文強等[17]設(shè)計了一種混合教與學(xué)算法有效求解了煉鋼連鑄調(diào)度問題。何雨潔等[18]提出了一種混合離散TLBO算法求解復(fù)雜并行機調(diào)度問題。但目前關(guān)于TLBO算法的研究集中在求解線性化問題上，僅少部分學(xué)者將其應(yīng)用在FSSP領(lǐng)域，且通過TLBO算法解決分布式預(yù)制構(gòu)件流水車間調(diào)度問題的研究還未出現(xiàn)。

因此，本文在充分考慮預(yù)制構(gòu)件生產(chǎn)特殊性(工序間的差異性較大，工序處理周期長)的基礎(chǔ)上，針對分布式預(yù)制構(gòu)件流水車間調(diào)度問題，以最小化訂單總拖期懲罰為目標(biāo)，結(jié)合問題雙層整數(shù)編碼的特點，提出了一種離散教與學(xué)優(yōu)化算法(DTLBO)。最后通過大量算例的測試實驗，驗證了DTLBO算法求解問題時的有效性。

1 問題描述與建模

如圖1所示，分布式預(yù)制流水車間調(diào)度問題可以描述為：來自客戶的n個預(yù)制構(gòu)件訂單，需被指派到F個預(yù)制構(gòu)件工廠處理，每個工廠內(nèi)都有一條流水線，流水線上的機器配置相同。生產(chǎn)過程由6道工序組成：1)模具組裝；2)鋼筋預(yù)埋；3)混凝土澆筑；4)蒸汽養(yǎng)護；5)模具拆除；6)瑕疵修整。每道工序僅有一臺機器(即單生產(chǎn)線工作模式)。預(yù)制構(gòu)件生產(chǎn)不同于傳統(tǒng)流水車間問題，根據(jù)生產(chǎn)工藝的特征可將工序分為并行工序(可同時處理多個訂單)和串行工序(當(dāng)進行到該工序下的訂單未處理完前，不可對下一訂單進行處理)。其中工序4蒸汽養(yǎng)護為并行處理，其余工序為串行處理。若訂單j被指派到工廠f生產(chǎn)后，在交貨期dj后完工，則會產(chǎn)生拖期懲罰費用。研究以最小化總訂單拖期懲罰為目標(biāo)，給出訂單在工廠間最佳的指派方案和生產(chǎn)調(diào)度方案。

圖1 分布式預(yù)制構(gòu)件生產(chǎn)調(diào)度系統(tǒng)

1.1 相關(guān)假設(shè)與參數(shù)說明

對于該集成優(yōu)化問題的相關(guān)假設(shè)有：1)所有機器在調(diào)度零時刻均為可用狀態(tài)；2)不考慮機器故障、工件損壞等突發(fā)情況；3)訂單在工序上處理完成之前不能被其他訂單搶占；4)訂單在相鄰工序間的安裝和運輸時間忽略不計。

表1 調(diào)度模型參數(shù)說明

1.2 數(shù)學(xué)模型

基于以上符號和假設(shè)建立數(shù)學(xué)模型如下：

(1)

s.t.

(2)

(3)

(4)

Cj,k≥Cj-1,k+Pj,k,?j,k∈K {4}

(5)

Cj,k≥Cj,k-1+Pj,k,?j,k∈K {4}

(6)

Cj,k=Cj,k-1+Pj,k,?j,k∈{4}

(7)

Cj,k≥0

(8)

式(1)為目標(biāo)函數(shù)最小化訂單總拖期懲罰費用；式(2)確保每個訂單被指派到某一工廠中；式(3)和式(4)表示訂單j是否和訂單i指派到同一工廠，且訂單j是否在訂單i緊后加工；式(5)表示訂單在工序上的處理時間不早于上一訂單在此工序上的完工時間，第4道工序蒸汽養(yǎng)護為并行處理過程，不需滿足此約束；式(6)表示訂單在工序上的開始處理時間不早于該訂單上一工序的完工時間；式(7)為并行工序完工時間的計算公式；式(8)定義了決策變量的取值范圍。

2 離散教與學(xué)優(yōu)化算法

TLBO算法原理[14]是模擬以班級為單位的學(xué)習(xí)方式，通過教師的“教”來引導(dǎo)班級學(xué)生成績提高；同時，學(xué)生之間通過相互“學(xué)習(xí)”的方式進一步促進知識的吸收。其中，教師和學(xué)生相當(dāng)于進化算法中的個體，而教師是對應(yīng)目標(biāo)值最佳的個體，學(xué)生成績提高表示優(yōu)化目標(biāo)得到改進。TLBO算法算法分為3個階段：1) 教師階段：在班級中尋得最優(yōu)解個體作為教師，引導(dǎo)班級中的學(xué)生搜索更好的解；2) 學(xué)生階段：班級中學(xué)生通過與其他學(xué)生學(xué)習(xí)，獲取比自身更好的解；3) 角色互換：在某次迭代中，若有學(xué)生尋得的解比教師的解更好，則在下一次迭代中將該學(xué)生替換為教師，教師降級為學(xué)生。

針對分布式預(yù)制構(gòu)件流水車間調(diào)度該類非線性整數(shù)規(guī)劃問題，本文在TLBO算法的基礎(chǔ)上提出了一種離散教與學(xué)優(yōu)化算法(DTLBO)，算法步驟如下：

圖2 DTLBO算法框圖

Step1：通過結(jié)合啟發(fā)式策略和隨機生成的方式生成初始“班級”群體pop，確定教師解Xt；

Step3：學(xué)習(xí)階段，學(xué)習(xí)階段分為相互學(xué)習(xí)和自我學(xué)習(xí)，相互學(xué)習(xí)過程是隨機將學(xué)生個體兩兩配對，進行與步驟2相同的信息交互操作，若得到的解質(zhì)量更好則更新學(xué)生個體；

Step5：將學(xué)生個體Xi中目標(biāo)值最優(yōu)的個體X*取出與教師解Xt比較，如對應(yīng)目標(biāo)值更佳，則將X*替換為Xt；

Step6：判斷是否滿足終止條件：否，返回步驟2；是，輸出最終教師解Xt和對應(yīng)目標(biāo)值。

2.1 調(diào)度解編碼解碼方式

以10訂單和3預(yù)制構(gòu)件工廠的問題為例，如圖3所示，從區(qū)間[1,F]隨機生成n個數(shù)字作為解的第一層，從區(qū)間[1,n]生成n個不重復(fù)的數(shù)字作為解的第二層。一層編號為 (1, 2, 1, 3, 2, 3, 1, 2, 3, 2)表示訂單到工廠的指派方案，二層編號為 (8, 7, 3, 2, 5, 6, 10, 1, 9, 4)。即訂單 (8, 3, 10) 被分配至工廠1處理；訂單 (7, 5, 1, 4) 被分配至工廠2處理；訂單 (2, 6, 9) 被分配至工廠3處理。訂單在廠內(nèi)的處理順序如括號內(nèi)從左到右所示，如此確定了訂單在不同工廠間的指派方案以及生產(chǎn)調(diào)度方案。

圖3 編碼示意圖

2.2 初始化“班級”群體

為了避免隨機方式產(chǎn)生的初始解群體質(zhì)量較差，設(shè)計了一種啟發(fā)式策略，即按各訂單交貨期排序，再將每個待加工訂單依次分配至各工廠，基于該策略生成一個班級個體，其余班級個體通過隨機方式生成。通過啟發(fā)式規(guī)則和隨機生成融合策略提升初始解的質(zhì)量，來增加算法的尋優(yōu)效率。

2.3 教學(xué)階段

在教學(xué)階段，結(jié)合問題模型雙層編碼結(jié)構(gòu)的特點，設(shè)計了兩種學(xué)習(xí)策略，通過讓班級中每個學(xué)生個體隨機選擇兩種學(xué)習(xí)策略中的一個與教師進行信息交互，提高班級學(xué)生的成績。兩種學(xué)習(xí)策略內(nèi)容如下：

圖4 頂層替換

圖5 底層替換

2.4 學(xué)生階段

2.4.1 相互學(xué)習(xí)

將學(xué)生個體兩兩隨機配對，進行與教學(xué)階段相同的信息交互操作，若得到的解質(zhì)量比相互學(xué)習(xí)前更好則更新學(xué)生個體。

2.4.2 自我學(xué)習(xí)

本文結(jié)合問題模型的特點，設(shè)計了兩種自我學(xué)習(xí)過程：

1) 如圖6所示，將每個學(xué)生個體Xi取出，通過變異算子在解的第一層隨機選取兩個位置點，然后從[1,F]內(nèi)隨機產(chǎn)生和選取點不一樣的值進行替換，從而改變訂單在工廠間的指派。

圖6 變異算子

2) 如圖7所示，將每個學(xué)生個體Xi取出，通過交叉算子在解中隨機選取兩個位置點，將兩位置點一二層包含的元素整層互換，從而改變訂單的生產(chǎn)調(diào)度排序。

圖7 交叉算子

2.5 參數(shù)設(shè)置

為了評估DTLBO算法的性能，將其與生產(chǎn)調(diào)度領(lǐng)域常用的智能算法GA[19]和VNS[20]作對比。公平起見，3種算法的終止準(zhǔn)則統(tǒng)一設(shè)置為最大運行時間t=n*6/10。需要調(diào)節(jié)的參數(shù)為DTLBO的種群大小 (pop)，以及GA算法的種群大小 (pop)、交叉率 (pc) 和變異率 (pm)。參數(shù)調(diào)整結(jié)果如下：

1) DTLBO：pop=100；

2) GA：pop=80，pc=0.9，pm=0.1。

3 分布式預(yù)制生產(chǎn)調(diào)度系統(tǒng)

3.1 系統(tǒng)原理

分布式預(yù)制生產(chǎn)調(diào)度系統(tǒng)的原理是：先將設(shè)定好的算法導(dǎo)入上位機，上位機接收到來自客戶的訂單信息，包括訂單數(shù)量、構(gòu)件類型、交貨期以及各類型構(gòu)件延期交付的懲罰費用；然后上位機根據(jù)訂單信息計算出最佳的訂單指派和調(diào)度方案；最后通過下位機將調(diào)度方案顯示反饋給生產(chǎn)管理人員，管理人員依據(jù)給出的調(diào)度序列控制各預(yù)制構(gòu)件訂單的開工時間完成調(diào)度工作。

圖8 系統(tǒng)原理圖

3.2 調(diào)度過程

以2.1節(jié)給出的10訂單調(diào)度解為例，首先對其進行解碼，得出最終可指導(dǎo)實際生產(chǎn)的調(diào)度方案，如表2所示。

表2 調(diào)度方案

根據(jù)該調(diào)度方案將各訂單依次指派到對應(yīng)的工廠按序加工處理。以工廠1為例，首先在工序1上處理訂單8，由式(5)～式(7)計算訂單8在工序1上的完成時間，并作為其緊后處理的訂單3在工序1上的開工時間，再通過式(5)～(7)計算訂單3在工序1上的完成時間，依次類推計算得出預(yù)制工廠1內(nèi)生產(chǎn)調(diào)度序列 (8 3 10) 內(nèi)所有訂單在1～6工序上的最佳開工時間、完工時間。生產(chǎn)管理者通過控制各訂單的開工時間完成對訂單的生產(chǎn)調(diào)度，并且已知各訂單最終的完工時間和各訂單的交貨期，帶入目標(biāo)函數(shù)式(1)即可算出總訂單拖期懲罰費用。圖9為廠1內(nèi)預(yù)制構(gòu)件訂單生產(chǎn)調(diào)度甘特圖，該圖反應(yīng)了經(jīng)算法優(yōu)化后的各訂單在每道工序上的最佳開工時間及完工時間。

圖9 生產(chǎn)調(diào)度甘特圖

4 仿真實驗與結(jié)果分析

實驗通過Matlab 2018b編程實現(xiàn)，計算機配置為Microsoft Windows 10，處理器為Intel Core i5-9400F CPU @ 2.9 GHz/8 GB RAM。通過不同規(guī)模下的算例實驗，對各算法求解分布式預(yù)制構(gòu)件調(diào)度問題時的魯棒性和求解性能進行比較分析。

4.1 測試實例

如表3所示，每種類型訂單各工序的處理時間取自Brandimarte等[21]文獻中的標(biāo)準(zhǔn)數(shù)據(jù)，訂單的單位時間拖期懲罰系數(shù)βi∈{10,20}，問題實例的交貨日期di在區(qū)間[PT‘n,3*n]均勻分布生成，PT為所有訂單處理時間的累加和。實驗中設(shè)定預(yù)制構(gòu)件工廠數(shù)量為3，考慮了20、30和50三種待調(diào)度訂單數(shù)量，在每種數(shù)量規(guī)模下測試了5個問題實例，每個問題實例運行20次，記錄20次運行取得目標(biāo)值的最小值 (Min) 、平均值 (Avg)和標(biāo)準(zhǔn)差 (Std)。

表3 訂單生產(chǎn)信息

4.2 算法性能對比分析

為了直觀地比較3種算法性能的優(yōu)劣。本文采用相對偏差率(RPD，relative percentage deviation)來評估各算法的性能。計算公式如下：

(11)

(12)

4.3 實驗結(jié)果分析

表4記錄了各算法在計算20、30和50三種不同待調(diào)度訂單數(shù)量問題實例下得出的最小RPD值、平均RPD值和Std值。為了便于區(qū)分，對同一個問題實例各算法得出的最小RPD值用粗體表示，最小平均RPD值用粗斜體表示，最小Std值用斜體表示。

從表4可以看出，實驗測試了不同訂單規(guī)模下的15個算例，對于各算例下的最佳平均RPD值和最小RPD值，均由DTLBO算法取得。各算例最小的Std值，DTLBO算法取得了14個。圖10是3種算法在求解不同訂單規(guī)模問題時的ARPD值對比圖，可以看出在3種訂單數(shù)量問題下，本文提出的DTLBO算法均取得了最佳ARPD值。即表明，與GA和VNS相比，提出的DTLBO算法具有更好的求解性能和魯棒性。

表4 實驗測試結(jié)果對比

圖10 各訂單數(shù)量的平均偏差率圖

以30訂單規(guī)模下的算例5為例，圖11為3種算法的迭代收斂曲線，可以看出DTLBO算法不僅有較好的求解質(zhì)量，且收斂速度最快。

圖11 收斂曲線

4.4 與啟發(fā)式調(diào)度方法對比

傳統(tǒng)預(yù)制構(gòu)件企業(yè)通常采用基于經(jīng)驗的啟發(fā)式調(diào)度方法：即先將訂單按交貨期的早晚排序，基于貪婪的思想將交貨期早的訂單置于調(diào)度序列的前部，先進行加工處理，如此依次將各個訂單分配置所有工廠內(nèi)，得出調(diào)度方案。

為了驗證本文提出算法的實際應(yīng)用價值，表5統(tǒng)計了3種訂單規(guī)模下分別通過DTLBO算法和啟發(fā)式調(diào)度方法計算得出的平均目標(biāo)值，DTLBO算法較啟發(fā)式調(diào)度方法在目標(biāo)值上的改進率分別為11.2%、10.8%和12.4%。可以看出，使用DTLBO算法提供的調(diào)度方案可以為企業(yè)有效降低訂單拖期懲罰費用成本，增加預(yù)制構(gòu)件制造企業(yè)凈收益。

表5 不同訂單規(guī)模下DTLBO算法的改進率

5 結(jié)束語

本文針對分布式預(yù)制構(gòu)件流水車間調(diào)度問題，以最小化訂單總拖期懲罰為目標(biāo)構(gòu)建了非線性整數(shù)規(guī)劃數(shù)學(xué)模型，并根據(jù)模型特點設(shè)計了雙層整數(shù)編碼形式，最后提出了一種離散教與學(xué)優(yōu)化算法(DTLBO)應(yīng)用于求解該問題。通過大量仿真實驗，從最優(yōu)RPD值、平均RPD值和Std值3個性能指標(biāo)與VNS算法和GA算法對比分析，結(jié)果驗證了提出的DTLBO算法在求解分布式預(yù)制構(gòu)件流水車間調(diào)度問題時的有效性和可行性。在下一步研究中，可以將機器故障、臨時訂單等突發(fā)情形集成到調(diào)度問題中進行求解。