貴金屬材料加工的排產(chǎn)調(diào)度算法

□ 馬峰超 □ 任仕偉 □ 陳 進 □ 陳 宇

江南大學(xué)機械工程學(xué)院 江蘇無錫 214122

1 研究背景

與一般離散型加工過程相比，貴金屬材料加工還有熔煉、機加工、初切、退火等工序，加工過程復(fù)雜。貴金屬材料加工過程通常如下：首先將訂單任務(wù)材料相同的集中在一起熔煉，需要制訂爐次計劃；熔煉之后，根據(jù)不同訂單任務(wù)的工藝路線進行加工，包括機加工、初切、退火、分剪、軋制、沖壓、檢驗和包裝等，需要制訂加工計劃。由于缺乏系統(tǒng)的理論和排產(chǎn)方法作為指導(dǎo)，計劃員常常依靠經(jīng)驗制訂爐次計劃和加工計劃，因此產(chǎn)生了一系列問題：①爐次計劃制訂不合理，熔煉能力沒有充分利用，資源過度浪費；②分剪計劃不合理，材料過度損耗；③生產(chǎn)計劃不合理，制造過程混亂，延誤交貨期；④設(shè)備利用率低。

為解決上述問題，一般有效的方法是對生產(chǎn)調(diào)度方法進行優(yōu)化，涉及到的算法主要有遺傳算法、進化算法、粒子群算法等［1-7］。但由于貴金屬材料加工工藝具有特殊性，生產(chǎn)過程復(fù)雜，常規(guī)的生產(chǎn)調(diào)度方法已無法滿足實際需求。在解決爐次計劃的相關(guān)問題時，唐立新等［8］為解決煉鋼連鑄計劃與調(diào)度中的爐次計劃問題，構(gòu)建了一個最優(yōu)爐次計劃的混合整數(shù)規(guī)劃數(shù)學(xué)模型；張健欣等［9］建立了融合多目標(biāo)的數(shù)學(xué)模型，用于解決煉鋼連鑄熱軋一體化生產(chǎn)的爐次計劃問題；王闖等［10］采用改進后的單親遺傳算法解決爐次計劃問題，通過對比分析，驗證了算法的有效性；馬天牧等［11］提出了將變鄰域搜索算法作為迭代局部搜索算法中局部搜索的混合算法；薛云燦等［12］針對爐次數(shù)未知的煉鋼連鑄一體化生產(chǎn)問題，提出了組爐模型，并將其作為偽旅行商問題來處理，采用離散粒子群優(yōu)化算法求解。可見，爐次計劃在煉鋼和熱處理過程中行之有效，且取得了不少研究成果，但是針對貴金屬熔煉爐次計劃的研究仍比較少。

針對貴金屬材料加工過程，筆者研究的排產(chǎn)方法集成了爐次計劃和加工計劃，形成了完整的排產(chǎn)調(diào)度算法［13-14］。具體實施過程為：結(jié)合工藝路線與多種參數(shù)的實際意義，基于啟發(fā)式算法基本原理與極大極小代數(shù)法思想，建立一種融合多目標(biāo)評價參數(shù)的數(shù)學(xué)模型，通過優(yōu)化計算可以得到訂單的評價指標(biāo)；根據(jù)評價指標(biāo)，通過迭代計算可以得到爐次計劃；依據(jù)評價指標(biāo)的優(yōu)先順序可以得到訂單的加工優(yōu)先順序，安排加工計劃。通過排產(chǎn)方法的應(yīng)用，理論上可以為全部訂單安排生產(chǎn)計劃，在保證全部訂單有序、高效完成生產(chǎn)的同時，能夠規(guī)范生產(chǎn)過程，降低熔煉費用，保證交貨期。通過實際案例對這一排產(chǎn)調(diào)度算法進行了驗證，證實了算法的實用性，對貴重金屬材料排產(chǎn)調(diào)度方法的研究具有借鑒意義。

2 算法介紹

2.1 變量定義

j為訂單編號， j=1，2，...，a。 k 為設(shè)備編號，k=1，2，...，b。

