基于離散教與學算法的分布式預制流水車間調度研究

曹勁松，熊福力

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

0 引言

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

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

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

1 問題描述與建模

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

圖1 分布式預制構件生產調度系統

1.1 相關假設與參數說明

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

表1 調度模型參數說明

1.2 數學模型

基于以上符號和假設建立數學模型如下：

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

2 離散教與學優化算法

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

針對分布式預制構件流水車間調度該類非線性整數規劃問題，本文在TLBO算法的基礎上提出了一種離散教與學優化算法(DTLBO)，算法步驟如下：

圖2 DTLBO算法框圖

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

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

Step5：將學生個體Xi中目標值最優的個體X*取出與教師解Xt比較，如對應目標值更佳，則將X*替換為Xt；

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

2.1 調度解編碼解碼方式

以10訂單和3預制構件工廠的問題為例，如圖3所示，從區間[1,F]隨機生成n個數字作為解的第一層，從區間[1,n]生成n個不重復的數字作為解的第二層。一層編號為 (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處理。訂單在廠內的處理順序如括號內從左到右所示，如此確定了訂單在不同工廠間的指派方案以及生產調度方案。

圖3 編碼示意圖

2.2 初始化“班級”群體

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

2.3 教學階段

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

圖4 頂層替換

圖5 底層替換

2.4 學生階段

2.4.1 相互學習

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

2.4.2 自我學習

本文結合問題模型的特點，設計了兩種自我學習過程：

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

圖6 變異算子

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

圖7 交叉算子

2.5 參數設置

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

1) DTLBO：pop=100；

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

3 分布式預制生產調度系統

3.1 系統原理

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

圖8 系統原理圖

3.2 調度過程

以2.1節給出的10訂單調度解為例，首先對其進行解碼，得出最終可指導實際生產的調度方案，如表2所示。

表2 調度方案

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

圖9 生產調度甘特圖

4 仿真實驗與結果分析

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

4.1 測試實例

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

表3 訂單生產信息

4.2 算法性能對比分析

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

(11)

(12)

4.3 實驗結果分析

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

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

表4 實驗測試結果對比

圖10 各訂單數量的平均偏差率圖

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

圖11 收斂曲線

4.4 與啟發式調度方法對比

傳統預制構件企業通常采用基于經驗的啟發式調度方法：即先將訂單按交貨期的早晚排序，基于貪婪的思想將交貨期早的訂單置于調度序列的前部，先進行加工處理，如此依次將各個訂單分配置所有工廠內，得出調度方案。

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

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

5 結束語

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