數(shù)據(jù)驅(qū)動(dòng)型的維修任務(wù)分配方法

摘要：采用數(shù)據(jù)驅(qū)動(dòng)方法來解決維修生產(chǎn)環(huán)境中復(fù)雜的任務(wù)分配問題。首先利用多種細(xì)致的量化方法制訂一套詳細(xì)而客觀的評(píng)分系統(tǒng)，然后采用并行計(jì)算環(huán)境下的蒙特卡洛樹搜索來快速搜尋各種有價(jià)值的分配組合方案，最后從探索的樹結(jié)構(gòu)中選擇最佳的方案來完成任務(wù)的分配。該方法不僅使數(shù)據(jù)科學(xué)技術(shù)在實(shí)際生產(chǎn)過程中得到落地，而且還取得了不錯(cuò)的效果。

關(guān)鍵詞：數(shù)據(jù)驅(qū)動(dòng)；大數(shù)定律；余弦定理；馬爾科夫決策過程；蒙特卡洛樹搜索

Keywords：data driven；law of large numbers；cosine theorem；MDP；MCTS

0 引言

通常在數(shù)學(xué)模型的設(shè)計(jì)上，只要數(shù)據(jù)量足夠，就可以用若干個(gè)簡單的模型取代一個(gè)復(fù)雜的模型，這種方法被稱為數(shù)據(jù)驅(qū)動(dòng)方法。該方法在數(shù)據(jù)量不足時(shí)找到的模型可能會(huì)與真實(shí)模型存在一定的偏差，但是在誤差允許的范圍內(nèi)可以認(rèn)為與精確的模型是等效的，這在數(shù)學(xué)上是有根據(jù)的。從原理上講，類似于切比雪夫大數(shù)定律[1]，如公式（1）所示。

其中，X是一個(gè)隨機(jī)變量，E（X）是該變量的數(shù)學(xué)期望值，n是實(shí)驗(yàn)次數(shù)（或者是樣本數(shù)），ε是誤差，δ2是方差。這個(gè)公式的含義是：當(dāng)樣本足夠多時(shí)，一個(gè)隨機(jī)變量和它的數(shù)學(xué)期望值之間的誤差可以任意小。

在今天的IT領(lǐng)域中，越來越多的問題可以用數(shù)據(jù)驅(qū)動(dòng)方法來解決。當(dāng)一個(gè)問題暫時(shí)不能用簡單而準(zhǔn)確的方法解決時(shí)，可以根據(jù)以往的歷史數(shù)據(jù)，構(gòu)造很多近似的模型來逼近真實(shí)情況。2016年谷歌的AlphaGo[2]就是數(shù)據(jù)驅(qū)動(dòng)方法對機(jī)器智能產(chǎn)生作用的最佳案例[1]。

1 理論分析與解決思路

1.1 理論分析

航線工作復(fù)雜多變，如果從任務(wù)序列上來審視，會(huì)發(fā)現(xiàn)對序列上的第n個(gè)任務(wù)如果執(zhí)行了行動(dòng)an（安排了具體的人員），就會(huì)導(dǎo)致整個(gè)團(tuán)隊(duì)的狀態(tài)sn（員工工作量狀態(tài)、人員任務(wù)的匹配狀態(tài)等）發(fā)生了變化，同時(shí)這個(gè)變化后的狀態(tài)sn+1又會(huì)影響到接下來的分配行動(dòng)an+1，那么分配過程就可以用一條狀態(tài)—行動(dòng)鏈條[3]表示（見圖1）。

圖1所示的狀態(tài)序列稱為馬爾科夫鏈，這個(gè)鏈條包含了狀態(tài)和行動(dòng)的依次相互轉(zhuǎn)換。如果用嚴(yán)謹(jǐn)?shù)姆绞奖硎?，策略是一種映射，它將團(tuán)隊(duì)的狀態(tài)sn映射到一個(gè)行動(dòng)集合的概率分布或概率密度函數(shù)上?？梢哉J(rèn)為管理者對每一個(gè)行動(dòng)都有一定的執(zhí)行可能性，且行動(dòng)的評(píng)價(jià)越高，執(zhí)行的概率越大，形式化來說就是在第n個(gè)任務(wù)選擇最優(yōu)的分配行動(dòng)[3]，如公式（2）所示。

