护士工作时间调度问题.doc

题目：宾馆服务员工作时间调度问题
【摘 要】
本文利用整数规划模型，对宾馆服务员工作时间调度问题进行相关分析和研究。为简化约束条件，避免因变量过多而导致求解不便，本文假设每名服务员连续工作4小时后只能休息2小时，且在休息2小时后继续工作4小时。
针对问题一，建立了以满足需求时所需服务员人数最少为目标函数的整数规划模型I，利用LINGO软件求解得到满足需求时至少需要100名服务员，且在12个时段开始工作的服务员人数分别为23、17、12、0、0、11、17、13、7、0、0、0。由此调度表可以看出在凌晨00am—04am开始上班与下班的总人数为72人，占服务员总人数的72%，超过了一半，但在这段时间开始上班和下班的服务员在生活中会有很多的不便，会引起在这段时间上、下班的服务员的不满意。为降低不满意度，使工作时间安排更加合理和人性化，对模型I进行改进。本文建立了以满足需求时需要在凌晨00am—04am开始上班与下班的服务员人数最少为目标函数的整数规划模型II，利用LINGO软件求解得到了更加合理的工作时间调度表，在12个时段开始工作的服务员人数分别为5、0、5、15、20、15、20、0、0、0、10、10，这样在凌晨00am—04am开始上班与下班的总人数就只有10人，只占服务员总人数的10%。
针对问题二，要研究的是在限定宾馆服务员人数为80的前提下，为满足需求，安排最少的服务员加班。本文建立了以满足需求时加班人数最少为目标函数的整数规划模型III，利用LINGO软件求解得到满足需求时至少需要40人加班。类似问题一，在此安排下，需要在凌晨00am—04am开始上班与下班的总人数为25人，占总人数的31.25%。为了对模型III进行改进，本文建立了以满足需求时在凌晨00am-04am开始上下班的服务员人数最少为目标函数的整数规划模型IV，利用LINGO软件求解得到在这段时间上、下班的服务员人数为5人，占总服务员人数的6.25%，并且得到了更加合理的工作时间调度表。

关键词：整数规划模型 工作时间调度 LINGO软件 满意度

一、问题重述
在某宾馆中,一个工作日分为12个两小时长的时段，每个时段的服务员要求都不同。例如，在夜间只要求有很少几个服务员就够了，但在上午为了给客人提供退房和卫生服务，需要较多服务员。下表列出了每个时段的人员需求量。
每个时段的人员需求
编号 时段 需要服务员人数
0 00am―02am 15
1 02am―04am 15
2 04am―06am 15
3 06am―08am 35
4 08am―10am 40
5 10am―12pm 40
6 12pm―02pm 40
7 02pm―04pm 30
8 04pm―06pm 31
9 06pm―08pm 35
10 08pm―10pm 30
11 10pm―12am 20
问题1：请计算出为满足需求最少需要多少个服务员，假定已知每个服务员每天工作8小时，且在工作四小时后需要休息两个小时。
问题2：此部门目前只有80名服务员，这个数目不足以满足给定的需求。因此建议每天安排部分服务员加班。每天加班时间为2小时，且紧随在后一个四小时工作时段之后，中间没有休息。请给出服务员工作时间安排方案，以使需要加班的服务员数目最少。

二、模型假设
1、假设所有服务员都能保持全勤率；
2、假设所有服务员都能服从安排，准时上下班；
3、假设不考虑各种客观因素对服务员人数的影响；
4、假设没有突发事件发生，宾馆无需做出人员调整；
5、假设每个服务员每天工作8小时，且连续工作4小时后只能休息2小时，在休息2小时后连续工作；
6、假设在夜晚要上班的服务员所要休息的2个小时都在宾馆休息。

三、符号说明
：为满足要求至少需要的服务员人数；
：在服务员人数不满足要求时，至少需要加班的服务员人数；
：第个时段开始工作的服务员人数，(第1时段为00—02，第2时段为02—04第12时段为10—12)，；
：第个时段开始工作的服务员人数中不需要加班的人数，；
：第个时段开始工作的服务员人数中需要加班的人数，。

