考慮設(shè)備布局的智能車(chē)間生產(chǎn)任務(wù)動(dòng)態(tài)分配方法

丁 凱，羅 丹，張旭東

（長(zhǎng)安大學(xué) 工程機(jī)械學(xué)院智能制造系統(tǒng)研究所，西安 710064）

0 引言

在智能制造環(huán)境下，智能工廠/車(chē)間內(nèi)的各類(lèi)制造資源擁有自感知、自配置、自控制、自決策、自學(xué)習(xí)等自治智能，各制造資源之間通過(guò)業(yè)務(wù)交互與信息共享，協(xié)作完成產(chǎn)品生產(chǎn)制造任務(wù)[1]。在此背景下，由制造資源開(kāi)展動(dòng)態(tài)生產(chǎn)任務(wù)分配（Production Task Allocation，PTA）是提高智能車(chē)間自治水平和柔性配置能力的關(guān)鍵。

PTA問(wèn)題是根據(jù)訂單交貨期、成本等約束，綜合考慮設(shè)備的加工能力和產(chǎn)能，優(yōu)化安排加工任務(wù)序列的問(wèn)題。PTA是車(chē)間按時(shí)完成加工任務(wù)的關(guān)鍵，且PTA方案需依據(jù)車(chē)間動(dòng)態(tài)需求進(jìn)行自適應(yīng)調(diào)整。不合理的PTA將導(dǎo)致設(shè)備能力不均衡、生產(chǎn)成本提高、交貨期拖延等問(wèn)題。近年來(lái)，國(guó)內(nèi)外學(xué)者圍繞PTA問(wèn)題開(kāi)展了較多研究。Cheng等[2]從問(wèn)題描述與建模、執(zhí)行過(guò)程分析、算法設(shè)計(jì)與選擇、決策優(yōu)化與仿真、任務(wù)執(zhí)行等角度，綜述了當(dāng)前PTA問(wèn)題的研究進(jìn)展；Li和Mo[3]提出了一種基于多屬性評(píng)價(jià)的生產(chǎn)任務(wù)隊(duì)列優(yōu)化方法，根據(jù)任務(wù)屬性建立了層次多屬性模型，給出了指標(biāo)量化方法；李益兵等[4]綜合考慮生產(chǎn)成本、加工資源、加工效率等多個(gè)因素，建立集團(tuán)分布式制造資源配置優(yōu)化模型，并采用基于Logistic混沌改進(jìn)的遺傳算法求解該模型的Pareto最優(yōu)解；Zhang等[5]建立了基于CPS和IIoT的智能生產(chǎn)-物流系統(tǒng)框架，并研究了制造資源建模和自組織配置機(jī)制；Hu和Chen[6]研究了人機(jī)協(xié)同制造系統(tǒng)的任務(wù)優(yōu)化分配問(wèn)題，并應(yīng)用線性規(guī)劃方法實(shí)現(xiàn)最佳聯(lián)合系統(tǒng)性能；Li等[7]提出了云制造環(huán)境下資源分配模型，并針對(duì)三個(gè)優(yōu)化目標(biāo)提出了三種子任務(wù)調(diào)度策略；Chu 等[12]提出一種基于知識(shí)的模糊綜合評(píng)價(jià)方法，解決了航空結(jié)構(gòu)件生產(chǎn)車(chē)間的制造任務(wù)分配問(wèn)題。

上述研究從不同角度開(kāi)展了PTA問(wèn)題的研究，但較少考慮制造資源的自主性和任務(wù)分配的動(dòng)態(tài)自適應(yīng)能力。本文將工件在設(shè)備之間的流轉(zhuǎn)（即工序流）視為馬爾科夫隨機(jī)過(guò)程，提出一種改進(jìn)的最大熵馬爾可夫模型，并引入特征函數(shù)并進(jìn)行參數(shù)訓(xùn)練，構(gòu)建了考慮車(chē)間設(shè)備布局的生產(chǎn)任務(wù)動(dòng)態(tài)分配模型。

1 問(wèn)題建模