1.2 解決思路

1）狀態(tài)的定義方法

把工作團(tuán)隊(duì)看成一個(gè)整體S，這個(gè)S的各個(gè)屬性需要有客觀的量化方法來計(jì)算，主要包括：人員與任務(wù)的匹配程度Sfit、人員默契程度Stacit、人為因素指標(biāo)Shf、人員分配合理程度Slogic等。

2）任務(wù)分配的綜合評(píng)價(jià)方法

屬性指標(biāo)之間關(guān)聯(lián)性較強(qiáng)，為了保證每個(gè)指標(biāo)數(shù)據(jù)都能對評(píng)估有貢獻(xiàn)而不被稀釋，采用非線性綜合評(píng)價(jià)模型[5]，如公式（3）所示。

其中，E為評(píng)估分?jǐn)?shù)，xi為指標(biāo)量化數(shù)值，wi為該指標(biāo)的權(quán)重系數(shù)。任務(wù)分配結(jié)束后計(jì)算各個(gè)屬性的分值，然后匯總評(píng)估該次分配方案的分?jǐn)?shù)。

3）策略好壞的度量方法

現(xiàn)實(shí)中不可能遍歷所有的行動(dòng)，根據(jù)大數(shù)定律啟發(fā)，一個(gè)行動(dòng)的好壞可以由其后產(chǎn)生的所有行動(dòng)樣本期望值來進(jìn)行估計(jì)，并且樣本數(shù)越大越接近真實(shí)值。

2 狀態(tài)屬性的量化方法

2.1 人員與任務(wù)匹配程度指標(biāo)

Sfit指標(biāo)采用余弦定理[6]來量化人員與任務(wù)之間的匹配關(guān)系。具體的計(jì)算過程可以參考筆者另一篇論文《針對大量業(yè)務(wù)數(shù)據(jù)的分析方法》[7]中的人員成分分析內(nèi)容。以該任務(wù)的最優(yōu)人員為基準(zhǔn)，其他人通過計(jì)算向量角的余弦值來表示與任務(wù)的匹配程度。對已經(jīng)完成的任務(wù)分配方案計(jì)算總體匹配程度，如公式（4）所示。

其中，ωc、ωn、ωs分別為重要任務(wù)、普通任務(wù)和簡單任務(wù)在總體匹配程度中所占的比例，且ωc+ωn+ωs=100%。μc、μn、μs分別為所有的重要任務(wù)、普通任務(wù)和簡單任務(wù)的配給人員任務(wù)匹配系數(shù)均值。對于VIP任務(wù)或者非常重要的任務(wù)，計(jì)算時(shí)可以對相應(yīng)的人員任務(wù)匹配系數(shù)進(jìn)行指數(shù)加權(quán)處理，增加系統(tǒng)的“懲罰”力度。

2.2 人員默契程度指標(biāo)

Stacit指標(biāo)與員工之間的歷史合作次數(shù)直接相關(guān)，主要采用3種評(píng)判標(biāo)準(zhǔn)：1）歷史合作次數(shù)np；2）近期合作次數(shù)nr；3）近期連續(xù)合作次數(shù)ns。計(jì)算時(shí)將上述3種數(shù)值和對應(yīng)的權(quán)重相乘求和得到標(biāo)準(zhǔn)化的合作次數(shù)W，然后利用邏輯回歸模型[6]對W進(jìn)行激活處理，得到人員之間的默契程度數(shù)值，最后將各合作人員之間的默契程度數(shù)值取平均值，得到該任務(wù)的人員默契程度數(shù)值，如公式（5）和（6）所示。

其中，α為遺忘系數(shù)（取值小于1.0），β為保持系數(shù)（一般取值等于1.0），γ為強(qiáng)化系數(shù)（取值大于1.0）。w0為判定人員默契的最少合作次數(shù)，該參數(shù)是超參數(shù)，可以依據(jù)現(xiàn)實(shí)情況自行設(shè)置。

