巡檢線路排班優化模型研究

陸春桃

【摘 要】文章利用雙向帶權連通圖遍歷方法、數學規劃方法、Excel工具對巡檢線路安排進行討論，從省力、工作量平衡等方面著手，構建出合理的巡檢線路安排的優化模型。首先以所需人數最少和所用時間盡量最少作為雙目標函數，同時需要滿足巡檢點的巡檢周期不超過35 min，構建出優化模型后再轉化為雙向帶權連通遍歷問題，用模型得出每條路線所需最少人數、一天需要巡檢人員人數；然后用窮舉法，安排出巡檢路線和巡檢時間安排表。考慮上休息時間和進餐時間因素，增設時間約束條件，應用同樣的方法，得出問題二的巡檢路線和巡檢時間安排表；最后利用Excel工具進行數據處理，給出問題三在錯時上班時是否省力的結論。

【關鍵詞】巡檢線路安排；數學規劃方法；窮舉法；優化模型

【中圖分類號】O224 【文獻標識碼】A 【文章編號】1674-0688（2017）11-0035-04

1 問題提出

合理安排工人進行巡檢，及時發現問題、及時維修是大型工廠安全生產、提高勞動效益的有效舉措。結合這一實際，2017年“高教社杯”全國大學生數學建模競賽D題給出了巡檢線路的排班問題。

某化工廠有26個點需要進行巡檢以保證正常生產，題目給出了各個點的巡檢周期、巡檢耗時、兩點之間的連通關系及行走所需時間。

現要求每個點每次巡檢安排1名工人，每人均從巡檢調度中心開始出發，分2種情況采取固定時間上班：一是每班工人不休息，二是每班工人每工作2 h可休息5～10 min，中午12時和下午6時左右有30 min的進餐時間；也可以錯時上班，在調度中心得到巡檢任務后開始巡檢?，F要求滿足所有點都能按要求完成巡檢，耗費的人力資源盡可能地少，每名工人在一段時間內（如1周或1個月等）的工作量盡量平衡3個條件來建立模型，進而確定巡檢人數和巡檢路線。

2 問題假設

（1）假設各個巡檢人員的巡檢路線是可以重復的。

（2）假設每個站點都可讓巡檢人員提前巡檢。

（3）假設每個站點都排除意外因素的發生。

（4）假設問題一中，巡檢工作人員的三班倒時間段為8：00-16：00；16：00-24：00；24：00-8：00。

（5）假設問題二中，巡檢工作人員的三班倒時間段為12：00-18：00；18：00-2：00；2：00-10：00。

（6）假設問題三中，巡檢工作人員的三班倒時間段為10：00-18：00；18：00-2：00；2：00-10：00。

（7）假設每個站點之間路程只有耗時的不同，并沒有其他不同。

（8）假設如有一名巡檢人員在某一段時間不夠完成巡檢工作的情況下，可以尋求臨近的其他巡檢人員幫忙。

（9）假設每個站點只需要1名巡檢人員，其余的巡檢人員可以路過該站點，但不需要停留巡檢。

3 符號說明

符號及對應的意義見表1。

4 問題分析

本題屬于優化模型問題，需要用數學規劃方法對問題進行求解。

針對問題一，不考慮巡檢人員的休息時間，采用每天三班倒，每班工作8 h左右的條件，我們可建立所需巡檢人數最少的目標函數，同時確定約束條件，確立優化的規劃模型。用Excel軟件的數據處理分析功能對模型進行求解，得到巡檢人員最少的人數，再用窮舉法，按區域劃分優先考慮回路的方式、折回的方式，根據題目所給的周期，選最少的時間按照連通圖上點的順序進行列舉得出最佳路線，并根據路線安排巡檢人員排班表。

在問題一的基礎上，新增巡檢人員每巡檢2 h左右需要休息一次、在中午12時和下午6時左右需要進餐一次、每次進餐時間為30 min 3個約束條件。保持問題一中的模型不變，再加上這些約束條件后，可以得到新的模型，隨后對模型進行求解，用同樣的方法得出巡檢人數、巡檢線路排班表。

至于問題三，采用錯時上班時間，在問題一、問題二模型的基礎上，分別通過Excel軟件的數據處理分析功能，得出化工廠最優化的巡檢人員人數，以此說明是否節約人力。

5 模型的建立和求解

5.1 問題一

5.1.1 確立模型

根據題意：固定上班時間，不考慮巡檢人員的休息時間，每天三班倒，每班工作盡量滿足8 h，而且每個巡檢點的實際巡檢周期都小于或等于所需巡檢周期。設Xi為巡檢所需最少人數，Ti為第i個巡檢點的巡檢周期，li為巡檢耗時時間（i=1，2，…，26），kj為路程間的耗時（j=1，2，…，31），建立巡檢人數最少的目標函數：

min∑Xi=li+kj（模型I）

min■|ti-480|（i=1，2，3，4，5，…，n）

s.t

Ti≤Ti≤35，（i=1，3，4，6，8，9，11，12，14，15，16，18，19，20，22，23，24，26）；Ti≤80，（i=7，13，21）；Ti≤120，（i=10，25）；T2≤50；T17≤480；T5≤72；

5.1.2 確定人數

通過Excel軟件對模型I進行數據處理分析，得到Xi=5。

結論：我們可以知道每班需要5名巡檢人員，每天采用三班倒，需要15名巡檢人員。

5.1.3 確定路線

因為最優解法在一般條件無法利用軟件求出，所以我們得出以上最優解法后，需要使用窮舉法，分區域劃分優先考慮回路的方式，再安排折回的方式選出以下5條路線：①22→20→19→2→4→21→22；②23→24→9→25→26→23；③7→5→3→1→14→8→3；④17→6→10→12→6；⑤15→18→16→13→11→15。