假設(shè)某智能車(chē)間有N臺(tái)機(jī)床，包括車(chē)床、銑床和車(chē)銑復(fù)合加工中心三種類(lèi)型，主要加工的工件包含H類(lèi)，所有類(lèi)型工件的工序總和為M個(gè)。其中：具有同種加工特征、不同加工參數(shù)的工序視為同類(lèi)工序，如：粗車(chē)外圓90和粗車(chē)外圓65均為“粗車(chē)外圓”工序。智能車(chē)間生產(chǎn)任務(wù)動(dòng)態(tài)分配問(wèn)題即為：在給定的設(shè)備布局約束下，如何根據(jù)零件工藝規(guī)劃流程和歷史加工記錄，動(dòng)態(tài)設(shè)定當(dāng)前工件每一道工序所在的機(jī)床，形成動(dòng)態(tài)機(jī)床序列。

本文將車(chē)間設(shè)備布局視為影響條件概率的因素，改進(jìn)了傳統(tǒng)的最大熵模型結(jié)構(gòu)，將智能車(chē)間生產(chǎn)任務(wù)動(dòng)態(tài)分配問(wèn)題抽象為考慮設(shè)備布局的最大熵馬爾可夫模型（Layoutbased Maximum Entropy Markov Model，L_MEMM），如式(1)所示：

其中：

I——與工件加工工序?qū)?yīng)的機(jī)床序列，為隱含狀態(tài)鏈，I i∈Y，Y={y1，y2，...yn}，Y表示智能車(chē)間擁有的機(jī)床集合。車(chē)間接到新的生產(chǎn)任務(wù)后，可由工件圖紙生成加工工序流，但與工序流對(duì)應(yīng)的機(jī)床序列是事先不可觀測(cè)的；

D——機(jī)床之間的距離矩陣。D=[dij]1×N，dij表示第i號(hào)機(jī)床到第j號(hào)機(jī)床的距離；

O——工件的加工工序序列，為可見(jiàn)狀態(tài)鏈，Oi∈V，V={v1，v2，...vn}，V表示智能車(chē)間歷史加工工件包含的所有加工工序集合；

P——滿足信息熵最大約束時(shí)的三元條件概率，即：在當(dāng)前工序?yàn)镺t、前一道工序所處的機(jī)床編號(hào)為It-1、由前一道工序運(yùn)輸?shù)疆?dāng)前工序的距離最小為的條件下，當(dāng)前工序Ot被分配至機(jī)床It進(jìn)行加工的概率P(It｜It-1，Ot，Dt)。

圖1 考慮設(shè)備布局的最大熵馬爾科夫模型

L_MEMM模型中最終得到的指數(shù)分布Pyi-1(y1IxI)，在引入物流距離D之后變量x和y有了新的含義，變量x表示工件的加工工序序列，變量y表示在時(shí)間上與工序?qū)?yīng)的工件所處的機(jī)床序列，則條件概率分布P可由以下公式計(jì)算：

矩陣中Pij表示工件的第一道工序?yàn)関i且該工序所處的機(jī)床為yj的概率。

考慮設(shè)備布局的智能車(chē)間生產(chǎn)任務(wù)分配問(wèn)題對(duì)工件當(dāng)前工序、前一道工序所處機(jī)床以及當(dāng)前工序所處的機(jī)床等信息非常敏感，需要將傳統(tǒng)的MEMM模型中的原始特征函數(shù)重新定義如式(5)所示：

特征函數(shù)定義為一個(gè)二值函數(shù)，這種特征能夠捕獲特定工序在滿足特征函數(shù)的條件下工件所處機(jī)床的傾向，如果上述定義中特征fα(.)對(duì)應(yīng)的權(quán)重ωα為較大正值，就表示在滿足特征函數(shù)的條件下，當(dāng)前工序oi有較大概率在機(jī)床yi上加工，則最佳的物流路徑即為上一道工序所在機(jī)床yi-1到當(dāng)前工序所在的機(jī)床yi。

2 算法求解

2.1 模型訓(xùn)練

采用迭代尺度算法對(duì)模型進(jìn)行訓(xùn)練，具體步驟如下：