2.3 人為因素指標(biāo)

Shf指標(biāo)分析人員的工作強(qiáng)度和間歇時(shí)間兩個(gè)方面的情況。首先，將員工的普通和特殊工作時(shí)長整合為標(biāo)準(zhǔn)的工作時(shí)長Tnorm，然后通過各自的折線函數(shù)F（t）得到工作強(qiáng)度數(shù)值，如圖2所示。間歇情況通過系數(shù)ω對工作強(qiáng)度數(shù)值來進(jìn)行影響，ω為間歇時(shí)間滿足人為因素的程度，如公式（7）和（8）所示。

其中，Q為任務(wù)分配方案中參與人員的人為因素指標(biāo)數(shù)值，對Q中m個(gè)最小值求平均，便得出了該次任務(wù)分配方案的總體人為因素指標(biāo)，其中m的數(shù)值需要遠(yuǎn)小于人員數(shù)量。

2.4 人員分配合理程度指標(biāo)

Slogic指標(biāo)衡量員工是否有充裕時(shí)間完成分配的工作。正常生產(chǎn)過程中，一人同時(shí)負(fù)責(zé)多項(xiàng)任務(wù)或者需要跨多機(jī)位同時(shí)工作是不允許出現(xiàn)的狀況，如果員工工作量序列中出現(xiàn)類似情況，就需要對任務(wù)分配方案進(jìn)行“懲罰”處理。當(dāng)某員工同時(shí)負(fù)責(zé)的任務(wù)個(gè)數(shù)超過設(shè)定的容忍極限值時(shí)，就直接將合理程度Slogic置0.0，若沒有超過就按照超額工作時(shí)長的線性關(guān)系進(jìn)行衰減處理。最后，與人為因素指標(biāo)計(jì)算方法類似，取該次任務(wù)分配人員中合理程度數(shù)值最小的m個(gè)人的均值作為該分配方案的總體合理程度指標(biāo)。

3 任務(wù)分配搜索方法

3.1 搜索原理

任務(wù)分配系統(tǒng)的核心方法是蒙特卡洛樹搜索MCTS[3]，該方法大量使用于博弈類問題[8]。對于那些由于計(jì)算過于復(fù)雜而難以得到解析解或者根本沒有解析解的問題，蒙特卡洛樹搜索是一種有效的求出數(shù)值解的方法。整個(gè)過程包含4個(gè)過程，分別是選擇、擴(kuò)展、仿真和回傳。

在實(shí)際計(jì)算操作過程中，任務(wù)列表按照時(shí)間順序劃分為搜索樹的層級(jí)，每層的節(jié)點(diǎn)就是當(dāng)前任務(wù)分配方法，也叫分配節(jié)點(diǎn)，整個(gè)搜索樹的深度就是需要分配的任務(wù)數(shù)量，廣度就是所有可能的方案數(shù)量，如圖3所示。

按照任務(wù)的順序從整個(gè)搜索樹的根節(jié)點(diǎn)開始往下搜索，根據(jù)ε-greedy算法[3]隨機(jī)生成新的節(jié)點(diǎn)或者選取最優(yōu)的節(jié)點(diǎn)作為子節(jié)點(diǎn)。完成所有任務(wù)分配后，調(diào)用評(píng)估系統(tǒng)對任務(wù)分配方案進(jìn)行打分，最后將該方案所得的分?jǐn)?shù)回傳到搜索樹中經(jīng)過的所有節(jié)點(diǎn)，并計(jì)算更新每個(gè)節(jié)點(diǎn)的回報(bào)收益均值。這種過程持續(xù)執(zhí)行成千上萬次，直到分配的方案分?jǐn)?shù)能夠滿足要求或者搜索次數(shù)達(dá)到設(shè)定的數(shù)值為止。

3.2 實(shí)際應(yīng)用

搜索運(yùn)行過程中會(huì)面臨探索和利用這一對矛盾體[3]。探索是嘗試一些不同的和之前判定得分低的方案，從而增加發(fā)現(xiàn)更好方案的可能性。利用是指利用當(dāng)前已知的情況實(shí)施策略，并把有限的采樣次數(shù)盡可能地用在評(píng)價(jià)高的方案上，從而驗(yàn)證其有效性。