四、服务员人数最少问题的研究
4.1问题的分析
服务员每天工作8小时，且连续工作4小时后需要休息2小时，然后再接着工作4小时。例如：在第5时段内工作的服务员人数等于第5时段开始工作的服务员人数、第4时段开始工作的人数、以及第1个和第2个时段开始工作的服务员人数之和。即：在时段5中，正在工作的服务员分别是在时段1、2、4、5开始工作。例如：有个服务员在时段2开始工作，则她在时段2和时段3中将进行工作，在时段4休息，然后在时段5和时段6继续工作。
我们需要保证在每个时段都有足够的服务员在工作。所以以满足要求时需要工作的最少服务员人数为目标函数，服务员一天工作八小时，且连续工作四小时后需要休息2小时为约束条件，建立整数规划模型I，求出满足需求时需要服务员的最少人数。
4.2模型I的建立
已知该宾馆中,一个工作日分为12个两小时长的时段，每个时段的服务员人数要求都不同。但必须满足每个时间段都有足够的服务员在工作，并且每个服务员每天工作8小时，连续工作4小时后需要休息2小时。由此可以列出约束条件，然后以满足需求所需的最少服务员人数为目标函数的整数规划模型。
模型I如下：

4.3模型I的求解
利用LINGO软件编程求解可以得到结果（代码见附录1）。

图1 程序1的运行结果
结论：在每个服务员每天工作8小时，且连续工作4小时候需要休息2小时的条件下，该宾馆为满足工作量的需求至少需要100名服务员。
表1 模型I的工作调度表
时段号
时间段
开始工作人数
总工作人数
1
00am-02am
23
30
2
02am-04am
17
40
3
04am-06am
12
29
4
06am-08am
0
35
5
08am-10am
0
40
6
10am-12pm
11
40
7
12pm-02pm
17
40
8
02pm-04pm
13
40
9
04pm-06pm
7
31
10
06pm-08pm
0
35
11
08pm-10pm
0
30
12
10pm-12am
0
20
4.4模型I的改进
4.4.1问题的分析
由表1可以看出服务员在凌晨00am—04am开始上班与下班的总人数为72人（第1时段开始工作的23人，第2时段开始工作的17人，第3时段开始工作的12，第8时段开始工作的13人,第9时段开始工作的7人，第10时段开始工作的人数为0），占最少所需服务员总人数的72%,所占百分比很大，已经超过总人数的一半；但在这段时间开始上班和下班的服务员在生活会有很多的不便，比如乘车问题、安全问题等等。这会引起在这段时间上、下班的服务员的不满意。
为降低不满意度，使工作时间安排更加人性化，对上述模型I进行改进。以满足需求时需要在凌晨00am—04am开始上班与下班的总服务员人数最少为目标函数，建立模型II，求出更加合理、更加人性化的工作时间调度表。
4.4.2模型II的建立
改进的模型中，仍然必须保证每个时段都有足够的服务员在工作，服务员每天需工作8小时，且连续工作4小时后需要休息2小时，并且所需服务员人数保持最小值100人，由此可以列出约束条件，建立以满足需求时需要在凌晨00am—04am开始上班与下班的总服务员的人数最少为目标函数的整数规划模型II。
模型II如下：

4.4.3模型II的求解
利用LINGO软件编程求解可以得到结果（代码见附录2）。

图2 程序2的运行结果