3）計(jì)算每個(gè)特征函數(shù)的樣本期望Eα：

4）迭代計(jì)算：

5）設(shè)置迭代結(jié)束條件：

若滿足條件5），結(jié)束迭代并輸出權(quán)重ωα(α=1,2...,m)，否則返回步驟2）。

訓(xùn)練結(jié)束后得到每個(gè)特征對(duì)應(yīng)的權(quán)重，代入最大熵模型的解即可獲得滿足約束條件的條件概率分布P(It｜It-1，Ot)。

2.2 生產(chǎn)任務(wù)分配預(yù)測(cè)

以工件加工工序序列為輸入，采用Viterbi算法對(duì)工序序列對(duì)應(yīng)的機(jī)床序列進(jìn)行預(yù)測(cè)。生產(chǎn)任務(wù)動(dòng)態(tài)分配問(wèn)題本質(zhì)上是一個(gè)動(dòng)態(tài)規(guī)劃求概率最大路徑問(wèn)題，一條物流路徑與一條機(jī)床序列相對(duì)應(yīng)。本文建立的模型為概率模型，根據(jù)動(dòng)態(tài)規(guī)劃原理，最優(yōu)的路徑具有以下特性：如果工件在t時(shí)刻通過(guò)機(jī)床那么這一方案中從機(jī)床到終點(diǎn)機(jī)床的部分序列，對(duì)于從的所有可能的部分序列來(lái)說(shuō)是最優(yōu)的。

定義變量δ、ψ，定義工件進(jìn)行到第t道工序時(shí)處于機(jī)床i的所有可能的方案i1，i2，...it中最有可能出現(xiàn)的機(jī)床序列，其概率由式(10)計(jì)算：

由定義可得δ的遞推公式如式(11)所示：

定義工件加工進(jìn)行到第t道工序時(shí)處于機(jī)床i的所有可能的分配方案（i1，i2，...，it-1，i）中，最有可能出現(xiàn)的機(jī)床序列，其第t-1個(gè)機(jī)床由式(12)計(jì)算得到：

從第一道工序t=1開(kāi)始，遞推計(jì)算在第t道工序工件處于機(jī)床i的各分配方案部分序列的最大概率，直至得到最后一道工序t=T時(shí)工件處于機(jī)床i的所有可能方案的最大概率，最后一道工序t=T的最大概率即為最佳的生產(chǎn)任務(wù)分配方案出現(xiàn)的概率P*，最優(yōu)方案的終點(diǎn)機(jī)床也同時(shí)得到，從終點(diǎn)機(jī)床開(kāi)始，由后向前逐步求得前一道工序所處的機(jī)床最終得到與工序序列相匹配的最大概率的生產(chǎn)任務(wù)分配方案

3 案例研究

某智能車(chē)間共有8臺(tái)機(jī)床，其中：a、b為普通車(chē)床，c為數(shù)控車(chē)床，d、e、f為數(shù)控銑床，g、h為車(chē)銑復(fù)合加工中心，各機(jī)床之間的物流距離矩陣D如式(13)所示：

該車(chē)間當(dāng)前待加工工件包括傳動(dòng)軸、法蘭端蓋、法蘭盤(pán)和閥蓋。為便于表達(dá)，將各工件的加工工序編碼如表1所示。

表1 加工特征編號(hào)

將工件加工工序進(jìn)行編碼，形成四類(lèi)工件的加工工序序列O：

將由車(chē)間歷史數(shù)據(jù)構(gòu)成的訓(xùn)練集數(shù)據(jù)輸入到模型訓(xùn)練算法中，模型包含的特征由訓(xùn)練數(shù)據(jù)直接提取，特征格式如式(14)所示。

式(14)表示前一道工序在機(jī)床c上加工，當(dāng)前工序?yàn)榫?chē)外圓，在除機(jī)床c外的所有機(jī)床中，機(jī)床a與機(jī)床c的物流距離最短，且當(dāng)前工序在機(jī)床a上進(jìn)行加工。掃描訓(xùn)練集后得到上述形式的特征函數(shù)72個(gè)，每個(gè)特征對(duì)應(yīng)權(quán)重的訓(xùn)練結(jié)果如圖2所示。

