建立數(shù)學模型解決“巡檢線路排班”問題

呂寧寧，潘娜娜，董 慧

(1.安徽工業(yè)經(jīng)濟職業(yè)技術(shù)學院，安徽 合肥 230051；2.安徽新華學院，安徽 合肥 230088)

1 問題描述

1.1 背景資料

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

每個點每次巡檢需要1名工人，巡檢工人的巡檢起始地點在巡檢調(diào)度中心，工人可以按固定時間上班，也可以錯時上班，在調(diào)度中心得到巡檢任務(wù)后開始巡檢?，F(xiàn)需要建立模型來安排巡檢人數(shù)和巡檢路線，使得所有點都能按要求完成巡檢，并且耗費的人力資源盡可能少，同時還應考慮每名工人在一定時間段內(nèi)(如1周或1個月等)的工作量盡量平衡。

1.2 問題提出

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

問題2，如果巡檢人員每巡檢2 h左右需要休息1次，休息時間大約是5～10 min，在12時和18時需要進餐1次，每次進餐時間為30 min，仍采用每天3班倒，每班需要多少人，巡檢線路如何安排，并給出巡檢人員的巡檢線路和巡檢時間表。

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

2 問題分析

不論固定上班還是錯時上班，工作人員都是從調(diào)度中心開始進行工作，但是離該點較遠的地方就要直接派工人走到一定的點后開始巡檢。因此，可以把巡檢工作轉(zhuǎn)化為圖論中的賦權(quán)圖，用Kruskal算法[1-2]找出賦權(quán)圖的最小生成樹[3-6]，然后進行問題的求解。

已知條件中的連通賦權(quán)圖為G=(V,E,A)，其中V=(v1,v2,…，v26)為頂點集，vi(i=1,2,…,26)表示26個需要巡檢的點[7]，v22為巡檢調(diào)度中心，E為邊的集合，A=(dij)26×26為鄰接矩陣，其中

lij表示巡檢點vi到巡檢點vj的路程耗時，若巡檢點vi到巡檢點vj沒有邊相連，記為∞。

接下來用Kruskal算法找出圖G的最小生成樹。因為v22為巡檢調(diào)度中心，所以以v22為樹的根，邊v22v23的權(quán)為1，為最小權(quán)邊，首先選擇邊v22v23，接下來的每一步都從未選的邊中選取邊e，使它與已選邊不構(gòu)成圈，且e是未選邊中的最小權(quán)邊，直到選夠21條邊為止(樹的邊數(shù)=頂點數(shù)-1)，就得到了圖G的最小生成樹T。

2.1 問題1的分析

如果采用固定上班時間，不考慮巡檢人員的休息時間，采用3班倒，可以假設(shè)上班時間分別為0∶00-8∶00、8∶00-16∶00、16∶00-24∶00。已知大部分點的巡檢周期為35 min，對于位號為XJ—0005，XJ—0010，XJ—0017，XJ—0025的點不作考慮，因為這4個點的巡檢周期均在120 min以上，經(jīng)過3個周期，空出來的時間就可以進行檢測。

先對最小生成樹進行大致分塊，給出每班約需要多少人，粗略劃分后，求出每一塊的邊權(quán)和頂點權(quán)之和，建立目標規(guī)劃模型，使用Floyd算法[8-15]求出每一名工人的最短路徑[16-18]，再使用MATLAB[19]及LINGO，驗證每班需要人數(shù)，給出合理優(yōu)化的巡檢線路[20]和巡檢時間表。

2.2 問題2的分析

如果工人需要休息時間和進餐時間，通過問題1可知，要保證工作正常進行，必須至少同時4人在工作，若在問題1的基礎(chǔ)上每班增加1人，由于12點左右吃飯時只能每人輪流進餐，因此吃飯時間至少持續(xù)2.5 h，不盡合理。所以在問題1的基礎(chǔ)上每班增加2人(考慮到3班需要倒班，所以忽略夜班0∶00-8∶00需要工人數(shù)更少的情況)，然后建立目標規(guī)劃模型，使用MATLAB及LINGO，驗證每班需要6人是否合理，并給出優(yōu)化的巡檢線路和巡檢時間表。

