工作时间调度问题

《工作时间调度问题》由会员分享，可在线阅读，更多相关《工作时间调度问题（22页珍藏版）》请在金锄头文库上搜索。

1、第 0 页，共 22 页2012 年武汉大学数学建模选拔赛承 诺 书我仔细阅读了 2012 年武汉大学数学建模选拔赛的竞赛细则。我完全明白，在竞赛开始后参赛选手不能以任何方式（包括电话、电子邮件、网上咨询等）与其他任何人（包括指导教师）研究、讨论与赛题有关的问题。我知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我将受到严肃处理。参赛选手 (签名) ： 12012 年武汉大学数学建模选拔赛编 号 专

2、 用 页论文标题：工作时间调度优化模型 选手姓名：史俊霞 选手学号：2010302540214 选手所在学院：电气工程学院 选手所在年级专业：2010 级 电气工程与自动化专业 选手联系电话：18707190308 选手 E-mail： （以下内容参赛选手不需要填写）竞赛评阅编号： 2题目：工作时间调度优化模型【摘 要】通过对问题的分析，这个时间调度问题可以归结为一个整数规划问题，本论文中根据题目所给的条件以及现实实际情况依次建立起来两个模型，在设计模型的过程中把约束条件逐渐放宽，逐步优化，使模型由浅及深，由简单到复杂。论文中并且对各个模型的优点和缺点进行了横向分析，最终对两个模型进行纵向比较

3、，结合现实生活中的实际需要，为实际的需要提出了自己的建议。本论文中通过设出决策变量，根据题目给出的条件将服务员在岗的时段确定下来，从而根据约束条件列出约束方程，建立线性规划模型，结合模型特点，利用 Lingo 软件求解，得到结果，并进行分析和拓展。本论文引入了工作方式的概念，在模型一中，约束条件比较严格，每个工作日需要工作的 8 小时分成两个 4 个小时的部分，中间休息的时间为 2 个小时。论文中分别设各个时段工作的人数为变量，从而将各个时段在岗人员数表示出来，得到约束方程，结果为=100，加班=40 人；同时可以得到加班时的班次安排表（表 5） ，针对某时段中在岗人数超过需求人数等不合理之处

4、，在模型二对约束条件进行了修改，将中间休息的时间可以调整为 ( =1,27)，使得时间调度更加灵活，得出=88，加班的人员有2n=26 人，无论是人力资源成本还是加班工人比例都得到很大改进。【关键词】：时间调度；整数规划模型；LINGO31 问题重述21 世纪追求性价比的时代使得低投入，高产出的高效率成为现代化的经营管理理念。因此根据工作的实际需要以及工作时间安排的人性化需求对工作时间调度进行合理的优化具有明显的现实意义。在某宾馆中，一个工作日分为 12 个两小时长的时段，由于每个时段的客流量不尽相同，因此对服务员数量的要求也随时间的变化产生差异，具体每个时段所需要的服务员人数见表 1 所示。

5、建立适当的数学模型，在综合考虑满足客人需要以及时间安排人性化的基础上，尽量减少成本（包括人力资源成本以及管理成本） 。第一个问题中限制了每个服务员每天必须工作 8 个小时，并且在工作四小时后需要休息两个小时。由题意可知，八个小时应该分成两个四小时的时段，并且在两个时间段之间必须休息两个小时。因此每个服务员的工作方式即已经确定，在这种情况下需要的最少的服务员数量。第二个问题是已知总共有 80 个服务员，显然不能满足需要，因此需要在其中安排一部分人加班，并且加班方式也是确定的，在第二个 4 小时的时段之后再连上两个小时，在这种情况下要求使得加班人员的数量最少。表 1 每个时段的人员需求编号 时段

6、需要服务员人数0123456789101100am02am02am04am04am06am06am08am08am10am10am12pm12pm02pm02pm04pm04pm06pm06pm08pm08pm10pm10pm12am15151535404040303135302042 问题分析问题一规定了每个服务员每天的工作时间，休息时间及休息时间的具体安排，需要求出在满足酒店运营要求的前提下的最少服务员个数。要使所需的员工数量最少，则必须保证一个员工在他的一天工作当中，中途休息时间最少，即只能按照工作 4 小时，休息 2 小时，再工作 4 小时，这样就能保证员工在酒店的服务有效时间最大化利

7、用。通过分析可以知道，问题一是一个整数规划问题，基于此建立使得岗人数最少的整数规划模型，根据题目要求添加相应的约束条件，再运用 lingo 求解，即可得到问题一的答案。问题二限定了服务员的人数，要保证酒店的服务正常进行，必须安排部分人员加班，每天加班时间是固定的，加班的时间段安排也是固定的（紧随在一个 4 小时时间段后且没有休息） ，同时也要满足问题一中的基本要求，同问题一一样，问题二同样是整数规划问题，但是问题二涉及到加班，就必须要增加相应的约束条件使得加班的安排更加合理和人性化。同样建立基于在岗人数最少的整数规划模型，运用 lingo 求解。3 模型假设假设一，宾馆是一个管理严格的系统，不

8、会存在服务员的旷工、迟到、早退等情况的发生。也忽略特殊情况如请假、人流突增等的影响。假设二，每个工作日的排班表都是相同，每天循环进行。即在 11 时段工作之后，0 时段继续工作也视为连续工作。4 符号说明模型一：不加班情况下需要的服务员数量;( i=0,1,211 ) ：第 i 时段开始时第一次上班的服务员数量；( i=0,1,211 )： 第 i 时段开始时，之前上过班，本时段又要上班的服务员数量；( i=0,1,211 ) ：第 i 时段结束时由于已经连续工作两个时段需要休息两个小时的服务员数量；( i=0,1,211 ) ：第 i 时段所需要的服务员的数量；( i=0,1,211 ) ：

