巡檢線路排班優(yōu)化模型研究

陸春桃

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

【關(guān)鍵詞】巡檢線路安排；數(shù)學規(guī)劃方法；窮舉法；優(yōu)化模型

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

1 問題提出

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

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

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

2 問題假設(shè)

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

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

（3）假設(shè)每個站點都排除意外因素的發(fā)生。

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

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

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

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

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

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

3 符號說明

符號及對應(yīng)的意義見表1。

4 問題分析

本題屬于優(yōu)化模型問題，需要用數(shù)學規(guī)劃方法對問題進行求解。

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

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

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

5 模型的建立和求解

5.1 問題一

5.1.1 確立模型

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

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 確定人數(shù)

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

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

5.1.3 確定路線

因為最優(yōu)解法在一般條件無法利用軟件求出，所以我們得出以上最優(yōu)解法后，需要使用窮舉法，分區(qū)域劃分優(yōu)先考慮回路的方式，再安排折回的方式選出以下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 安排時間

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

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

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

5.2 問題二

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

5.2.1 建立模型

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

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

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

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 求出人數(shù)

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

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

5.2.3 確定路線

由窮舉法：分區(qū)域劃分優(yōu)先考慮回路的方式，再安排折回的方式，得出以下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 安排時間

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

因為巡檢人員每天工作時間分別為6 h、9 h、9 h，并且每條路線巡檢耗時和路程耗時不同，存在細微的時間差，所以為了確保在一個時間段內(nèi)的工作量盡量平衡，要求每位巡檢人員都要在6 h、9 h、9 h進行三班倒，因此可以考慮5天換一次班次，在這5天內(nèi)每次上班的路線都需要輪流走這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名巡檢人員，已經(jīng)達到最優(yōu)化，所以錯時上班并沒有起到節(jié)省人力資源的作用。

5.3.2 問題二：錯時上班

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

6 模型評價與分析

本文應(yīng)用窮舉法將復雜的數(shù)據(jù)進行處理，采用Excel工具產(chǎn)生巡檢人員的排班表，并且聯(lián)系實際生產(chǎn)，可以運用到生產(chǎn)中的各種排班問題上，實現(xiàn)巡檢路線的最優(yōu)化。但本模型的計算機自動化程度不高，沒有能夠編寫程序?qū)崿F(xiàn)全自動化排序。此外，安排的時間表具有一定的偶然性，普遍性不強。

參 考 文 獻

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

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

[3]佚名.排班問題的最優(yōu)數(shù)學規(guī)劃[EB/OL].https：//wenku.

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

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

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

7633.html，2011-07-15.

[責任編輯：鐘聲賢]