曹勁松，熊福力

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

0 引言

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

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

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

1 問(wèn)題描述與建模

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

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

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

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

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

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

基于以上符號(hào)和假設(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ù)最小化訂單總拖期懲罰費(fèi)用；式(2)確保每個(gè)訂單被指派到某一工廠中；式(3)和式(4)表示訂單j是否和訂單i指派到同一工廠，且訂單j是否在訂單i緊后加工；式(5)表示訂單在工序上的處理時(shí)間不早于上一訂單在此工序上的完工時(shí)間，第4道工序蒸汽養(yǎng)護(hù)為并行處理過(guò)程，不需滿足此約束；式(6)表示訂單在工序上的開(kāi)始處理時(shí)間不早于該訂單上一工序的完工時(shí)間；式(7)為并行工序完工時(shí)間的計(jì)算公式；式(8)定義了決策變量的取值范圍。

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

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

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

圖2 DTLBO算法框圖

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

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

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

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

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

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

圖3 編碼示意圖

2.2 初始化“班級(jí)”群體

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

2.3 教學(xué)階段

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

圖4 頂層替換

圖5 底層替換

2.4 學(xué)生階段

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

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

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

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

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

圖6 變異算子

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

圖7 交叉算子

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

為了評(píng)估DTLBO算法的性能，將其與生產(chǎn)調(diào)度領(lǐng)域常用的智能算法GA[19]和VNS[20]作對(duì)比。公平起見(jiàn)，3種算法的終止準(zhǔn)則統(tǒng)一設(shè)置為最大運(yùn)行時(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)入上位機(jī)，上位機(jī)接收到來(lái)自客戶的訂單信息，包括訂單數(shù)量、構(gòu)件類(lèi)型、交貨期以及各類(lèi)型構(gòu)件延期交付的懲罰費(fèi)用；然后上位機(jī)根據(jù)訂單信息計(jì)算出最佳的訂單指派和調(diào)度方案；最后通過(guò)下位機(jī)將調(diào)度方案顯示反饋給生產(chǎn)管理人員，管理人員依據(jù)給出的調(diào)度序列控制各預(yù)制構(gòu)件訂單的開(kāi)工時(shí)間完成調(diào)度工作。

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

3.2 調(diào)度過(guò)程

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

表2 調(diào)度方案

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

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

4 仿真實(shí)驗(yàn)與結(jié)果分析

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

4.1 測(cè)試實(shí)例

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

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

4.2 算法性能對(duì)比分析

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

(11)

(12)

4.3 實(shí)驗(yàn)結(jié)果分析

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

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

表4 實(shí)驗(yàn)測(cè)試結(jié)果對(duì)比

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

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

圖11 收斂曲線

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

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

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

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

5 結(jié)束語(yǔ)

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