T 為任務(wù)加工時間矩陣，T=［tjk］a×b，矩陣元素 tjk為訂單編號j在設(shè)備k上的加工時間與準(zhǔn)備時間之和，當(dāng)訂單j不在設(shè)備k上加工時，tjk為0。

R 為工藝路徑矩陣，R=［rjk］a×b，矩陣元素 rjk為訂單編號j在加工工藝路徑中設(shè)備k所處的順序，訂單編號j不需要在設(shè)備k上進行加工時，rjk為+∞，R即為全部訂單的工藝路線。由工藝路徑矩陣引出的工藝函數(shù)為r（j，k）=O，O為訂單 j在設(shè)備 k所處的加工工藝路線中的加工順序號。定義設(shè)備反求函數(shù)E（j，rjk）=k，則知道訂單編號和加工順序號后，可以通過設(shè)備反求函數(shù)得到加工設(shè)備。

X為開工時間矩陣，xjkl為設(shè)備k對訂單編號為j且熔爐號為l的訂單的加工活動的計劃開始時間。

Y為完工時間矩陣，yjkl為設(shè)備k對訂單編號為j且熔爐號為l的訂單的加工活動的計劃完成時間。

j為設(shè)備k在訂單j到達前剛剛加工過的訂單。k為訂單j在到達設(shè)備k前剛剛用過的設(shè)備。

設(shè)置如下假設(shè)條件：在同一熔爐中熔煉的訂單具有相同的配方，一個爐次中訂單的熔煉、機加工、初切、退火具有相同的工藝。

2.2 算法建模

貴金屬材料加工過程復(fù)雜，不僅要保證交貨期，而且要保證設(shè)備有較高的利用率，提高排產(chǎn)效率，特別是要充分利用熔爐的熔煉能力。經(jīng)過反復(fù)建模和試驗驗證，構(gòu)建計算量小、計算時間短、優(yōu)化效果好的啟發(fā)式目標(biāo)函數(shù)作為評判準(zhǔn)則。

式中：h為加工順序號，1≤h≤e，e為訂單j在加工工藝路線中最大的加工順序號；ΔTdj，τ為交貨期與當(dāng)前排產(chǎn)時間的差值，d為常量，τ為當(dāng)前排產(chǎn)時間；yj為優(yōu)先級，yj越小，說明訂單越重要，應(yīng)優(yōu)先考慮排產(chǎn)；mj為訂單需要用到的材料質(zhì)量，由于是貴金屬材料，因此mj越大，說明訂單價值越大，應(yīng)優(yōu)先進行排產(chǎn)；ε1、ε2、ε3、ε4為權(quán)重；Qj，k為在設(shè)備k處訂單j具有的評價指標(biāo)，評價指標(biāo)越小，說明訂單的優(yōu)先級越高，應(yīng)優(yōu)先安排生產(chǎn)。

取O=1，即在第一道熔煉工序時，得到全部訂單任務(wù)的評價指標(biāo)，然后從小到大進行排序，i=1，2，3…c，c等價于訂單數(shù)。通過設(shè)備反求函數(shù)可以得到訂單編號，P（i）=j。

熔爐的熔煉能力為W。盡量將評價指標(biāo)相近或者相互連續(xù)的訂單放到一個熔爐中進行熔煉，使熔煉訂單的總質(zhì)量接近W，以達到保證訂單按照優(yōu)先級的先后進行加工，充分利用熔爐的熔煉能力，減少浪費。

爐次計劃步驟如下。

（1）將未排訂單按照評價指標(biāo)從小到大進行排序，第一個序號為1，第二個序號為2，依次類推。排好后如圖1所示開始循環(huán)，圖中M為訂單質(zhì)量的累加。

（2）循環(huán)結(jié)束，將符合條件的訂單合為一爐熔煉，不符合條件的訂單轉(zhuǎn)為未排訂單。

（3） 重復(fù)步驟（1）、（2），直至所有訂單完成。

（4） 計算熔爐的評價指標(biāo) Φl，o，并從小到大進行排序。Φl，o越小，表明優(yōu)先級越高，應(yīng)優(yōu)先進行熔煉。

