曹西林

摘要：对化工厂安排工人巡检问题，是一个具有一般性的调度安排问题，在实际中具有重要作用。本文建立了优化模型，采用多TSP问题的思想和原理，将问题等价变换为寻找区域划分数最少的问題，还通过LINGO求解TSP问题给出了每个工人的最优巡检路线；打破工人区域限制，对所有节点进行了人员的初始任务分配，然后根据每个节点的巡检周期，得到关于所有任务的开始工作时刻序列，结束工作时刻序列，任务对应节点序列，并以此建立了巡检人数最少和工作量尽量均衡的双目标0-1规划模型；对错时上班问题，考虑了每个人上班时间可调整情况下，巡检人数最少和工作量尽量均衡的双目标0-1规划模型，并设计算法进行求解。

关键词：巡检；TSP模型；最优路线；优化模型

中图分类号：TP391 文献标识码： A 文章编号：1009-3044（2018）19-0234-02

1 问题提出

某化工厂的巡检，需要考虑26个点需要进行巡检以保证正常生产，各个点的巡检周期、巡检耗时、两点之间的连通关系及行走所需时间（数据参见2017年全国大学生数学建模竞赛C题附件1）。建立相关数学模型来安排巡检人数和巡检路线。

针对该问题，需要完成三种情况下的计算。一是固定上班时间，不考虑巡检人员的休息时间情形；二是固定上班，但巡检人员有休息情形；三是错时上班情形。

问题1. 如果采用固定上班时间，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8小时左右，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。

问题2. 如果巡检人员每巡检2小时左右需要休息一次，休息时间大约是5到10分钟，在中午12时和下午6时左右需要进餐一次，每次进餐时间为30分钟，仍采用每天三班倒，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检的时间表。

问题3. 如果采用错时上班，重新讨论问题1和问题2，试分析错时上班是否更节省人力。

2 问题分析

针对问题1， 我们将所有26个节点分成若干个区域，每个区域内的节点满足：（1）按最短路线行走和巡检，巡检走完所有节点并回到开始点，其所花时间不超过该区域内所有节点的最小周期。（2）每个节点在一个周期内必须巡检一次，因此要满足首次到达该节点的时间不能超过该节点的周期。该问题本质上是一个多TSP问题。我们要建立模型，寻找满足两个条件的最少划分区域。

针对问题2，由于每个工人工作两小时后要休息5-10分钟，而且中午12点和下午4点要吃饭花30分钟左右。这样采用问题1的静态划分方式就不行了，需要采用动态方式，使工人在需要的时候自动在全区去完成当前任务。我们拟建立一般模型，并设计算法进行计算。

针对问题3，采用错时上班，每个人可以在一天的任意时间上班，只要连续工作8小时就可以。我们仍然建立一般模型，并进行动态调整，当有任务而当前无法完成时，就可以增加一个人去完成。这样对可能更能节省人力，提高效率。

3 模型建立与求解

问题一：

该问题中采用固定上班时间，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8小时左右。我们考虑将26个节点分成若干个区域，每个区域内的节点满足：（1）按最短路线行走和巡检，巡检走完所有节点并回到开始点，其所花时间不超过26个节点的最小周期35分钟。（2）同时由于各节点周期不同，每个节点在一个周期内必须巡检一次，因此要满足首次到达该节点的时间不能超过该节点的周期。我们的任务就是寻找满足该条件的最少划分区域。本质上是一个多TSP问题。

根据上面可确定的每个节点初次到达时刻。设第[i]个节点初次到达时刻为[ti]，该点巡检周期为[Ti]，则该点后面的任务序列为[t=ti+ki.Ti] ，其中[ki=480-tiTi]，其中[]表示向下取整。这里[ki]表示不超过8小时的最大巡检次数。对附件中的初始分配，可计算得到所有26个节点可计算得到任务序列为258个。

首先利用Floyd算法和附件所给出的连通图，计算出所有节点两两之间的最短路，即相互到达的最小时间，给定初始人数[m]，根据问题1，开始可取[m=5]进行计算。将[m]个人进行初始分配，分配方式可采用前面介绍方式进行，共同对26个节点进行首次巡检，得到每个节点的首次访问时间。设第[i]个节点的首次巡检时间为为[ti]，该点巡检周期为[Ti]，则该点后面需要完成的的任务序列为[t=ti+ki.Ti] ，其中[ki=480-tiTi]。当如果全天考虑时（问题3），只需要取总时间为24*60=1440分钟。其中[]表示向下取整。这里[ki]表示不超过8小时的最大巡检次数。

利用循环计算，我们可以很容易统计出每个人工作时间，每个人每次执行的任务及所在的节点序号。

我们将每天分为3班。第一班知需要每工作两小时左右休息5～10分钟；第二班不但休息，还含有12时需要吃饭花30分钟左右；第三班也是不但需要休息，还含有下午6时需要吃饭花30分钟左右。我们计算结果为：第一班需要人数为5人，第二班需要人数为6人，第三班需要人数为6人，总共需要20人，比问题1多了2人，各班任务均衡度都比问题1均衡度55.28更好。说明动态调整也更有利于工作量均衡。

问题三：

对错时上班，对每个人不再有固定开始上班时间。可以根据任务需要随时参与巡检，只要工作满8小时，则下班不再工作。

则在问题2前面模型中，初始时不再让所有人都在开始时刻上班。设第[i]个人最后一次巡检时刻[di]，则：

通过该算法，我们同样可以计算得到需要的结果信息。这里我们考虑在问题1情形（不休息），采用初始6人参与分派任务方式。得到初始安排以后剩余的总任务有828项。计算得到总共需要安排人员15人。每个人的任务安排见表13。人员序号按工作先后编号。

问题2情形（含休息和吃饭），我们采用初始6 人分配任务，采用错时上班。得到初始安排以后剩余的总任务有828项。计算得到最终需要17人。

从该结果来，对问题1情形，每天总人数仍然为15人，但任务的均衡性得到大大改善，由原来的55.28降为23.42，大大得到改善。对问题2需要工作和吃饭情形，每天需要总工人数为17人，而问题2按固定班次计算总人数为19人，这样按错时安排，总人数比原来问题的总人数减少2人，均衡性也比起最小的均衡度35.23小，说明其均衡性也得到改善。

4 模型的评价与推广

对化工厂安排工人巡检问题，是一个具有一般性的调度安排问题，在实际中具有重要作用。本文对问题1采用多TSP划分区域，求解后人员使用操作简单，每个工作在自己固定区域巡检。所建双目标规划模型合理地表达了问题，便于使用和利用模型来验证、求解。

该模型简单明了，容易理解，可以灵活的运用，具有很强的使用价值，因此可以将该模型推广于相关行业的排班和人员安排。

参考文献：

[1] 戴朝寿.数学建模简明教程[M].北京：高等教育出版社，2008.

[2] 韩中庚.数学建模方法及其应用[M].北京：高等教育出版社，2005.

[3] 肖华勇.实用数学建模与软件应用[M].西安：西北工业大学出版社，2008.