2.3 問題3的分析

由問題1可知，要滿足背景資料的條件，必須至少4名工人同時工作，若要把問題1中的固定上班改為錯時上班，反而會增加人力成本，不可取。

問題2中，牽涉到休息和吃飯的問題，如果能合理安排，讓工人錯開時間上班，就可以節(jié)省人力。比如：第一組工人上班時間為3∶00-11∶30，工作時間為8.5 h，第二組工人上班時間為11∶30-19∶00，工作時間為7.5 h，第三組工人上班時間為19∶00-3∶00，工作時間為8 h。這種上班時間安排可將2次進餐時間錯開，所有工人可以省去吃飯的30 min，這樣工作量減少，每班5個人就可以完成，此種方法比固定上班共節(jié)省3人。因為在一定的周期內(nèi)3組工人要進行調(diào)班，所以整體來看，工人的工作量仍然能保持均衡。接下來建立目標規(guī)劃模型，使用MATLAB及LINGO，驗證每班需要5人是否合理，并給出優(yōu)化的巡檢線路和巡檢時間表。

可以如下安排，第一組工人上班時間為4∶00-12∶00，第二組工人上班時間為12∶00-20∶00，第三組工人上班時間為20∶00-4∶00；則每組工作時間都為8 h，第一次進餐時間無需計算，只需在6∶00時進餐1次即可，則第一班人數(shù)為5人，第二班人數(shù)為6人，第三班人數(shù)為5人，則此種方法比固定上班共節(jié)省2人。這種方式在此不進行深入討論。本文只探討每班5名工人工作的情形。

3 模型的建立與求解

3.1 問題1的模型建立與求解

在樹T中，所有邊的權(quán)之和為47，26個頂點的權(quán)之和為67，巡檢點的巡檢周期大部分都是35 min，那么每班的工人數(shù)要大于或等于(47+67)÷35≈3.26，由于要取整，那么每班的工人數(shù)至少要為4人，而巡檢點的個數(shù)為26，考慮到每名工人在一定時間段內(nèi)的工作量盡量平衡，每位工人所負責的巡檢點的個數(shù)應該在26÷4=6.5≈7左右，然后將最小生成樹T劃分為4個部分，在劃分的時候盡量滿足以下幾個條件：

1)劃分的4塊盡量接近調(diào)度中心，即接近頂點；

2)劃分的各子圖盡量為連通圖，各子圖所含頂點數(shù)在7個左右；

3)因為要進行循環(huán)巡檢，所以劃分的子圖應容易形成圈。

按照以上的條件，對最小生成樹T進行粗略分塊(表1)。

表1 最小生成樹的分塊

每一個工人在35 min內(nèi)巡檢自己所負責的點，對于巡檢周期較長的可以循環(huán)幾次之后對該點進行巡檢一次。每位工人負責的巡檢區(qū)域子圖分別記為G1、G2、G3、G4，記

(1)

其中qi為巡檢點vi巡檢所需耗時。

為使工人的工作量盡量平衡，引入1個量η進行衡量，稱之為工作量均衡度，記

(2)

顯然，η值越接近于0，說明工作量越均衡。

這樣就建立了以下的目標函數(shù)

(3)

根據(jù)劃分時需要滿足的條件可以給出上述目標函數(shù)的約束條件。

1)因為工人都是從調(diào)度中心開始工作的，因此頂點v22應在每一個子圖中，即v22∈Gk,k=1,2,3,4。

2)4個分塊應包含圖G的所有頂點，即

V(G1)∪V(G2)∪V(G3)∪V(G4)=V(G)

3)因為大部分點的巡檢周期都是35 min，所以在35 min以內(nèi)，每個工人都應在其負責的區(qū)域巡檢一遍，并能夠回到巡檢起點，即

由上所述，可以得到問題1的目標規(guī)劃模型

(4)

(5)

運用Floyd算法，使用MATLAB對每組求最短路徑，使用LINGO求出最優(yōu)回路，并對結(jié)論進行微調(diào)。

最優(yōu)巡檢線路及周期耗時見表2。