式中：l為當(dāng)前熔爐編號，q（j）=l表示訂單 j在熔爐 l中熔煉；n為熔爐l在一次熔煉計劃中熔煉的訂單數(shù)量。

（5）輸出爐次計劃。

2.3 變量賦值

▲圖1 爐次計劃原理

在一個熔爐中熔煉的訂單具有相同的熔煉、機加工、初切和退火時間，加工時間上的差異體現(xiàn)在分剪、精軋、沖壓和檢驗包裝方面。訂單一般包含很多個相同規(guī)格的產(chǎn)品，為了簡化描述過程，將訂單作為整體來進行討論。

訂單的熔煉、機加工、初切、退火是流程性生產(chǎn)，過程比較單一，筆者不做討論，著重討論分剪、精軋、沖壓、檢驗包裝。對于訂單j將要在設(shè)備k上加工，分四種情況。

（1）訂單j上一道工序未完成，設(shè)備k當(dāng)前有任務(wù)，訂單j在設(shè)備k上的開始加工時間為訂單j上一道工序的結(jié)束時間與設(shè)備k加工完成當(dāng)前訂單時間中的大值，即：

（2）訂單j上一道工序完成，設(shè)備k當(dāng)前有任務(wù)，訂單j在設(shè)備k上的開始加工時間為設(shè)備k加工完成當(dāng)前訂單的時間，即：

“噬菌體侵染細菌的實驗”是人教版“高中生物學(xué)”《必修2·遺傳與進化》第三章第一節(jié)的教學(xué)難點。要徹底理解這部分的內(nèi)容，學(xué)生不僅需要對科學(xué)史有一定了解，還需要具備一定的分析對比、綜合提煉的能力。除此之外，學(xué)生還需要具備一定的空間想象能力，能想象出噬菌體的形態(tài)特點等。這給學(xué)生帶來不小的學(xué)習(xí)障礙。學(xué)生在學(xué)習(xí)過程中經(jīng)常存在以下的困惑：①利用放射性同位素32P和35S分別標(biāo)記的是噬菌體的什么物質(zhì)？②噬菌體侵染細菌的過程具體是怎樣的？③為什么上清液和沉淀物的放射性會有不同？

（3）訂單j上一道工序未完成，設(shè)備k當(dāng)前無任務(wù)，訂單j在設(shè)備k上的開始加工時間為訂單j上一道工序的結(jié)束時間，即：

（4）訂單j上一道工序完成，設(shè)備j當(dāng)前無任務(wù)，訂單j在設(shè)備k上的開始加工時間為當(dāng)前時間。

2.4 算法步驟

（1） R、T 根據(jù)已知賦初值，j=1，2，…，a，k=1，2，…，b，X的元素賦初值無窮大。

（2）統(tǒng)計相關(guān)信息，包括訂單j在設(shè)備k上的加工時間及在加工工藝路線中的加工順序號、訂單j的交貨期、訂單j的優(yōu)先級、訂單j所需熔煉原料質(zhì)量。

（3） 利用式（1）計算 Qj，k，得到投料順序，根據(jù)圖1和式（2）計算 Φl，o，得到爐次計劃。

（4） Φl，o越小的訂單，越優(yōu)先進行熔煉；Qj，k越小的訂單，越優(yōu)先進行加工。

（5） 按照優(yōu)先順序從大到小，利用式（3）～式（6）循環(huán)計算開工時間變量xjkl，同時通過公式y(tǒng)jkl=xjkl+tjkl計算輸出完工時間矩陣Y，直到所有訂單中每個工序的開工時間和完工時間均被賦值，計算結(jié)束。

3 算法實例

生產(chǎn)系統(tǒng)由2個熔爐、1臺機加工設(shè)備、1臺初切設(shè)備、1個退火爐、3臺分剪設(shè)備、2臺精軋設(shè)備、2臺沖壓設(shè)備、3臺檢驗包裝設(shè)備組成，人力資源作為設(shè)備來考慮。熔爐的設(shè)備編號為1a、1b，機加工設(shè)備的設(shè)備編號為2，初切設(shè)備的設(shè)備編號為3，退火爐的設(shè)備編號為4，分剪設(shè)備的設(shè)備編號分別為5、6、7，精軋設(shè)備的設(shè)備編號分別為8、9，沖壓設(shè)備的設(shè)備編號分別為10、11，包裝檢驗的設(shè)備編號分別為 12、13、14。

