李波　王妍婷

摘 要： 本文根據一個巡檢線路的數據，用數學統(tǒng)計方法對線路評估并給出優(yōu)化方案。用了最小生成樹算法、整數線性規(guī)劃建立了一系列數學規(guī)劃模型，并用EXCEL和Mathematica、LINGO軟件編程實現。

關鍵詞： 最小生成樹；最短路徑；巡檢線路

中圖分類號： O242.1 文獻標識碼： A 文章編號： 2095-8153（2018）03-0073-04

0 引言

人力資源管理是一個企業(yè)進行人力資源分配的重要工作，合理地安排人力資源，能夠為企業(yè)帶來最大的經濟效益、社會效益、環(huán)境效益。本文研究的是化工廠為滿足不同條件的最優(yōu)巡檢人員調配方案問題，具體內容參看2017年全國大學生數學建模競賽D題[1]。

結合本題附件中給出的具體要求及相關政策，建立模型，解決如下問題：

問題一：若滿足巡檢人員固定上班時間，每班需要巡檢人員的數量，以及巡檢線路的安排，并給出巡檢的時間表。根據已有的各個點的巡檢周期、巡檢耗時、兩點之間的連通關系及行走所需時間驗證所建模型的合理性。

問題二：根據所建立的模型，分析如果巡檢人員每巡檢2小時左右需要休息一次，休息時間大約是5到10分鐘，在中午12時和下午6時左右需要進餐一次，每次進餐時間為30分鐘，仍采用每天三班倒輪班制，每班需要巡檢人員的數量，巡檢線路的安排，巡檢人員的巡檢線路和巡檢的時間表。

問題三：根據問題一問題二所述，若滿足巡檢人員錯時上班，重新驗證問題一問題二，試分析錯時上班是否更節(jié)省人力，是否更具有合理性。

1 模型假設

模型假設

（1）假設巡檢人員在某一個時段一起開始上班，在某一個時段結束時一起下班。

（2）假設固定上班時間為早上8：00，每個巡檢人員必須每天連續(xù)工作8小時，并且工作時間段穩(wěn)定。

（3）假設不考慮上下班巡檢人員交接班、中途吃飯和休息等時間。

（4）排除人員因生病、請假等不能正常工作的情況，排除天氣對巡檢的影響。

2 模型建立與求解

2.1 問題一的模型建立及求解

為估計巡檢人員數量的下限，使用LINGO程序得到精確的計算結果[2]，其中路程耗時68分鐘和檢查耗時67分鐘，共計135分鐘。巡視點兩次巡視的最小間隔時間是35分鐘，且135/35=3.86，因此，一個班至少需要4名工人。根據題目要求來看，只用4名工人巡視，肯定是不夠的，應考慮增加1名工人，一個班使用5名工人?，F知道每個班需要5名工人，所以需要將巡視點劃分成5個區(qū)域，每個區(qū)域最多包含6個點，最少也要有4個點，其目的是保證每個區(qū)域的工作量（巡視時間）盡量平衡。

由于題目要求，每位工人均從22號點開始巡視。因此，距22號點較近的點則多安排一些，而距22號較遠的點則少安排一些。為了完成這種需求的安排，需要計算從22號點至其余各點的最短路，這項工作可用Dijkstra （戴克斯特拉）算法完成。

從圖1出發(fā)，作如下嘗試，將 22、20、19、2、4和21號點編為第一組； 23、24、9、8、17和25號點編為第二組； 1、3、6、14、5和7號點編為第三組； 26、15、18和12號點編為第四組； 11、13、16和10號點編為第五組。每一組都找出相應TSP的結果，這種分組方式是為了滿足題目的要求，在規(guī)定的巡視時間間隔內完成巡視；每位工人的工作量盡量平衡，巡視時間既不能過長，也不能過短。

下面給出具體的巡視路線和巡視時間：

第1組（22、20、19、2、4和21號點）的巡視周期是29分鐘，而21號點的周期間隔是80分鐘，可以兩個35分鐘巡視一次，所以此時巡視周期是27分鐘。

第2組（23、24、9、8、17和25號點）的巡視，最長周期是32分鐘、最短周期28分鐘（17號點和25號點的時間間隔分別為480分鐘和120分鐘）。

第3組（1、3、6、14、5和7號點）的巡視，最長周期是32分鐘，最短周期19分鐘（5號點和7號點的時間間隔分別為720分鐘和80分鐘）。