圖2 算法訓(xùn)練權(quán)重結(jié)果

由于矩陣規(guī)模較大，本文只給出部分結(jié)果如式(16)所示

將得到的模型最優(yōu)參數(shù)與預(yù)測(cè)目標(biāo)序列O代入Viterbi算法，計(jì)算后得到與四類(lèi)工件的加工工序序列相對(duì)應(yīng)的四條機(jī)床序列如式(17)所示：

4 討論分析

以傳動(dòng)軸為例對(duì)預(yù)測(cè)結(jié)果進(jìn)行分析，L_MEMM模型預(yù)測(cè)得到的結(jié)果為：a→d→c→d→b→c→a→c→f，而根據(jù)車(chē)間內(nèi)各類(lèi)機(jī)床的加工能力和物理布局得出的理論最優(yōu)的物流路徑為：a→d→b→d→b→c→a→c→f。通過(guò)對(duì)比發(fā)現(xiàn)，只有第三道工序?qū)?yīng)的預(yù)測(cè)結(jié)果與理論結(jié)果之間存在偏差，但是普通車(chē)床b與數(shù)控車(chē)床c都能滿足第三道工序車(chē)削端面，而數(shù)控車(chē)床c與上一道工序所在的機(jī)床d之間的物流距離最短，故預(yù)測(cè)結(jié)果可靠。

進(jìn)一步地，本文以平均絕對(duì)誤差（Mean Absolute Error，MAE）及均方根誤差（Root Mean Square Error，RMSE）作為預(yù)測(cè)結(jié)果準(zhǔn)確率的評(píng)價(jià)指標(biāo)：

式中：N表示實(shí)驗(yàn)次數(shù)，表示實(shí)際的機(jī)床序列，表示預(yù)測(cè)得到的機(jī)床序列，T表示工件加工工序數(shù)量。因此，MAE和RMSE描述的是對(duì)于同一工件的加工工序序列，模型預(yù)測(cè)得到的機(jī)床序列與實(shí)際機(jī)床序列的偏差度量，其數(shù)值越小說(shuō)明預(yù)測(cè)結(jié)果越準(zhǔn)確。

本文給出L_MEMM與傳統(tǒng)的隱馬爾可夫模型（Hidden Markov Model，HMM）之間的預(yù)測(cè)結(jié)果對(duì)比如表2和表3示所示。

表2 MAE值對(duì)比（T=10）

表3 RMSE值對(duì)比（T=10）

由實(shí)驗(yàn)結(jié)果可知，隨著工序數(shù)量的增加，L_MEMM模型預(yù)測(cè)準(zhǔn)確性更好，原因是L_MEMM以一個(gè)條件概率分布替換了HMM的狀態(tài)轉(zhuǎn)移概率分布和觀測(cè)概率分布，更符合智能車(chē)間生產(chǎn)任務(wù)動(dòng)態(tài)分配的實(shí)際情況。

5 結(jié)語(yǔ)

本文研究了一種考慮設(shè)備布局的最大熵馬爾科夫模型來(lái)解決智能車(chē)間生產(chǎn)任務(wù)動(dòng)態(tài)分配問(wèn)題。該方法依據(jù)歷史生產(chǎn)任務(wù)數(shù)據(jù)進(jìn)行特征自提取，在遵循最大 模型框架下進(jìn)行模型訓(xùn)練。案例表明，該方法改進(jìn)了HMM模型的固有缺陷，為智能車(chē)間制造任務(wù)動(dòng)態(tài)分配預(yù)測(cè)提供了方法。由于智能車(chē)間生產(chǎn)執(zhí)行過(guò)程是一個(gè)相當(dāng)復(fù)雜的過(guò)程，后續(xù)工作需要進(jìn)一步考慮車(chē)間實(shí)時(shí)生產(chǎn)環(huán)境數(shù)據(jù)等在生產(chǎn)任務(wù)動(dòng)態(tài)分配中的影響。