董 慧，李國芳，李慧娟，楊慧琳

(安徽工業(yè)經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院，合肥 230001)

1 問題提出

2017年全國大學(xué)生數(shù)學(xué)建模競賽D題探討了在節(jié)省人力資源耗費(fèi)和實(shí)現(xiàn)工作量平衡的前提下如何安排巡檢人數(shù)及路線，該題在基本巡檢要求下需解決三個(gè)問題，即分別給出在固定上班時(shí)間、錯(cuò)峰上班時(shí)間下的巡檢人數(shù)、路線和時(shí)間表，并分析何種方式更節(jié)省人力，具體要求可見全國大學(xué)生數(shù)學(xué)建模競賽官網(wǎng)。

2 問題分析

2.1 問題1分析

三班倒固定上班時(shí)間，不防設(shè)為0:00—8:00、8:00—16:00和16:00—24:00。

巡檢線路圖的設(shè)計(jì)要考慮巡檢人數(shù)、路線、總時(shí)間等因素。通過分析，首先確定每班至少4人，然后通過Kruskal算法構(gòu)建最小生成樹，再將圖分為若干子圖，進(jìn)而構(gòu)建優(yōu)化模型，給出巡檢路線及時(shí)間表。

2.2 問題2分析

0:00—8:00不需要進(jìn)餐，結(jié)合問題1的結(jié)論，此時(shí)只需考慮是否能滿足休息時(shí)間的要求即可。8:00—16:00、16:00—24:00需要進(jìn)餐，但情況類似，只選其一討論。所有點(diǎn)按要求完成巡檢至少需要4人同時(shí)在崗，因要有進(jìn)餐時(shí)間，每班至少5人。按每班5人、6人依次討論給出巡檢路線和時(shí)間表。通過是否滿足休息、進(jìn)餐時(shí)間及人數(shù)多少等因素評(píng)價(jià)每班5人、6人的優(yōu)劣。

2.3 問題3分析

由問題2知，每班5人比6人進(jìn)餐時(shí)間長，若想節(jié)省人力應(yīng)通過錯(cuò)時(shí)上班，盡量安排每班5人，同時(shí)解決進(jìn)餐時(shí)間長的問題。利用上下班時(shí)間點(diǎn)避開就餐時(shí)間段，對(duì)不同錯(cuò)時(shí)上班的情況重新對(duì)問題2進(jìn)行討論。

3 模型假設(shè)

A.所有測試所得數(shù)據(jù)有效。

B.不考慮工人停頓、缺席、請(qǐng)假以及不同工人行走快慢等情況。

C.假設(shè)剛到上班時(shí)間工人即刻工作。

D.假設(shè)巡檢點(diǎn)不會(huì)出現(xiàn)設(shè)備故障。

4 模型建立與求解

4.1 問題1的建模與求解

4.1.1 數(shù)據(jù)預(yù)處理

根據(jù)巡檢點(diǎn)周期表，巡檢周期為35 min的有18個(gè)點(diǎn)，超過35 min的僅8個(gè)點(diǎn)。以35 min為一個(gè)周期T來討論，超過35 min的8個(gè)點(diǎn)暫不參與巡檢，最后單獨(dú)討論。重新處理巡檢圖，得圖1。

圖1

4.1.2 確定每班人數(shù)

4.1.3 巡檢線路和時(shí)間表

三個(gè)班情況一樣，只討論0:00—8:00班的情況。

將圖1抽象為賦權(quán)連通圖G(V,E,ω)，其中V為巡檢點(diǎn)集，E為邊集，ω={ωij},ωij表示第i個(gè)巡檢點(diǎn)和第j個(gè)巡檢點(diǎn)的最短耗時(shí)。此外，給點(diǎn)賦權(quán)，令υ={vi}，vi為第i個(gè)巡檢點(diǎn)的周期。

1)找出最小生成樹

利用Kruskal算法，找出圖的最小生成樹(見圖2)。算法為：①選e1∈E(G)，使e1是邊權(quán)值最小的邊。②若e1,e2,…,ei已選好，則從E(G)-{e1,e2,…,ei}中選取ei+1，使得：ⅰ){e1,e2,…,ei,ei+1}中無圈；ⅱ)ei+1是E(G)-{e1,e2,…,ei}中邊權(quán)值最小的邊；ⅲ)直到選得e|V|-1為止。

圖2

圖3

2)分解圖G

根據(jù)最小生成樹(圖2)將圖G分成4塊(見圖3)，分解原則為：①分解點(diǎn)為V22(V22表示第22個(gè)巡檢點(diǎn))或盡量接近V22。②分解后的各子圖盡量為連通圖。③分解所得的4個(gè)子圖頂點(diǎn)周期和盡可能小于35。④生成的子圖容易形成圈或接近圈。

3)構(gòu)建優(yōu)化模型

綜上，建立優(yōu)化模型(1)：

利用Dijkstra算法給出巡檢線路，經(jīng)過適當(dāng)調(diào)整可得到4組3個(gè)周期的巡檢路線表(見表1)、巡檢時(shí)間表(見表2)。

表1 巡檢路線表

表2 巡檢時(shí)間表

4.2問題2的建模與求解

由問題1知，每個(gè)人在一周期巡檢的時(shí)間均未超過35 min，記未達(dá)到的部分為一個(gè)周期節(jié)約的時(shí)間，統(tǒng)計(jì)前4個(gè)周期節(jié)約的時(shí)間列表如下：

