呂寧寧，潘娜娜，董 慧

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

1 問題描述

1.1 背景資料

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

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

1.2 問題提出

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

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

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

2 問題分析

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

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

lij表示巡檢點(diǎn)vi到巡檢點(diǎn)vj的路程耗時(shí)，若巡檢點(diǎn)vi到巡檢點(diǎn)vj沒有邊相連，記為∞。

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

2.1 問題1的分析

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

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

2.2 問題2的分析

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

2.3 問題3的分析

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

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

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

3 模型的建立與求解

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

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

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

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

3)因?yàn)橐M(jìn)行循環(huán)巡檢，所以劃分的子圖應(yīng)容易形成圈。

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

表1 最小生成樹的分塊

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

(1)

其中qi為巡檢點(diǎn)vi巡檢所需耗時(shí)。

為使工人的工作量盡量平衡，引入1個(gè)量η進(jìn)行衡量，稱之為工作量均衡度，記

(2)

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

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

(3)

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

1)因?yàn)楣と硕际菑恼{(diào)度中心開始工作的，因此頂點(diǎn)v22應(yīng)在每一個(gè)子圖中，即v22∈Gk,k=1,2,3,4。

2)4個(gè)分塊應(yīng)包含圖G的所有頂點(diǎn)，即

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

3)因?yàn)榇蟛糠贮c(diǎn)的巡檢周期都是35 min，所以在35 min以內(nèi)，每個(gè)工人都應(yīng)在其負(fù)責(zé)的區(qū)域巡檢一遍，并能夠回到巡檢起點(diǎn)，即

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

(4)

(5)

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

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

表2 問題1的巡檢路線

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

表3 問題1的巡檢時(shí)間

以后周期的巡檢時(shí)間可以依次類推。

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

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

(6)

其中qi為巡檢點(diǎn)vi巡檢所需耗時(shí)。

工作量均衡度

(7)

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

(8)

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

1)因?yàn)楣と硕际菑恼{(diào)度中心開始工作的，因此頂點(diǎn)v22應(yīng)在每一個(gè)子圖中，即v22∈Gk,k=1,2,3,4,5,6。

2)6個(gè)分塊應(yīng)包含圖G的所有頂點(diǎn)，即

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

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

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

(9)

(10)

運(yùn)用Floyd算法，使用MATLAB對每組求最短路徑，最短路徑可以確定工人在其工作區(qū)域如何以最快速度到達(dá)需要巡檢的點(diǎn)。使用LINGO求出最優(yōu)回路，因?yàn)槊课还と诵枰谄涔ぷ鲄^(qū)域循環(huán)巡檢，因此求出的最優(yōu)回路就是工人的最優(yōu)巡檢路線。

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

表4 問題2的巡檢耗時(shí)

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

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

表5 問題2的巡檢時(shí)間

表5(續(xù))

以后周期的巡檢時(shí)間可以依次類推。

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

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

(11)

其中qi為巡檢點(diǎn)vi巡檢所需耗時(shí)。

工作量均衡度

(12)

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

(13)

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

1)因?yàn)楣と硕际菑恼{(diào)度中心開始工作的，因此頂點(diǎn)v22應(yīng)在每一個(gè)子圖中，即v22∈Gk,k=1,2,3,4,5。

2)5個(gè)分塊應(yīng)包含圖G的所有頂點(diǎn)，即V(G1)∪V(G2)∪V(G3)∪V(G4)∪V(G5)=V(G)

3)因?yàn)榇蟛糠贮c(diǎn)的巡檢周期都是35 min，所以在35 min以內(nèi)，每個(gè)工人都應(yīng)在其負(fù)責(zé)的區(qū)域巡檢一遍，并能夠回到巡檢起點(diǎn)，即

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

(14)

(15)

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

表6 問題3的巡檢路線

5名工人3個(gè)周期的巡檢時(shí)間見表7。

表7 問題3的巡檢時(shí)間

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

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