表2 模型II的工作时间调度表
时段号
时间段
开始工作人数
总工作人数
1
00am-02am
5
15
2
02am-04am
0
15
3
04am-06am
5
25
4
06am-08am
15
35
5
08am-10am
20
40
6
10am-12pm
15
40
7
12pm-02pm
20
55
8
02pm-04pm
0
55
9
04pm-06pm
0
35
10
06pm-08pm
0
35
11
08pm-10pm
10
30
12
10pm-12am
10
20
4.4.4模型II的结果分析
由表2可以看出改进后的模型II中，服务员在凌晨00am—04am开始上班与下班的总人数为10人（第1时段开始工作的5人以及第3时段开始工作的5人，第2、8、9、10时段开始工作的服务员人数都为0），占总服务员人数的10%；而在未改进的模型I中，服务员在凌晨00am—04am开始上班与下班的总人数占服务员总人数的72%。比较可知改进后的模型II能在很大程度上降低服务员对工作时间安排的不满意度，其工作时间调度表更加合理、更加人性化。

五、加班人数最少问题的研究
5.1问题的分析
此宾馆目前只有80名服务员，这个数目不足以满足需求，故需要安排部分人加班。考虑到服务员每天只加班两小时，且紧跟随在后一个4小时工作时段之后，中间没有休息，同问题一类似分析，例如：在第5时段内工作的服务员人数等于此时段开始工作的服务员人数、第1个和第2个时段开始工作的服务员人数、第4时段开始工作的服务员人数以及第12时段开始工作的服务员人数中需要加班的服务员人数之和。所以以满足要求时加班人数最少为目标函数，建立模型III，求出满足需求时需要加班的服务员的最少人数。
5.2模型III的建立
不加班的服务员每天工作8小时，连续工作4小时候需休息2小时；需要加班的服务员在原工作的基础上每天加班2小时，且紧随在后一个4小时工作时段之后，中间没有休息；宾馆总共有80名服务员，由此可以列出约束条件，以满足需求时加班人数最少为目标函数建立整数规划模型。
模型III如下：

5.3模型III的求解
利用LINGO软件编程求解可以得到结果（代码见附录3）。

图3 程序3的运行结果
结论：在宾馆只有80名服务员，加班服务员每天加班时间为2小时，且紧随在后一个四小时工作时段之后，中间没有休息的条件下，该宾馆为满足工作量的需求至少需要40名服务员加班。
表3 模型III的工作时间调度表
时段号
时间段
需加班的人数
不加班的人数
开始工作人数
总工作人数
1
00am-02am
14
0
14
26
2
02am-04am
0
2
2
17
3
04am-06am
0
0
0
15
4
06am-08am
0
9
9
35
5
08am-10am
3
0
3
40
6
10am-12pm
11
10
21
40
7
12pm-02pm
0
11
11
41
8
02pm-04pm
0
7
7
30
9
04pm-06pm
0
0
0
31
10
06pm-08pm
0
0
0
35
11
08pm-10pm
0
1
1
30
12
10pm-12am
12
0
12
20
5.4模型III的改进
5.4.1问题的分析
在凌晨00am-04am开始上下班的包括：在第1、2、3、8、9、10时段开始工作且不需要加班的服务员，以及在第1、2、3、7、8、9时段开始工作但需要加班的服务员。由表3可以看出模型III中需要在这个时间段开始上下班的服务员人数为25人，占总服务员人数的31.25%，即占近三分之一的服务员。为了使工作时间调度表更加合理和更加人性化，对上述关于加班人数最少问题的模型III进行改进。使得在在凌晨00am-04am开始上下班的服务员人数最少，提高服务员的满意度。
5.4.2模型IV的建立
在改进后的模型中，条件依然为不加班的服务员每天工作8小时，连续工作4小时候需休息2小时；需要加班的服务员在原工作的基础上每天加班2小时，且紧随在后一个4小时工作时段之后，中间没有休息；宾馆总共有80名服务员；需要加班的服务员人数保持40人不变。由此可以列出约束条件，以在凌晨00am-04am开始上下班的服务员人数最少为目标函数，建立整数规划模型IV，求出更加合理更加人性化的工作时间调度表。
模型IV如下：

5.4.3模型IV的求解
利用LINGO软件编程求解可以得到结果（代码见附录4）。