9、第 i 时段开始工作的需要加班的服务员数量；( i=0,1,211 ) ：第 i 个时段开始工作的不用加班的服务员的数量；5：问题二中需要加班的人数模型二：不加班情况下需要的服务员数量;(i=1,242) ：第 j 时段采用第 i 种工作方式的服务员的数量;(i=1,284) ：存在加班情况时第 j 时段采用第 i 种工作方式的服务员数量；(j=0,1,211) ：第 j 时段所需要的服务员的数量；：问题二中需要加班的人数5 模型一的建立与求解5.1 问题一求解这个优化问题的目标是使得满足要求的服务员的数量最少，要做的决策就是排班计划，安排每个时段上班下班的人员情况（a i，b i，c i 的

10、值） ，决策受到几个条件的限制：工作方式、每个时段所需要的服务员数量。设出某服务员开始上班的时段，该名服务员在岗的时段即可以确定下来。按照题目所给出的条件，将决策变量、目标函数、和约束条件用数学符号和式子表示出来，就可以得到下面的模型。（1）目标函数需要的服务员的数量为：（1）110miniQa（2）约束条件首选我们分析一下第 时段的服务员来源，它主要是包含四个部分： 时段、i 4i时段， 时段，以及 时段新上岗的，表示如下：3i1i时段 -4 -3 -2 -1 +1 +2图 1 第 时段的服务员来源i是指第 时段开始时，之前上过班本时段又要上班的服务员数量，包括 3 个部分：i以前上过两个、

11、四个、六个小时。分别与之对应：=+ （2）(注： 若出现负值，用 12+ 取代，因为假设了工作安排的循环)i i表2 某服务员上班方式表示6时段 -1i上班 是 是 否 是 是是指第i时段结束时由于已经连续工作两个时段需要休息两个小时的服务员数量，因此有：（3）101()iicaca对于每一个时间段而言，必须满足酒店的服务要求，则有：+= ( =0,1,211 ) （4）同时， 、 和 都是自然数，定义 为自然数集合，则可以得出问题一的 整数iaibicN线性规划模型： 110miniQa1340.()(,1),iiiiiiiabstcabNL（3）模型求解将目标函数及约束条件输入到 Ling

12、o11 中运行求解，可以得到结果（程序语句以及输出结果参见附录 1、2） ，可以得到优化结果为 。由实验输出结果可以排1min0Q出工作时间调度表为：表 3 模型一下问题一的时间调度安排人数时段0 0 30 01 5 10 02 15 14 53 20 15 154 15 25 205 5 35 156 0 40 57 1 35 08 10 21 19 20 15 1010 9 21 2011 0 20 9（4）模型检验与分析7图 2 模型一结果与实际需求比较从图中可以看出，在岗人数为左侧长条，需求的人数是右侧的长条，可见，每个时段的安排都满足需求，但是有几个时段在岗的服务员数量大于需要的数量

13、，差值比较大。分析之后发现由于工作方式限制比较严格而致，也就是说，由于每个人的工作方式只能是先工作 4 个小时，再休息 2 个小时，接着工作 4 个小时，为了保证每个时段有满足需要的人数，必须这样安排。如果可以将上班的方式设置的更加灵活，约束条件即将会变少，从而将会减少需要的人数。接下来的模型二就是优化了这个条件，改变了假设，将工作方式做出了相应的调整，得出了更加满意的结果。5.2 问题二求解实际条件限制了只有 80 个服务员，因此必须要安排一定数量的服务员加班才能满足要求。加班的方式也是确定的：在完成第二个 4 小时的工作之后，接下来马上进行2 个小时的加班。可以设加班的人数为 ，非加班的人

14、员数量为 ，则 ， 的约束条xyxy件可以明显得出。加班的人员可以分成， （ 从 0 到 11） ，分别表示第 个时段开始工作i i的加班人员和非加班人员。对于， ，前者将要工作接下来的 、 +1、 +3、 +4、 +5 时i i段，而后者只是工作接下来的 、 +1、 +3、 +4 时段，如表 4 所示。则每个时段工作ii的人数即可以确定，由约束条件即可解出安排表。表 4 时段开始上班的服务员工作方式示意图i时段 i+1上班情况 、 都休息 不再上（1）目标函数模型建立的目的是要求出最少的加班人员数量以及加班的安排，因此加班的服务员数量就是目标变量，因此可以得到目标函数为：110miniPx（

15、5 ）0 1 2 3 4 5 6 7 8 9 10 118（2）约束条件要求第 个时间段在岗的人员必须不小于，而第 时段在岗的人数可以分成五部分：i i已经工作了 0、2、4、6、8 个小时的服务员，其中已经工作了 8 个小时的服务员一定是原来 时段加班的，分别与之对应可以得到：5i= （6）（注：如果出现负值 则用 12+ 表示）ii同时限制总人数总人数只有 80 人，因此：（7）108ixy都是自然数，定义 为自然数集合，则可以得出问题二的整数线性规划模型：,ixyN110miniPx34110()()()()8.,iiiiiiiiiiixyyyxnstNL（3）模型求解将目标函数及约束条件输入到 Lingo11 中运行求解，