探索和利用是一對矛盾體，當(dāng)計(jì)算總資源一定時(shí)，將更多的資源分配給當(dāng)前表現(xiàn)優(yōu)秀的方案就會(huì)忽略一些有潛力的方案，反之亦然。研究表明，在學(xué)習(xí)初期側(cè)重于探索后期側(cè)重于利用[3]具有不錯(cuò)的效果。本文采用UCT算法[8]來計(jì)算每個(gè)節(jié)點(diǎn)的置信權(quán)重，如公式（9）所示。

4 系統(tǒng)優(yōu)化

為了提高系統(tǒng)的計(jì)算效率、搜索準(zhǔn)確性和泛化能力，需要對上述運(yùn)行流程進(jìn)行優(yōu)化設(shè)計(jì)，以便更好地應(yīng)對紛繁復(fù)雜的實(shí)際生產(chǎn)環(huán)境。

4.1 計(jì)算效率的優(yōu)化

為了提高系統(tǒng)的整體運(yùn)行效率，縮短得到滿意分配方案所花費(fèi)的時(shí)間，采用了數(shù)據(jù)預(yù)存和并行計(jì)算兩個(gè)方法來提高計(jì)算速度。

1）數(shù)據(jù)預(yù)存

在計(jì)算過程中其實(shí)有大量的計(jì)算是重復(fù)性的。為了提高系統(tǒng)的計(jì)算效率，降低系統(tǒng)的計(jì)算復(fù)雜程度[11]，對一些計(jì)算過程量進(jìn)行存儲(chǔ)保留，后續(xù)程序運(yùn)行時(shí)可以從緩存區(qū)直接調(diào)取[11]，這樣可以大幅提高程序的運(yùn)行速度。

2）并行計(jì)算

Python里對應(yīng)這種計(jì)算密集型的任務(wù)可以采用多進(jìn)程方式來實(shí)現(xiàn)[12-13]，涉及多進(jìn)程的運(yùn)行最關(guān)鍵的就是整個(gè)計(jì)算過程中探索的多樣性和共享數(shù)據(jù)的一致性。MCTS的幾種典型并行計(jì)算方式[14]分別為：葉子節(jié)點(diǎn)并行模式、多搜索樹并行模式、單搜索樹全局鎖并行模式、單搜索樹局部鎖并行模式。

本文采用的方式是不加鎖的蒙特卡洛樹搜索算法Lock-free MCTS[15]。在沒有保護(hù)的計(jì)算過程中有可能導(dǎo)致更新信息的丟失，但是在大規(guī)模的采樣環(huán)境和高效的單次搜索過程中這些影響很有限，可以被忽略[15]。

4.2 模型的搜索準(zhǔn)確性優(yōu)化

4.3 模型的泛化能力優(yōu)化

1）應(yīng)對航班時(shí)刻變化的能力

為了能更好地適應(yīng)航線工作需求，提高模型應(yīng)對復(fù)雜生產(chǎn)環(huán)境的能力，在計(jì)算過程中可以人為地為每個(gè)任務(wù)加入相對應(yīng)的時(shí)間噪聲，如公式（7）和（8）所示。

2）應(yīng)對突發(fā)事件的能力

在生產(chǎn)中會(huì)出現(xiàn)某個(gè)航班的非正常滯留（如目的地機(jī)場的天氣原因或航路的天氣原因等）和AOG（飛機(jī)故障）情況，這些情況的出現(xiàn)會(huì)打亂現(xiàn)有的人員分配計(jì)劃。如果出現(xiàn)類似情況，需要有對應(yīng)的特殊處理方法，實(shí)際操作中的流程為：

a.從現(xiàn)有的航班管理系統(tǒng)或者生產(chǎn)人員那里了解航班的當(dāng)前狀態(tài)；

b.鎖定已經(jīng)處于工作中的人員分配方案；

c.更改非正常任務(wù)的工作時(shí)間范圍；