第4組（26、15、18和12號點）的巡視，周期長度是28分鐘。

第5組（11、13、16和10號點）的巡視，周期長度是25分鐘。

2.2 問題二的模型建立及求解

2.2.1 休息時間

為了簡化問題，先不用考慮“每巡視2小時左右休息大約5到10分鐘”這一要求。因為在問題1的求解過程中，5名工人在巡視過程中，多次出現5分鐘的空余時間，這些空余時間可作休息時間。

2.2.2 進餐時間

在問題1的討論中，每班需要5名工人，考慮兩次進餐時間（1小時），就需要增加5小時，如果再考慮進餐的銜接時間，需要增加的時間還不止5小時，所以僅依賴于原來的5名工人而擠出進餐時間幾乎是不可能的。因此，需要增加1名工人讓他在其他工人進餐時，完成巡視工作。

排班的方法是： 原來的排班時間不變；

5名工人的進餐時間安排在11時至13時之間，和17時至19時之間；進餐時間為35分鐘（最小的時間間隔），進餐時的巡視工作由第6名（機動）工人完成；第6名（機動）工人的進餐時間可安排在他不替班的非工作時間。

2.3 問題三模型建立及問題求解

問題3是考慮錯時上班能否更省人力。

由前面的分析（巡視人員的下限和問題1），知道人員的下限是每班4人，而固定時間上班則需要每班5人。每個點的檢查時間（共計67分鐘）肯定是不能省，因此，要省也只能省下巡視中所花的路程時間。巡視全部點（26個點）的最短路程這恰好是一個旅行商問題，由前面的計算已知，這個時間是68分鐘。那么巡視全部點的最短時間是135分鐘。而題目要求，要在規(guī)定的時間間隔（最短為35分鐘）內完成各點的巡視。這樣，只能換一種排班方法，讓每名巡視工人完成一輪（26個點）的巡視，而每名工人的上班時間向后錯35分鐘，即在前一位工人開始巡視的35分鐘之后，再安排另一名工人巡視。對于巡視間隔要求大于35分鐘的點，可以采用下面的方法處理：無論哪一個點，一律在35分鐘巡視一次，這樣肯定滿足題目的要求。在滿足巡視時間間隔要求的情況下，可以不巡視，但要在相應點處休息，休息的時間就是該點的巡視需要的時間。因此，得到如下的排班方法：第1名工人在8：00開始巡視（上班或換班），第2名工人則在8：35開始巡視，第3名是9：10，第4名是9：45。而每位工人都走最優(yōu)的旅行商路線。注意到，每名巡視工人的間隔時間是35分鐘，4名工人的間隔時間是140分鐘，而一次26個點的旅行商問題的用時是135分鐘。如果第1名工人在第一輪巡視后，休息5分鐘，那么他要在10：20開始第二輪的巡視，與第一輪巡視的第4名工人的巡視時間間隔正好相差35分鐘。第2名工人第二輪巡視的開始時間是10：55，與第1名工人相差35分鐘，以此類推。由上述推導可知，4名工人足夠滿足巡視的要求，同時也達到了巡視人員要求的下界，是最優(yōu)的。

進餐時間會使排班麻煩一些。首先由于進餐時間增加了4個小時，所以，不可能在一個班內由4名工人完成。與問題2一樣，需要增加1名機動工人，頂替工人吃飯時的巡視。由于題目要求，換班只能在22號點完成，也就是說，吃飯的換班時間也只能在22號點完成，也就是在完成某一輪的巡視后，才可以考慮進餐。給出部分表格。

3 模型評價

本題用運用最短路算法，kruskal算法、哈密爾頓圖來計算分區(qū)路線的均衡性，得到相應的時間均衡度，從使用時間的長短均衡度來看，分為這四個區(qū)域均衡性比較好，能保證所有的巡檢點在較短的時間內完成巡檢，而且每個區(qū)域巡檢一個周期所使用的時間相差較小，從而最大限度地避免了一個每個區(qū)域巡檢的時間不均衡。

[參考文獻]

[1]全國大學生數學建模競賽組委會.2017高教社杯全國大學生數學建模競賽（CUMCM）題目D題[EB/OL].[2017-09-14].http：//www.mcm.edu.cn/.

[2]謝金星，薛 毅.優(yōu)化建模與LINDO/LINGO軟件.北京： 清華大學出版社，2005：7.