图4 程序4的运行结果
改进后的工作时间调度表如下所示：
表4 模型IV的工作时间调度表
时段号
时间段
需加班的人数
不加班的人数
开始工作人数
总工作人数
1
00am-02am
0
5
5
15
2
02am-04am
0
0
0
15
3
04am-06am
0
0
0
20
4
06am-08am
0
15
15
35
5
08am-10am
10
5
15
40
6
10am-12pm
20
5
25
40
7
12pm-02pm
0
0
0
40
8
02pm-04pm
0
0
0
30
9
04pm-06pm
0
0
0
40
10
06pm-08pm
0
0
0
35
11
08pm-10pm
5
5
10
30
12
10pm-12am
5
5
10
20
5.4.4模型IV的结果分析
由表4可以看出在改进后的模型IV中，服务员在凌晨00am—04am开始上班与下班的总人数为5人（即在第1时段开始工作且不需要加班的5人），占总服务员人数的6.25%；而在未改进的模型III中，服务员在凌晨00am—04am开始上班与下班的总人数占服务员总人数的31.25%，两者进行比较，可以看出改进后的模型IV得到的工作时间调度表更加合理、更加人性化，能够大大提高服务员对工作时间安排的满意度。

六、模型的评价与推广
6.1模型的优点
文中的数据都采用表格的形式给出，更加清晰和直观；建立的整数规划模型通俗易懂，能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有良好的通用性和推广性；我们对模型进行改进，得到了更加合理和更加人性化的工作调度表，有很强的实用性；在模型求解时采用LINGO软件，算法简单，很容易编程实现，推广容易并且可信度高。
6.2模型的缺点
模型的建立在一定理想情况的得出的结果，未考虑各种客观因素的影响，难免有一些欠妥之处。例如，所建模型是建立在假设每名服务员连续工作4小时后只能休息2小时，且在休息2小时后继续工作4小时的基础上。这个假设使得所建模型更加简单但存在一定的不合理性，因为在实际生活中，服务员在连续工作4小时后可以休息不止2小时，然后再进行接下来的工作。
6.3模型的改进与推广
6.3.1模型的改进
本文中建立的模型假设了每名服务员在连续工作4小时后只能休息2小时，在休息2小时后连续工作。在实际工作中，服务员在工作时间内，可能会有特殊情况需要请假；服务员上班时间不连续；或者是有突发事件导致所需服务员人数增加。考虑以上因素，可建立一个工作时间不连续的整数规划模型，用枚举法可得出在工作时间不连续的情况下的最优人数与工作时间安排。
6.3.2模型的推广
本文中建立的整数规划模型不仅可以解决宾馆服务员工作时间调度问题，也可以应用于其它领域，比如超市工作人员的时间调度问题、图书馆工作人员的值班问题等等。

参考文献
[1] 姜启源 谢金星 叶俊，《数学模型》（第三版），北京：高等教育出版社，2003。
[2] 牛映武，《运筹学》，陕西：西安交通大学出版社，1994。
[3] 何坚勇，《最优化方法》，北京：清华大学出版社，2007。
[4] 袁新生，《LINGO和Excel在数学建模中的应用》，北京：科学出版社，2007。

附录
附录1
%模型I的LINGO程序1
min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12;
x9+x10+x12+x1>=15;
x10+x11+x1+x2>=15;
x11+x12+x2+x3>=15;
x12+x1+x3+x4>=35;
x1+x2+x4+x5>=40;
x2+x3+x5+x6>=40;
x3+x4+x6+x7>=40;
x4+x5+x7+x8>=30;
x5+x6+x8+x9>=31;
x6+x7+x9+x10>=35;
x7+x8+x10+x11>=30;
x8+x9+x11+x12>=20;
@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);
@gin(x7);@gin(x8);@gin(x9); @gin(x10);@gin(x11);@gin(x12);
运行结果如下：