d.對還未進(jìn)行工作的分配計(jì)劃進(jìn)行清空；

e.對清空的計(jì)劃任務(wù)開始新的分配方案搜索；

f.用變化小但分?jǐn)?shù)高的新方案來進(jìn)行人員局部調(diào)整。

5 結(jié)束語

本文的主要工作是基于強(qiáng)化學(xué)習(xí)的蒙特卡洛樹搜索來完成任務(wù)的自動(dòng)化分配。作為當(dāng)前流行的機(jī)器學(xué)習(xí)方法在實(shí)際生產(chǎn)中的初步試探，取得了不錯(cuò)的效果。目前系統(tǒng)信息環(huán)境比較局限，可以嘗試更加復(fù)雜多樣的信息環(huán)境，在多個(gè)信息維度下同時(shí)展開搜索。機(jī)器學(xué)習(xí)技術(shù)落地需要不斷的探索和嘗試，怎樣將這些前沿的研究成果轉(zhuǎn)化為實(shí)際生產(chǎn)力是我們應(yīng)該不懈努力的方向。

參考文獻(xiàn)

[1] 吳軍.智能時(shí)代[M].北京：中信出版集團(tuán)，2016：30-35.

[2] SILVER D，HUANG A，MADDISON C J.，et al. Mastering the Game of Go with Deep Neural Networks and Tree Search[J]. Nature，2016（1）：484-489.

[3] 馮超.強(qiáng)化學(xué)習(xí)精要核心算法與 Tensorflow實(shí)現(xiàn)[M].北京：電子工業(yè)出版社，2018：145-147，178-181，309-312.

[4] 郭憲，方勇純.深入淺出強(qiáng)化學(xué)習(xí)原理入門[M].北京：電子工業(yè)出版社，2018：18-22.

[5] 胡永宏，賀思輝.綜合評(píng)價(jià)方法[M].北京：科學(xué)出版社，2000：48.

[6] 吳軍.數(shù)學(xué)之美[M].北京：人民郵電出版社，2015：127-135，244-248.

[7] 陳瑞.針對大量業(yè)務(wù)數(shù)據(jù)的分析方法[J].航空維修與工程，2019（7）：52-56.

[8] BROWNE C.B.，POWLEY E.，WHITEHOUSE D，et al. A Survey of Monte Carlo Tree Search Methods[J]. IEEE Transactions on Computational Intelligence and AI in Games，2012（3）：1-43.

[9] AUER P. Finite-time Analysis of the Multiarmed Bandit Problem[J].Machine Learning，2002（47）：235-256.

[10] KOCSIS L，SZEPESV′ARI C. Bandit-based Monte-Carlo Planning[J].European Conference on Machine Learning，2006（9）：282-293.

[11] DOGLIO F. Mastering Python High Performance[M].陶俊杰，陳小莉，譯.北京：人民郵電出版社，2016：12-16，84-85.

[12] BEAZLEY D，JONES B K. Python Cookbook[M].陳舸，譯.北京：人民郵電出版社，2015：496-547.

[13] CHUN W. Core Python Applications Programming（3rd edition）[M].孫波翔，李斌，李晗，譯.北京：人民郵電出版社，2016：122-165.

[14] CHASLOT G，WINANDS M H.M.，HERIK H J V D. Parallel Monte-Carlo Tree Search[J].International Conference on Computers and Games，2008（9）：60-71.

[15] ENZENBERGER M，MULLER M.A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm[J].Advances in Computer Games，2009（5）：14-20.

[16] NELLI F. Python Data Analyt- ics[M].杜春曉，譯.北京：人民郵電出版社，2016.

[17] MILOVANOVIC L. Python Data Visualization Cookbook[M].顓清山，譯.北京：人民郵電出版社，2016.

[18] 賈俊平，何曉群，金勇進(jìn).統(tǒng)計(jì)學(xué)（第六版）[M].北京：中國人民大學(xué)出版社，2016：57-58.

作者簡介

陳瑞，工程師，主要從事業(yè)務(wù)數(shù)據(jù)的分析與挖掘工作。