曹西林

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

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

中圖分類號：TP391 文獻標識碼： A 文章編號：1009-3044（2018）19-0234-02

1 問題提出

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

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

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

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

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

2 問題分析

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

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

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

3 模型建立與求解

問題一：

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

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

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

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

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

問題三：

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

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

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

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

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

4 模型的評價與推廣

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

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

參考文獻：

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

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

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