附录2
%模型II的LINGO程序2
min=x1+x2+x3 +x8+x9+x10;
x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12=100;
x9+x10+x12+x1>=15;
x10+x11+x1+x2>=15;
x11+x12+x2+x3>=15;
x12+x1+x3+x4>=35;
x1+x2+x4+x5>=40;
x2+x3+x5+x6>=40;
x3+x4+x6+x7>=40;
x4+x5+x7+x8>=30;
x5+x6+x8+x9>=31;
x6+x7+x9+x10>=35;
x7+x8+x10+x11>=30;
x8+x9+x11+x12>=20;
@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);
@gin(x7);@gin(x8);@gin(x9); @gin(x10);@gin(x11);@gin(x12);
运行结果如下：

附录3
%模型III的LINGO程序3
y8+w1+y1+w9+y9+w10+y10+w12+y12>=15;
y9+w1+y1+w2+y2+w10+y10+w11+y11>=15;
y10+w2+y2+w3+y3+w11+y11+w12+y12>=15;
y11+w1+y1+w3+y3+w4+y4+w12+y12>=35;
y12+w1+y1+w2+y2+w4+y4+w5+y5>=40;
y1+w2+y2+w3+y3+w5+y5+w6+y6>=40;
y2+w3+y3+w4+y4+w6+y6+w7+y7>=40;
y3+w4+y4+w5+y5+w7+y7+w8+y8>=30;
y4+w5+y5+w6+y6+w8+y8+w9+y9>=31;
y5+w6+y6+w7+y7+w9+y9+w10+y10>=35;
y6+w7+y7+w8+y8+w10+y10+w11+y11>=30;
y7+w8+y8+w9+y9+w11+y11+w12+y12>=20;
y1+y2+y3+y4+y5+y6+y7+y8+y9+y10+y11+y12+w1+w2+w3+w4+w5+w6+w7+w8+w9+w10+w11+w12=80;
@gin(y1);@gin(y2);@gin(y3);@gin(y4);@gin(y5);@gin(y6);@gin(y7);@gin(y8);
@gin(y9);@gin(y10);@gin(y11);@gin(y12);@gin(w1);@gin(w2);@gin(w3);@gin(w4);
@gin(w5);@gin(w6);@gin(w7);@gin(w8);@gin(w9);@gin(w10);@gin(w11);@gin(w12);
min=y1+y2+y3+y4+y5+y6+y7+y8+y9+y10+y11+y12;
运行结果如下：

附录4
%模型IV的LINGO程序4
min=w1+w2+w3+w8+w9+w10+y1+y2+y3+y7+y8+y9;
y8+w1+y1+w9+y9+w10+y10+w12+y12>=15;
y9+w1+y1+w2+y2+w10+y10+w11+y11>=15;
y10+w2+y2+w3+y3+w11+y11+w12+y12>=15;
y11+w1+y1+w3+y3+w4+y4+w12+y12>=35;
y12+w1+y1+w2+y2+w4+y4+w5+y5>=40;
y1+w2+y2+w3+y3+w5+y5+w6+y6>=40;
y2+w3+y3+w4+y4+w6+y6+w7+y7>=40;
y3+w4+y4+w5+y5+w7+y7+w8+y8>=30;
y4+w5+y5+w6+y6+w8+y8+w9+y9>=31;
y5+w6+y6+w7+y7+w9+y9+w10+y10>=35;
y6+w7+y7+w8+y8+w10+y10+w11+y11>=30;
y7+w8+y8+w9+y9+w11+y11+w12+y12>=20;
y1+y2+y3+y4+y5+y6+y7+y8+y9+y10+y11+y12+w1+w2+w3+w4+w5+w6+w7+w8+w9+w10+w11+w12=80;
y1+y2+y3+y4+y5+y6+y7+y8+y9+y10+y11+y12=40;
@gin(y1);@gin(y2);@gin(y3);@gin(y4);@gin(y5);@gin(y6);@gin(y7);@gin(y8);
@gin(y9);@gin(y10);@gin(y11);@gin(y12);@gin(w1);@gin(w2);@gin(w3);@gin(w4);
@gin(w5);@gin(w6);@gin(w7);@gin(w8);@gin(w9);@gin(w10);@gin(w11);@gin(w12);
运行结果如下：

13