5.1.4 安排時間

根據上述運算結果，假設巡檢工作人員的三班倒時間段為8：00-16：00；16：00-24：00；24：00-8：00。

按每一班的時間表進行數據整理，由此我們得出三班倒的巡檢時間安排表見表1，8：00-16：00的巡檢時間表見表2。

我們知道巡檢人員每天的工作時間為8 h，但是由于每條路線巡檢耗時和路程耗時不同，存在細微的時間差，為了讓每位巡檢人員在上班時間段內的工作量盡量平衡，所以每個巡檢人員每次上班的路線都實行輪換制來巡檢以上5條路線。

5.2 問題二

考慮到增設條件：巡檢人員每巡檢2 h左右需要休息一次、休息時間為5～10 min、在中午12時和下午6時左右需要有30 min的進餐時間。

5.2.1 建立模型

假設三班倒的時間為2：00-10：00；10：00-18：00；18：00-2：00。為節省時間，假設每工作2 h的休息時間為5 min，兩次進餐時間分別為巡檢人員的上班前和下班后，先優化上班時間，使進餐時間分別在交接班處。綜上所述，調整巡檢人員的三班倒的時間為3：00-12：00，12：00-18：00，18：00-3：00，時長分別為9 h、6 h、9 h。

設Xi為巡檢所需的最少人數；li為巡檢耗時時間（i=1，2，…，26）；

kj為路程間的耗時時間（j=1，2，…，31）；Ti為第i個巡檢點的巡檢周期，建立目標函數：

min∑Xi=li+kj（模型II）

min■|A-360|（i=1，2，3，4，5，…，n）

（A為6 h的巡檢耗時時間）

min■|B-540|（i=1，2，3，4，5，…，n）

（B為9 h巡檢耗時時間）

s.t

Ti≤Ti≤35，（i=1，3，4，6，8，9，11，12，14，15，16，18，19，20，22，23，24，26）；Ti≤80，（i=7，13，21）；Ti≤120，（i=10，25）；T2≤50；T17≤480；T5≤72；

5.2.2 求出人數

通過Excel軟件對模型II進行數據處理分析，得到Xi=5。

結論：9 h和6 h每班都需要5名巡檢人員，所以一天需要15名巡檢人員。

5.2.3 確定路線

由窮舉法：分區域劃分優先考慮回路的方式，再安排折回的方式，得出以下5條路線：①22→20→19→2→4→21→22；②23→24→9→25→26→23；③7→5→3→1→14→8→3；④17→6→10→12→6；⑤15→18→16→13→11→15。

5.2.4 安排時間

按每一班的時間表進行數據整理，由此我們得出三班倒的巡檢時間安排表（見表3），下面給出12：00-18：00的巡檢時間表。

因為巡檢人員每天工作時間分別為6 h、9 h、9 h，并且每條路線巡檢耗時和路程耗時不同，存在細微的時間差，所以為了確保在一個時間段內的工作量盡量平衡，要求每位巡檢人員都要在6 h、9 h、9 h進行三班倒，因此可以考慮5天換一次班次，在這5天內每次上班的路線都需要輪流走這5條路線，走完5條路線就必須讓巡檢人員進行一次換班。

記5名巡檢工人為a、b、c、d、e，5條線路用1、2、3、4、5標記，得出這5名工人輪換早班、中班、晚班的巡檢線路表（見表4）。

5.3 問題三

5.3.1 問題一：錯時上班

對于問題一，采用錯時上班的時間，由于沒有考慮休息時間，每人的巡檢時間都為8 h，只是上班時間不同步。因此用同樣的辦法可以知道問題三中錯時上班每班需要5名巡檢人員，一天需要15名巡檢人員，已經達到最優化，所以錯時上班并沒有起到節省人力資源的作用。

5.3.2 問題二：錯時上班

對于問題二，采用錯時上班的時間，考慮到中午12點、下午18點左右巡檢人員需要進餐，針對問題二中10：00-18：00這一班，午餐時間5名巡檢人員輪流去吃午餐（共花費30 min），若不考慮換路線，則每條路線安排2名巡檢人員，10名巡檢人員可以確保各個站點的巡檢；若考慮換線路，則需要增加2名工人進行替換，這班共安排7名巡檢人員。其余兩班并沒有進餐時間的影響，每班各有5名巡檢人員，所以一天需要17～20名巡檢人員，因此錯時上班時間并沒有起到節省人力的作用。

6 模型評價與分析

本文應用窮舉法將復雜的數據進行處理，采用Excel工具產生巡檢人員的排班表，并且聯系實際生產，可以運用到生產中的各種排班問題上，實現巡檢路線的最優化。但本模型的計算機自動化程度不高，沒有能夠編寫程序實現全自動化排序。此外，安排的時間表具有一定的偶然性，普遍性不強。

參 考 文 獻

[1]姜啟源，謝金星，葉俊.數學模型[M].第3版.北京：高等教育出版社，2003.

[2]謝金星，薛毅.優化模型與LINDO/LINGO軟件[M].北京：清華大學出版社，2005.

[3]佚名.排班問題的最優數學規劃[EB/OL].https：//wenku.

baidu.com/view/ab88b7834431b90d6d85c721.html？qq-

pf-to=pcqq.discussion，2015-08-21.

[4]佚名.基于線性規劃的護士排班優化問題[EB/OL].http：//www.nexoncn.com/read/51fc68bb0a70fc16056d

7633.html，2011-07-15.

[責任編輯：鐘聲賢]