人員前三個(gè)周期節(jié)約的總時(shí)間(105 min)前四個(gè)周期節(jié)約的總時(shí)間(140 min)甲67乙46丙33丁1010

甲乙丁工作4個(gè)周期可騰出5 min休息，但丙不能，即丙2 h無法進(jìn)行休息，為使所有巡檢人員在2 h都能至少休息5 min，只有通過增加巡檢人數(shù)實(shí)現(xiàn)。

4.2.1 0:00—8:00班情況

此班無需進(jìn)餐，只需增加1人即可實(shí)現(xiàn)。具體可參考4.2.2建模，不再贅述。

4.2.2 8:00—16:00班情況

由于在12點(diǎn)與18點(diǎn)左右進(jìn)餐，此處只討論8:00—16:00情況。所有點(diǎn)都能按要求完成巡檢，至少要有4人同時(shí)在崗，因而要保證中午12時(shí)左右能輪換進(jìn)餐，每班至少需要5人。按輪流進(jìn)餐方式依次討論5人、6人的情況。

4.2.2.1 每班5人的情況

由于進(jìn)餐時(shí)間為30 min，在問題1的基礎(chǔ)上增加1人后，每人每次巡檢1輪時(shí)間降低且在30 min左右，為方便討論，工人在巡檢1個(gè)周期結(jié)束再去進(jìn)餐。即：當(dāng)有人去進(jìn)餐時(shí)，其余4人巡檢結(jié)束或休息結(jié)束，可以按問題1的路線進(jìn)行巡檢，將進(jìn)餐工人的工作分擔(dān)掉。

類似問題1的方法，首先將圖G分成5塊(分解原則同4.1.3)，然后構(gòu)建優(yōu)化模型(2)：

其中，ω(Ck)為分塊后第k組的回路路程，a為均衡度，Vi為第i個(gè)子圖的點(diǎn)集。

利用Dijkstra算法給出巡檢線路，經(jīng)過適當(dāng)調(diào)整得到表3-4。5人工作時(shí)，每次1人去進(jìn)餐，11:00—13:30進(jìn)餐，共2.5h。

表3 巡檢路線表

表4 巡檢時(shí)間表

4.2.2.2 每班6人的情況

類似4.2.2.1的方式，可得出每班6人時(shí)的巡檢路線圖和時(shí)間表，見表5～6。6人工作時(shí)，分3組輪流進(jìn)餐，每次兩人，11:30—13:00進(jìn)餐，共1.5 h。

表5 巡檢路線表

表6 巡檢時(shí)間表

4.2.2.3 每班5人、6人情況評(píng)價(jià)

每班5人時(shí)，人數(shù)少，但進(jìn)餐時(shí)間長，且最后1人進(jìn)餐已13:00。每班6人時(shí)，進(jìn)餐時(shí)間短，第1人、最后1人開始進(jìn)餐時(shí)為11:30、12:30。從人性化角度考慮，建議每班6人。

4.3 問題3的求解

4.3.1 錯(cuò)時(shí)上班時(shí)，針對(duì)問題1討論

為保證所有點(diǎn)都能按要求完成巡檢，至少要4人。問題1每班4人，已是最少人數(shù)，錯(cuò)時(shí)上班，人數(shù)明顯會(huì)超過4人，并不節(jié)省人力。

4.3.2 錯(cuò)時(shí)上班時(shí)，針對(duì)問題2討論

進(jìn)餐只在12時(shí)和18時(shí)左右進(jìn)行，三班中，第一班無需進(jìn)餐且已是最少人數(shù)，為節(jié)省人力，只能減少第二、三班人數(shù)。

由模型(2)的討論可知，安排進(jìn)餐每0.5 h輪1次。安排5人時(shí)，就餐時(shí)間為11:00—13:30。假設(shè)錯(cuò)時(shí)上班的時(shí)間應(yīng)是0.5 h的倍數(shù)，為節(jié)省人力，每班應(yīng)不占用上班時(shí)間進(jìn)餐，即到就餐時(shí)間，員工下班或上班時(shí)已吃完，故錯(cuò)時(shí)上下班時(shí)間點(diǎn)，應(yīng)正好在此時(shí)間段內(nèi)。

假設(shè)錯(cuò)時(shí)上班時(shí)間為0:00—8:30、8:30—18:00、18:00—24:00。0:00—8:30無需進(jìn)餐，安排5人巡檢。8:30—18:00只考慮12時(shí)進(jìn)餐，18時(shí)下班時(shí)無需進(jìn)餐，按4.2.2.1情況討論，此時(shí)安排6人。18:00—24:00考慮巡檢員上班時(shí)已進(jìn)完餐，工作時(shí)間無需進(jìn)餐，安排6人。其他情況討論，見表7。

表7 不同錯(cuò)時(shí)上班時(shí)間下每班人數(shù)安排表

由表7可知，第4種討論，按3:00—11:00、11:00—19:00、19:00—3:00排班時(shí)，最節(jié)省人力，每班均安排5人。

問題2，錯(cuò)時(shí)上班更節(jié)省人力。

5 結(jié)語

本研究提出的分組準(zhǔn)則簡便易行，可操作性強(qiáng)，用均衡度的概念較好刻畫了分組的均衡性。但模型建立時(shí)的考慮過于理想化，數(shù)據(jù)處理和求解過程中出現(xiàn)的誤差也會(huì)影響模型求解的精確度，這些問題后續(xù)都需進(jìn)一步改進(jìn)。