確定任務(wù)加工時間矩陣T和工藝路徑矩陣R，設(shè)定系統(tǒng)的起始時間為0，熔爐的熔煉能力為100 kg，求解訂單的狀態(tài)矩陣和輸出矩陣。

訂單關(guān)系表記中所包含的屬性有訂單號、物料編碼、優(yōu)先級、質(zhì)量、交貨期、Qj，k、投料順序、設(shè)備、開工時間、加工時間、完工時間。現(xiàn)有12個訂單，訂單號、設(shè)備、物料編碼、優(yōu)先級、質(zhì)量、交貨期、加工時間為已知。將訂單號、優(yōu)先級、質(zhì)量、交貨期、加工時間，以及O=1、ε1=1、ε2=1、ε3=10、ε4=0.01 代入式（1），經(jīng)過求解計算，得到 Qj，k。 根據(jù) Qj，k的大小，從小到大進行排序，得到投料順序。

訂單關(guān)系表見表1，表中交貨期無量綱。

表1 訂單關(guān)系表

根據(jù)圖1和式（2），得到爐次計劃，如圖2和圖3所示。熔爐1a安排兩次熔煉，先熔煉編號為8、9、4的訂單，后熔煉編號為 5、11、3、10、12 的訂單。熔爐 1b 安排一次熔煉，熔煉訂單編號為 6、7、2、1。 熔爐 1a、1b 同時開工。

根據(jù)算法，得到全部排產(chǎn)方案，見表2。

圖4為熔爐1a熔煉訂單8、9、4時熔爐的利用率，圖5為熔爐 1a熔煉訂單 5、11、3、10、12 時熔爐的利用率，圖6為熔爐1b熔煉訂單6、7、2、1時熔爐的利用率。由圖4～圖6可見，熔爐1a第一次熔煉時熔爐的利用率達到了92%，熔爐1a第二次熔煉時熔爐的利用率達到了95%，熔爐1b的利用率達到了96%。

訂單在熔煉、機加工、初切、退火完成后，已完成退火但未參加下一步加工的訂單，再按評價指標(biāo)從小到大進行排序，評價指標(biāo)小的先進行排產(chǎn)加工。

表2 排產(chǎn)方案

▲圖2 熔爐1a爐次計劃

▲圖3 熔爐1b爐次計劃

▲圖4 熔爐1a第一次熔煉利用率

▲圖5 熔爐1a第二次熔煉利用率

▲圖6 熔爐1b熔煉利用率

4 結(jié)論

筆者集合了爐次計劃、加工排產(chǎn)、車間調(diào)度等多種需求，首先采用啟發(fā)式算法對所有訂單進行評價排序，得到投料順序；然后在此基礎(chǔ)上結(jié)合熔爐的熔煉能力，得到了爐次計劃；最后得到一整套完整的排產(chǎn)調(diào)度算法。通過這一算法可以確定每個訂單每道工序加工過程中具體的計劃開始時間和計劃結(jié)束時間。

貴金屬材料加工的工藝流程具有熔煉、集中、分剪等特點，用啟發(fā)式算法建立生產(chǎn)運作的數(shù)學(xué)模型，運行速度快，實用性強，優(yōu)化效果明顯。

求解模型融合了多目標(biāo)評價參數(shù)，可以通過改變權(quán)重 ε1、ε2、ε3、ε4的大小， 來調(diào)節(jié)各參數(shù)的權(quán)重比例，達到預(yù)期的排產(chǎn)效果。

筆者提出的排產(chǎn)調(diào)度算法結(jié)合實際情況，在安排訂單高效有序進行生產(chǎn)加工的同時，可以保證訂單交貨期，節(jié)約能源消耗，提高設(shè)備利用率，進而使熔爐的熔煉能力得到充分利用。