搜索
2017D题*12017D题巡检线路的排班某化工厂有26个点需要进行巡检以保证正常生产，各个点的巡检周期、巡检耗时、两点之间的连通关系及行走所需时间在附件中给出。每个点每次巡检需要一名工人，巡检工人的巡检起始地点在巡检调度中心（XJ0022），工人可以按固定时间上班，也可以错时上班，在调度中心得到巡检任务后开始巡检。现需要建立模型来安排巡检人数和巡检路线，使得所有点都能按要求完成巡检，并且耗费的人力资源尽可能少，同时还应考虑每名工人在一时间段内（如一周或一月等）的工作量尽量平衡。22017D题巡检线路的排班问题1：如果采用固定上班时间，不考虑巡检人员的休息时间，采用每天三班倒，每班工作8小时左右，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检时间表。问题2：如果巡检人员每巡检2小时左右需要休息一次，休息时间大约是5到10分钟，在中午12时和下午6时左右需要进餐一次，每次进餐时间为30分钟，仍采用每天三班倒，每班需要多少人，巡检线路如何安排，并给出巡检人员的巡检线路和巡检时间表。问题3：如果采用错时上班，重新讨论问题1和问题2，试分析错时上班是否更节省人力。3基本信息表（巡检总耗时67分钟）位号周期（分）巡检耗时（分）位号周期（分）巡检耗时（分）XJ-0001XJ-0002XJ-0003XJ-0004XJ-0005XJ-0006XJ-0007XJ-0008XJ-0009XJ-0010XJ-0011XJ-0012XJ-001335503535720358035351203535803232232342325XJ-0014XJ-0015XJ-0016XJ-0017XJ-0018XJ-0019XJ-0020XJ-0021XJ-0022XJ-0023XJ-0024XJ-0025XJ-002635353548035353580353535120353232223323222451、问题分析问题所属类型：旅行商问题（TSP），或者是带有时间窗口的车辆路径问题。可通过最短路算法，结合启发式得到结果。巡检路径的设计本二人人宝2固时上班错时上班不进餐、不休息进餐、休息不考虑不进餐、不休息进餐、休息不考虑62.巡检人员下限估算图172.巡检人员下限估算为估算巡检人员数量的下限，先计算旅行商问题所需要的时间（包括路程时间和巡检耗时）其中：路程耗时：68分钟（79-11）检查耗时：67分钟共计：135分钟由于巡视点两次巡视最小间隔时间是35分钟，即135≈435因此，一个班至少需要4名工人。83.问题1的求解题目要求：每名工人均从22点开始巡视。通过分析可知，每个班需要5名工人，故需要将26个巡视点划分成5个区域，每个区域最多包含6个点，最少也要有4个点，其目的是保证每个区域的工作量（巡视时间）尽量平衡。因此，距22点较近的点可多安排一些，而距22点较远的点则少安排一些。具体需求安排，需要计算从22点至其余各点的最短路，可通过Dijkstra（戴克斯特拉）算法或者LINGO程序完成。922号点到各点的最短路及时间10将相同点较多路线合并，得到如表所示路线：到达点经过路径最短时间（min)722-21-4-2-3-5-7101891222-23-24-9-25-26-15-1222-21-4-2-3-6-141421622-21-4-2-3-6-10-11-13-16198171822-23-24-9-25-1722-23-24-9-25-26-15-1818192622-20-19422-23-24-9-25-261011通过最短路径与巡检耗时得到5条路线注：同一颜色为一区域路线1：蓝色；路线2：红色；路线3：橘色；路线4：绿色；路线5：紫色1215条路线及巡检耗时分别为：路线一：22→21→4→1→3→6→14（6个点）巡检耗时：35min路线二：22→20→19→2→5→7巡检耗时：35min（5个点）路线三：22→23→24→9→25→26（6个点）巡检耗时：35min路线四：22→17→8→10→12→15（5个点）巡检耗时：35min路线五：22→18→16→13→11巡检耗时：31min（4个点）13也可以这样划分5条路线：14相应的5条路线及巡检耗时分别为：•第1组：22、20、19、2、4和21点；（6个点）•巡视周期29min；•第2组：23、24、9、8、17和25点；（6个点）巡视周期32min；•第3组：1、3、6、14、5和7点；（6个点）巡视周期32min；•第4组：26、15、18和12点；（4个点）巡视周期28min；•第5组：11、13、16和10点；（4个点）巡视周期25min。••••15问题1的结论：班次上班时间下班时间巡检人员数第一班次第二班次第三班次8:0016:000:0016:000:008:00555固定上班每班需要5人，一天共需15人。16第1组巡视时间表174.问题2的求解4.1休息时间可通过减少巡检周期大于35min的巡检点巡检次数得到，若线路中无大于35min周期的巡检点或压缩时间太少，可将线路分段并增加巡检人员。4.2进餐时间可以通过调整各班次上下班时间，使得各班次进餐时由下一班次顶替。如：第一班巡检人员11：00下班进餐，则第二班次在11：00上班。进餐时间安排可适当放宽在11时至13时之间和17时至19时之间。18固时进餐休息各班次上下班时间及巡检人员数班次上班时间下班时间巡检人员数第一班次第二班次第三班次3:0011:0019:0011:0019:003:00666194.3问题2的另解排班方法如下：•问题1中原排班时间不变；•进餐时间安排在11时至13时之间和17时至19时之间；•进餐时间为35分钟（最小巡视周期）；•进餐时由第6名（机动）工人完成巡视工作；•第6名（机动）工人进餐时间可灵活安排在替班前后。以第2组为例：23、24、9、8、17和25点；（6个点）巡视周期32min.204.3.问题2的另解第2组巡视时间表（黄色部分为进餐时间）214.3.问题2的另解第6名工人（机动）巡视时间表接替顺序：2→1→3→5→4接替时段：10:54~13:5717:10~20:1522问题2的结论：班次上班时间下班时间巡检人员数第一班次第二班次第三班次8:0016:000:0016:000:008:00555固定上班每班需要5人，考虑休息进餐时间，需增加一名机动工人作为替补，一天共需16人。235.问题3的求解问题3要求：考虑错时上班能否更省人力??5.1不考虑休息进餐时间由前面分析可知，人员下限为每班4人。排班计划如下：1）让每名工人完成1轮（26个点）巡视；2）每名工人上班时间依次向后错35分钟；即在前一名工人开始巡视35min之后，再安排后一名工人巡视；3）对巡视间隔大于35min的点，在相应点处可休息。24Hamilton回路图255.问题3的求解具体排班方法如下：1第1名工人在8:00开始巡视；第2名工人在8:35开始巡视；第3名工人在9:10开始巡视；第4名工人在9:45开始巡视。42第1名工人在第1轮巡视后休息5分钟；第1名工人在10:20开始第2轮巡视.3265.问题3的求解第1名工人具体巡视如下：在8:00开始第1轮巡视；在10:20开始第2轮的巡视；在12:40开始第3轮的巡视；在15:00结束第3轮的巡视；在每轮巡视后，均休息5分钟，共计巡视420min，即7小时.275.问题3的求解错时上班时间表l结论：不考虑休息进餐时间的错时上班，每班需要4人，一天共需12人（小于固时上班15人）。285.问题3的求解5.2考虑休息进餐时间排班方法如下：•错时排班时间不变；•进餐时间可适当放宽；•进餐时间为35分钟（最小巡视周期）；•进餐时第5名（机动）工人开始替换完成巡视工作；•第5名（机动）工人进餐时间可灵活安排在替班前后。295.问题3的求解5.2考虑休息进餐时间替换表第1人8:0010:2012:40换4第2人8:3510:55换113:15第3人9:1011:30换213:50第4人9:4512:05换314:25第1人15:0017:2019:40换4第2人15:3517:55换1第3人16:1018:30第4人16:4519:05换2换3结论：考虑进餐时间，再增加1人机动，每天共需13人，（小于固时上班16人）.305.问题3的求解增加进餐时间部分排班表31