表2 問題1的巡檢路線

表3為第一班工人從0∶00時開始時，前3個周期內(nèi)26個巡檢點的巡檢時間。

表3 問題1的巡檢時間

以后周期的巡檢時間可以依次類推。

3.2 問題2的模型建立與求解

通過前面的問題分析，把6名工人負責的巡檢區(qū)域子圖分別為G1、G2、G3、G4、G5、G6，記

(6)

其中qi為巡檢點vi巡檢所需耗時。

工作量均衡度

(7)

這樣就建立了以下的目標函數(shù)

(8)

根據(jù)劃分時需要滿足的條件可以給出上述目標函數(shù)的約束條件。

1)因為工人都是從調(diào)度中心開始工作的，因此頂點v22應在每一個子圖中，即v22∈Gk,k=1,2,3,4,5,6。

2)6個分塊應包含圖G的所有頂點，即

V(G1)∪V(G2)∪V(G3)∪V(G4)∪V(G5)∪V(G6)=V(G)

3)35 min以內(nèi)，每名工人都應在其負責的區(qū)域巡檢一遍，并能夠回到巡檢起點，即

由上所述，可以得到問題1的目標規(guī)劃模型

(9)

(10)

運用Floyd算法，使用MATLAB對每組求最短路徑，最短路徑可以確定工人在其工作區(qū)域如何以最快速度到達需要巡檢的點。使用LINGO求出最優(yōu)回路，因為每位工人需要在其工作區(qū)域循環(huán)巡檢，因此求出的最優(yōu)回路就是工人的最優(yōu)巡檢路線。

表4給出了每班6名工人的巡檢路線，以及前3個周期的巡檢耗時。

表4 問題2的巡檢耗時

以甲為例，前3周期巡檢耗時均為27 min，每個周期都能有空余休息時間，這樣一定能保證2 h可以有5～10 min的休息時間。而吃飯的時候需要有4人在線工作，所以可以安排2人1組去吃飯，剩余4人按照問題1的巡檢路線進行巡檢，這樣所有工人的進餐時間前后只要持續(xù)1.5 h就可以，而如果每班5人,則吃飯持續(xù)時間2.5 h時間過長，不符合要求的12時或者6時左右進餐。

表5給出了第一班工人從0∶00時開始，前3個周期內(nèi)26個巡檢點的巡檢時間。

表5 問題2的巡檢時間

表5(續(xù))

以后周期的巡檢時間可以依次類推。

3.3 問題3的模型建立與求解

通過問題3的分析，把5名工人負責的巡檢區(qū)域子圖分別G1、G2、G3、G4、G5，記

(11)

其中qi為巡檢點vi巡檢所需耗時。

工作量均衡度

(12)

建立以下目標函數(shù)

(13)

根據(jù)劃分時需要滿足的條件可以給出上述目標函數(shù)的約束條件。

1)因為工人都是從調(diào)度中心開始工作的，因此頂點v22應在每一個子圖中，即v22∈Gk,k=1,2,3,4,5。

2)5個分塊應包含圖G的所有頂點，即V(G1)∪V(G2)∪V(G3)∪V(G4)∪V(G5)=V(G)

3)因為大部分點的巡檢周期都是35 min，所以在35 min以內(nèi)，每個工人都應在其負責的區(qū)域巡檢一遍，并能夠回到巡檢起點，即

由上所述，得到問題3的目標規(guī)劃模型

(14)

(15)

運用Floyd算法，使用MATLAB對每一子圖求出最短路徑，以此確定工人到達巡檢點所需最短時間。然后使用LINGO求出最優(yōu)回路，以此得到工人的最優(yōu)巡檢路線。通過對結(jié)論進行優(yōu)化，最終5名工人的巡檢路線見表6。

表6 問題3的巡檢路線

5名工人3個周期的巡檢時間見表7。

表7 問題3的巡檢時間

所以若要把問題1中的固定上班改為錯時上班，反而會增加人力成本，不可取。

若把問題2中的固定上班改為錯時上班，考慮到長遠，要進行3班調(diào)班，所以得出3班均為5人上班，比固定上班共節(jié)省3名工人。