曹西林

摘要：對化工廠安排工人巡檢問題，是一個具有一般性的調(diào)度安排問題，在實(shí)際中具有重要作用。本文建立了優(yōu)化模型，采用多TSP問題的思想和原理，將問題等價變換為尋找區(qū)域劃分?jǐn)?shù)最少的問題，還通過LINGO求解TSP問題給出了每個工人的最優(yōu)巡檢路線；打破工人區(qū)域限制，對所有節(jié)點(diǎn)進(jìn)行了人員的初始任務(wù)分配，然后根據(jù)每個節(jié)點(diǎn)的巡檢周期，得到關(guān)于所有任務(wù)的開始工作時刻序列，結(jié)束工作時刻序列，任務(wù)對應(yīng)節(jié)點(diǎn)序列，并以此建立了巡檢人數(shù)最少和工作量盡量均衡的雙目標(biāo)0-1規(guī)劃模型；對錯時上班問題，考慮了每個人上班時間可調(diào)整情況下，巡檢人數(shù)最少和工作量盡量均衡的雙目標(biāo)0-1規(guī)劃模型，并設(shè)計算法進(jìn)行求解。

關(guān)鍵詞：巡檢；TSP模型；最優(yōu)路線；優(yōu)化模型

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼： A 文章編號：1009-3044（2018）19-0234-02

1 問題提出

某化工廠的巡檢，需要考慮26個點(diǎn)需要進(jìn)行巡檢以保證正常生產(chǎn)，各個點(diǎn)的巡檢周期、巡檢耗時、兩點(diǎn)之間的連通關(guān)系及行走所需時間（數(shù)據(jù)參見2017年全國大學(xué)生數(shù)學(xué)建模競賽C題附件1）。建立相關(guān)數(shù)學(xué)模型來安排巡檢人數(shù)和巡檢路線。

針對該問題，需要完成三種情況下的計算。一是固定上班時間，不考慮巡檢人員的休息時間情形；二是固定上班，但巡檢人員有休息情形；三是錯時上班情形。

問題1. 如果采用固定上班時間，不考慮巡檢人員的休息時間，采用每天三班倒，每班工作8小時左右，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢的時間表。

問題2. 如果巡檢人員每巡檢2小時左右需要休息一次，休息時間大約是5到10分鐘，在中午12時和下午6時左右需要進(jìn)餐一次，每次進(jìn)餐時間為30分鐘，仍采用每天三班倒，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢的時間表。

問題3. 如果采用錯時上班，重新討論問題1和問題2，試分析錯時上班是否更節(jié)省人力。

2 問題分析

針對問題1， 我們將所有26個節(jié)點(diǎn)分成若干個區(qū)域，每個區(qū)域內(nèi)的節(jié)點(diǎn)滿足：（1）按最短路線行走和巡檢，巡檢走完所有節(jié)點(diǎn)并回到開始點(diǎn)，其所花時間不超過該區(qū)域內(nèi)所有節(jié)點(diǎn)的最小周期。（2）每個節(jié)點(diǎn)在一個周期內(nèi)必須巡檢一次，因此要滿足首次到達(dá)該節(jié)點(diǎn)的時間不能超過該節(jié)點(diǎn)的周期。該問題本質(zhì)上是一個多TSP問題。我們要建立模型，尋找滿足兩個條件的最少劃分區(qū)域。

針對問題2，由于每個工人工作兩小時后要休息5-10分鐘，而且中午12點(diǎn)和下午4點(diǎn)要吃飯花30分鐘左右。這樣采用問題1的靜態(tài)劃分方式就不行了，需要采用動態(tài)方式，使工人在需要的時候自動在全區(qū)去完成當(dāng)前任務(wù)。我們擬建立一般模型，并設(shè)計算法進(jìn)行計算。

針對問題3，采用錯時上班，每個人可以在一天的任意時間上班，只要連續(xù)工作8小時就可以。我們?nèi)匀唤⒁话隳Ｐ?，并進(jìn)行動態(tài)調(diào)整，當(dāng)有任務(wù)而當(dāng)前無法完成時，就可以增加一個人去完成。這樣對可能更能節(jié)省人力，提高效率。

3 模型建立與求解

問題一：

該問題中采用固定上班時間，不考慮巡檢人員的休息時間，采用每天三班倒，每班工作8小時左右。我們考慮將26個節(jié)點(diǎn)分成若干個區(qū)域，每個區(qū)域內(nèi)的節(jié)點(diǎn)滿足：（1）按最短路線行走和巡檢，巡檢走完所有節(jié)點(diǎn)并回到開始點(diǎn)，其所花時間不超過26個節(jié)點(diǎn)的最小周期35分鐘。（2）同時由于各節(jié)點(diǎn)周期不同，每個節(jié)點(diǎn)在一個周期內(nèi)必須巡檢一次，因此要滿足首次到達(dá)該節(jié)點(diǎn)的時間不能超過該節(jié)點(diǎn)的周期。我們的任務(wù)就是尋找滿足該條件的最少劃分區(qū)域。本質(zhì)上是一個多TSP問題。

