對巡檢線路的排班數(shù)學(xué)模型分析

李波　王妍婷

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

關(guān)鍵詞： 最小生成樹；最短路徑；巡檢線路

中圖分類號： O242.1 文獻(xiàn)標(biāo)識碼： A 文章編號： 2095-8153（2018）03-0073-04

0 引言

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

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

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

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

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

1 模型假設(shè)

模型假設(shè)

（1）假設(shè)巡檢人員在某一個(gè)時(shí)段一起開始上班，在某一個(gè)時(shí)段結(jié)束時(shí)一起下班。

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

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

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

2 模型建立與求解

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

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

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

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

下面給出具體的巡視路線和巡視時(shí)間：

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

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

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

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

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

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

2.2.1 休息時(shí)間

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

2.2.2 進(jìn)餐時(shí)間

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

排班的方法是： 原來的排班時(shí)間不變；

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

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

問題3是考慮錯(cuò)時(shí)上班能否更省人力。

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

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

3 模型評價(jià)

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

[參考文獻(xiàn)]

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

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