根據(jù)上面可確定的每個節(jié)點(diǎn)初次到達(dá)時刻。設(shè)第[i]個節(jié)點(diǎn)初次到達(dá)時刻為[ti]，該點(diǎn)巡檢周期為[Ti]，則該點(diǎn)后面的任務(wù)序列為[t=ti+ki.Ti] ，其中[ki=480-tiTi]，其中[]表示向下取整。這里[ki]表示不超過8小時的最大巡檢次數(shù)。對附件中的初始分配，可計算得到所有26個節(jié)點(diǎn)可計算得到任務(wù)序列為258個。

首先利用Floyd算法和附件所給出的連通圖，計算出所有節(jié)點(diǎn)兩兩之間的最短路，即相互到達(dá)的最小時間，給定初始人數(shù)[m]，根據(jù)問題1，開始可取[m=5]進(jìn)行計算。將[m]個人進(jìn)行初始分配，分配方式可采用前面介紹方式進(jìn)行，共同對26個節(jié)點(diǎn)進(jìn)行首次巡檢，得到每個節(jié)點(diǎn)的首次訪問時間。設(shè)第[i]個節(jié)點(diǎn)的首次巡檢時間為為[ti]，該點(diǎn)巡檢周期為[Ti]，則該點(diǎn)后面需要完成的的任務(wù)序列為[t=ti+ki.Ti] ，其中[ki=480-tiTi]。當(dāng)如果全天考慮時（問題3），只需要取總時間為24*60=1440分鐘。其中[]表示向下取整。這里[ki]表示不超過8小時的最大巡檢次數(shù)。

利用循環(huán)計算，我們可以很容易統(tǒng)計出每個人工作時間，每個人每次執(zhí)行的任務(wù)及所在的節(jié)點(diǎn)序號。

我們將每天分為3班。第一班知需要每工作兩小時左右休息5～10分鐘；第二班不但休息，還含有12時需要吃飯花30分鐘左右；第三班也是不但需要休息，還含有下午6時需要吃飯花30分鐘左右。我們計算結(jié)果為：第一班需要人數(shù)為5人，第二班需要人數(shù)為6人，第三班需要人數(shù)為6人，總共需要20人，比問題1多了2人，各班任務(wù)均衡度都比問題1均衡度55.28更好。說明動態(tài)調(diào)整也更有利于工作量均衡。

問題三：

對錯時上班，對每個人不再有固定開始上班時間?？梢愿鶕?jù)任務(wù)需要隨時參與巡檢，只要工作滿8小時，則下班不再工作。

則在問題2前面模型中，初始時不再讓所有人都在開始時刻上班。設(shè)第[i]個人最后一次巡檢時刻[di]，則：

通過該算法，我們同樣可以計算得到需要的結(jié)果信息。這里我們考慮在問題1情形（不休息），采用初始6人參與分派任務(wù)方式。得到初始安排以后剩余的總?cè)蝿?wù)有828項(xiàng)。計算得到總共需要安排人員15人。每個人的任務(wù)安排見表13。人員序號按工作先后編號。

問題2情形（含休息和吃飯），我們采用初始6 人分配任務(wù)，采用錯時上班。得到初始安排以后剩余的總?cè)蝿?wù)有828項(xiàng)。計算得到最終需要17人。

從該結(jié)果來，對問題1情形，每天總?cè)藬?shù)仍然為15人，但任務(wù)的均衡性得到大大改善，由原來的55.28降為23.42，大大得到改善。對問題2需要工作和吃飯情形，每天需要總工人數(shù)為17人，而問題2按固定班次計算總?cè)藬?shù)為19人，這樣按錯時安排，總?cè)藬?shù)比原來問題的總?cè)藬?shù)減少2人，均衡性也比起最小的均衡度35.23小，說明其均衡性也得到改善。

4 模型的評價與推廣

對化工廠安排工人巡檢問題，是一個具有一般性的調(diào)度安排問題，在實(shí)際中具有重要作用。本文對問題1采用多TSP劃分區(qū)域，求解后人員使用操作簡單，每個工作在自己固定區(qū)域巡檢。所建雙目標(biāo)規(guī)劃模型合理地表達(dá)了問題，便于使用和利用模型來驗(yàn)證、求解。

該模型簡單明了，容易理解，可以靈活的運(yùn)用，具有很強(qiáng)的使用價值，因此可以將該模型推廣于相關(guān)行業(yè)的排班和人員安排。

參考文獻(xiàn)：

[1] 戴朝壽.數(shù)學(xué)建模簡明教程[M].北京：高等教育出版社，2008.

[2] 韓中庚.數(shù)學(xué)建模方法及其應(yīng)用[M].北京：高等教育出版社，2005.

[3] 肖華勇.實(shí)用數(shù)學(xué)建模與軟件應(yīng)用[M].西安：西北工業(yè)大學(xué)出版社，2008.