世博会历史-基建工作总结

武汉大学2012年数模选拔赛赛题完整解答（参考）


题目：_________服务员工作时间调度最优模型_________
【摘 要】

本文主要建立整数规划模型解决服务员工作时间调度 的问题。在满足每个时段需要
工作的最少服务员人数的前提下，考虑到服务员工作4小时后只休息2小时 后又继续工
作四小时，休息时间较短和夜间上班服务员所占比例大，服务员对夜间加班的满意度问
题，进行两次人性化优化，得到最佳工作时间人员安排。

模型I、II、III：针 对问题1，考虑到每个服务员一天工作8小时，且连续工作4
小时后需要休息2小时，我们建立了以满足 需求时需要工作的最少服务员人数为目标函
数的整数规划模型。用
LINGO
软件求解 得到满足需求至少需要的服务员为100名。进
一步考虑到服务员两次工作4小时之间只休息2小时，休 息时间较短，不太合理，于是
将每个服务员工作中间的休息时间调为4小时，进行第一次优化，得到模型 II,用
LINGO
软件求得此时所需服务员至少为88名。
又考虑到第一次优化后 凌晨0：00到早上6：00这段时间，安排上班的人有35人，
占总数的39.8%，比较大，考虑到 人的生物钟，这段时间内需要睡眠，在这个时间段上
班的服务员需要从睡眠状态进入工作状态，会引起此 阶段上班的服务员对工作调度安排
的不满。为了降低不满意程度，需要进行第二次优化。以凌晨0：00 到早上6：00需要
工作的服务员人数最少为目标函数，建立模型III。用
LINGO
软件求得凌晨0：00到早
上6：00需要工作的服务员人数为30人，占总人数的34.6%，且这 三阶段工作的人数恰
好等于这阶段所需的最少人数。故此时得到的调度方案为此假设前提下最优解。

模型IV、VI、VII：针对问题2，在宾馆服务员人数不足的情况下需 要部分服务员
加班。同问题1类似分析，建立以需要加班的服务员人数最少为目标函数的整数规划模型。用
LINGO
软件求得需要加班的最少服务员人数为40人。
同模型II分 析，将每个服务员工作中间的休息时间调为4小时，将模型III进行
第一次优化，得到模型IV,用< br>LINGO
软件求得需要加班的最少服务员人数为26人。此
时凌晨0：00到早上6： 00这段时间，安排上班的人有39人，占总员工的48.75%。
同模型III分析，为了降低夜间 上班的不满意程度，以凌晨0：00到早上6：00需
要工作的服务员人数最少为目标函数，建立模型V II。用
LINGO
软件求得凌晨0：00到
早上6：00需要工作的服务员人数为2 6人，占总员工数的32.5%。并得出此方案下服务
员每个时段的调配方案。

最后讨论了本文所建模型的优点和缺点，针对其缺点提出了改进了方案并简述了该
模型的推广及应用。

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

一 问题重述
在某宾馆中,一个工作日分为12个两小时长的时段，每个时段的服务员要求都不同。
例如，在夜间只要求有很少几个服务员就够了，但在上午为了给客人提供退房和卫生服
务，需要较多服务 员。请你为宾馆制定服务员的工作时间表。下表列出了每个时段的人
员需求量。
问题 1：请计算出为满足需求最少需要多少个服务员，假定已知每个服务员每天工
作8小时，且在工作四小时 后需要休息两个小时。
问题2：此部门目前只有80名服务员，这个数目不足以满足给定的需 求。因此建议
每天安排部分服务员加班。每天加班时间为2小时，且紧随在后一个四小时工作时段之后，中间没有休息。请给出服务员工作时间安排方案，以使需要加班的服务员数目最少。
每个时间段的人员需求量
编号 时段 需要服务员人
数
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

二 模型假设
模型I、III的假设：
1、假设每个服务员都服从工作安排；
2、假设每个服务员都准时上、下班，在上班期间无特殊情况发生,不需要请假；
3、假设每 个服务员每天工作8小时，且连续工作4小时后只能休息2小时，在休息2
小时后连续工作；
模型II、IV的假设
在模型I的假设（1）（2）前提下，补充假设：
3 、假设每个服务员每天工作8小时，且连续工作4小时后休息4小时，在休息4小时
后连续工作；
模型III、VI的假设：
在模型II的前提下，补充假设：
4、凌晨0：00到早上6：00需要工作的服务员人数最少。

三 符号说明
Z
1
：为满足要求至少需要的服务员人数；
Z
2
：在服务员人数不满足要求时，至少需要加班的服务员人数；
m
i
：第
i
个时段宾馆需要服务员人数；
x
i< br>：第
i
个时段开始工作的服务员人数，(第1时段为00
am
—02< br>am
，第2时段
为02
am
—04
am

第12时段为10
pm
—12
am
；)，
(i1,2 12)
；
w
i
：第
i
个时段开始工作的服务员人数中不 需要加班的人数，
(i1,212)
；
y
i
：第
i
个时段开始工作的服务员人数中需要加班的人数，
(i1,212)
。

补充说明：
当
x
i1
、x
i3
、x
i4
分别等于 0、 -1、-2、-3时，
x
i1
、x
i3
、x
i4分别表示第12、11、
10、9个时段开始工作的服务员人数。


四 问题分析

问题1：
要保证在每个时段都有足够的服务员在工作。 考虑到服务员一天只工作8小时，且
连续工作4小时后需要休息2小时。
每个时段正在工作的服务员由四部分组成：
1.本阶段开始上班的服务员；
2.本阶段往前数第一个阶段开始上班的服务员；
3.本阶段往前数第三个阶段开始上班的服 务员，工作两时段后，休息两时段在本时
段开始继续工作；
4.本阶段往前数第四个阶段开始上班的服务员，工作两时段后，休息两时段后在本
时段工作。

用公式表达：
m
i
x
i
x
i1
x
i3
x
i4
（i1,2,3,4,12）

例如：

m
1
x
1
x
12x
10
x
9
m
2
x
2
x1
x
11
x
10
m
3
x
3x
2
x
12
x
11
依此类推。

以满足要求时需要工作的最少服务员人数为目标函数，服务员一天工作八小时，且
连 续工作四小时后需要休息2小时为约束条件，建立整数规划模型，求出满足需求时需
要服务员的最少人数 。此工作时间安排可以满足宾馆需求，但此工作时间调度表，服务
员两次工作4小时之间只休息2小时， 休息时间较短，不太合理，于是将每个服务员工
作中间的休息时间调为4小时，进行第一次优化。
改变约束条件为：
（i1,2,3,4,12）

进一步考 虑到第一次优化后凌晨0：00到早上6：00这段时间，安排上班的人有35
人，占总数的39.8% ，比较大，考虑到人的生物钟，这段时间内需要睡眠，在这个时间
段上班的服务员需要从睡眠状态进入工 作状态，会引起此阶段上班的服务员对工作调度
安排的不满。为了降低不满意程度，需要进行第二次优化 。以凌晨0：00到早上6：00
需要工作的服务员人数最少为目标函数，建立模型III。
在模型II的基础上，添加约束条件：

m
i
x
ix
i1
x
i4
x
i5

minx(1)x(2)x(3)x(12)x(11)x(10)x(9)x(8)
;
利用
LINGO
软件求出更为合理的服务员工作时间调度表。


问题2：
此宾馆目前只有80名服务员，这个数目不足以满足 需求，故需要安排部分人加班。
考虑到服务员每天只加班两小时，且紧跟随在后一个4小时工作时段之后 ，中间没有休
息。用
LINGO
软件建立模型VI求出最少加班人数以及合理的服务员 工作时间调度表。
同问题一类似分析，每一个时段的工作人员由以下5部分组成：
1.本阶段不加班的开始上班的服务员和要加班的开始上班的服务员；
2.本阶段往前数第一个阶段不加班的开始上班的服务员和要加班的开始上班的服
务员；
3.本阶段往前数第三个阶段不加班的开始上班的服务员，和要加班的开始上班的服
务员；
4.本阶段往前数第四个阶段不加班的开始上班的服务员，和要加班的开始上班的服
务员；
5.本阶段往前数第五个阶段要加班的开始上班的服务员。
用公式表达为：
mi
w
i
w
i1
w
i3
w
i4
y
i
y
i1
y
i3
y
i4
y
i5
（i1,2,3,4,12）


同问题一，可以将每个服务员工作中间的休息时间调为4小时，进行第一次优化。

得到模 型IV，求出此约束条件下最少加班人数以及合理的服务员工作时间调度表。。
改变约束条件为： < br>m
i
w
i
w
i1
w
i4
w
i5
y
i
y
i1
y
i4
y
i5
y
i6
（i1,2,3,4,12）


同样，同问题1，在模型IV的条件下，考虑到凌晨0：00到早上6：00这段时间，安排上班的人有39人，占总员工的48.75%，所占比例大。我们对模型IV进行改进得到
模型 VII,建立以凌晨0：00到早上6：00这段时间工作人数最少为目标函数的规划模型，
用
LINGO
软件处理求得更为合理的服务员工作时间调度表。
在模型IV的基础上，添加约束条件即可。约束条件为：
minx(1)x(2)x( 3)x(12)x(11)x(10)x(9)x(8)
y(1)y(2)y(3) y(12)y(11)y(10)y(9)y(8)y(7);

（i1,2,3,4,12）


五 模型的建立与求解
针对问题一，建立初始模型I和优化模型II、III。
针对问题二，建立初始模型IV和优化模型VI、VII。
模型I：
首先，知某宾馆的一个 工作日分为12个时段，每个时段所需服务员的人数不同，
所以，必须保证每个时段都有足够的服务员在 工作；其次，每个服务员一天只工作8小
时，且连续工作4小时后需要休息2小时，所以可以给出约束条 件；接下来，建立以满
足需求至少需要的服务员人数为目标函数的整数规划模型。模型如下：
minZ
1


x

i
i1
1 2

x
1
x
9
x
10
x
1 2
15


x
1
x
2
x
1 0
x
11
15

xxxx15
231112< br>

x
1
x
3
x
4
x
12
35

xx
2
x
4
x
5< br>40

1

x
2
x
3
x< br>5
x
6
40

s.t.

x
3
x
4
x
6
x
7
40


xxxx40
578

4

x
5x
6
x
8
x
9
31

< br>x
6
x
7
x
9
x
10
4 0

xxxx40
781011


x
8
x
9
x
11
x
12
40
< br>*

x
i
Z

用
LINGO
软件求解，得：
为满足需求，最少需要的服务员人数为10 0人，且第1、2、

11、12时段新
安排工作的人数
x
1、
x
2

x
11
、
x
12
和总的工作人数如下表一所示：
表一

时间段
00:00-02:00
02:00-04:00
04:00-06:00
06:00-08:00
08:00-10:00
10:00-12:00
12:00-14:00
14:00-16:00
16:00-18:00
18:00-20:00
20:00-22:00
22:00-00:00

开始工作人数
23
17
12
0
0
11
17
13
7
0
0
0
总人数100

总工作人数
30
40
29
35
40
40
40
41
35
35
30
20


模型II：
工作时间调度表1可以满足宾馆需求，但此工作时间调度表 ，服务员两次工作4小时之
间只休息2小时，休息时间较短，于是将每个服务员工作中间的休息时间调为 4小时，
进行第一次优化。
minZ
1


x

i
i1
12

x
1
x
12
 x
9
x
8
15

xx
1
x
10
x
9
15

2

x
3
x
2
x
11
x
10
15

x
4
x
3
x
12
x
11
35

xxxx40
54112


x
6x
5
x
2
x
1
40
st
< br>
x
7
x
5
x
3
x
2
40

xxxx30
8643


x
9
x
7
x
5
x
4
31

xxxx35
865

10

x
11
x
9
x
7
x
6
30


x< br>12
x
10
x
8
x
7
20

用
LINGO
软件求解，得：

为满足 需求，最少需要的服务员人数为100人，且第1、2、

11、12时段新
安排工 作的人数
x
1
、
x
2

x
11
、
x
12
和总的工作人数如下表一所示：
表二

时间段
00:00-02:00
02:00-04:00
04:00-06:00
06:00-08:00
08:00-10:00
10:00-12:00
12:00-14:00
14:00-16:00
16:00-18:00
18:00-20:00
20:00-22:00
22:00-00:00

开始工作人数
0
10
5
18
10
20
5
2
1
4
1
12
总人数88
总工作人数
15
15
20
36
40
40
40
30
31
35
30
20

需求人数
15
15
15
35
40
40
40
30
31
35
30
20


从表二可以看出，优化后只需要88名服务员即可满足 每个时段的工作需要。相比
于模型一所需的100人，优化率为



10088
100
*100%22%

故问题一优化后所需最少服务员数量为88名。



模型III：
模型二的缺点是凌晨0：00到早上6：00这段时间，安排上班的人有35人，占总
数的39.8%，比较大，考虑到人的生物钟，这段时间内需要睡眠，在这个时间段上班的
服务员需要从 睡眠状态进入工作状态，会引起此阶段上班的服务员对工作调度安排的不
满。为了降低不满意程度，需要 进行第二次优化。
为了更直白分析模型二中的数据，用图表表示：

图一

定义：凌晨0：00到早上6：00这三个时段上班人数的多少反映了宾馆服务员对工
作时间调度表的满意度。这段时间开始上班和下班的人数越多，服务员对工作时间调度
表的满意度越小 ，这段时间开始上班和下班的人数越少，服务员对工作时间调度表的满
意度越大。
通 过该图可以看出：凌晨0：00到早上6：00这段时间，安排上班的人有35人，
占总数的39.8% ，比较大，考虑到人的生物钟，这段时间内需要睡眠，在这个时间段上
班的服务员需要从睡眠状态进入工 作状态，会引起此阶段上班的服务员对工作调度安排
的不满。为了降低不满意程度，需要进行第二次优化 。
服务员在凌晨0：00—6：00开始上班和下班的人是由第1、2、3、8、9、10、11、< br>12个时段开始工作的服务员人组成，因此在满足宾馆各个时段服务员需求的条件下，在
模型II 的基础上宾馆有88名服务员，对服务员的满意度可建立模型III，如下：
minx(1 )x(2)x(3)x(12)x(11)x(10)x(9)x(8)


用
LINGO
软件求解，得到如下调配安排。求得凌晨0：00到早上6：00需要工 作
的服务员人数为30人，占总人数的34.6%，比模型II的工作调度表更为合理，能在一
定程度上降低服务员对工作时间安排的不满意度。得到模型改进后的最佳工作时间安排
表三所示：



x
i
x
i1
x
i 4
x
i5
m
i

12

st


x
i
88

i1

xz*

i

表三
时间段
00:00-02:00
02:00-04:00
04:00-06:00
06:00-08:00
08:00-10:00
10:00-12:00
12:00-14:00
14:00-16:00
16:00-18:00
18:00-20:00
20:00-22:00
22:00-00:00

图二
开始工作人数
3
7
3
20
8
22
8
0
3
2
3
9
总工作人数
15
15
15
35
40
40
40
31
31
35
35
20
需求人数
15
15
15
35
40
40
40
30
31
35
30
20



由以上图表可得，经模型III优化后，
minx(1)x(2)x(3)x(12 )x(11)x(10)x(9)x(8)30

优化率


3530
30
*100%16.7%

模型IV：
已知，宾馆只有80名服务员，这个数目不足以满足需 求。所以要部分人加班；其
次，同模型I，只不过此模型中，每个时段内工作的服务员人数（包括需要加 班的服务
员人数和不需要加班的服务员人数这两部分）不仅仅是前几个时段和相对应的此时段开
始工作的服务员人数之和，还应加上某时段开始工作的服务员人数中需要加班的那一部
分。例如：在第6 时段内工作的服务员人数等于此时段开始工作的服务员人数、第5时
段开始工作的人数、第2个和第3个 时段开始工作的服务员人数以及第1时段开始工作
的服务员人数中需要加班的那部分服务员人数之和；最 后，建立以加班的服务员人数最
少为目标函数的整数规划模型如下：
12
minZ
2


i1
y
i


w
1
w
12
w
10
w
9
y
1
y
12
y
10
y
9
y
8
15


w
2
w
1
 w
11
w
10
y
2
y
1
y
11
y
10
y
9
15

wwww yyyyy15
320


w
4
w
3
w
1
w
12
y
4
y
3
 y
1
y
12
y
11
35

ww wwyyyyy40
421542112

5

w< br>6
w
5
w
3
w
2
y
6y
5
y
3
y
2
y
1
40< br>
s

w
7
w
6
w
4
w
3
y
7
y
6
y
4
y
3
y
2
40

wwwwyyyyy3075487543

8
w
9
w
8
w6
w
5
y
9
y
8
y
6
y
5
y
4
31


w
10
w
9
w
7
w
6
y
10
y9
y
7
y
6
y
5
35
wwwwyyyyy30
111


w
12
w
11
w
9
w
8
y
12
y
11
y
9
y
8
y
7
20
*

y
i
z
12


( w
i1
i
y
i
)80
**

y
i
z,w
i
z

利用
LINGO< br>软件求解，得到最少加班的服务员人数为40人，并求得各个时段开始
工作的人数、开始工作的人 数中不需要加班的人数及各个时段总工作人数如下表四所
示；

表四
时间段 不加班工作人数 要加班人数 开始工作人数 总工作人数
00:00-02:00 0 6 6 23
02:00-04:00 7 0 7 21
04:00-06:00 1 0 1 16
06:00-08:00 20 0 20 35
08:00-10:00 0 7 7 40
10:00-12:00 0 19 19 40
12:00-14:00 0 0 0 40
14:00-16:00 3 0 3 39
16:00-18:00 9 0 9 38
18:00-20:00 0 0 0 35
20:00-22:00 0 8 8 30
22:00-00:00 0 0 0 20
总加班人数
总人数100
40


模型VI
同问题一，假设每个服务员每 天工作8小时，且连续工作4小时后休息4小时，在
休息4小时后连续工作；建立模型VI。
12
minZ
2


i1
y
i


w
1
w
12
w
9
w
8< br>y
1
y
12
y
9
y
8
y
7
15

ww
1
w
10
w
9
y
2
y
1
y
10
y
9
y
8
15

2

w
3
w
2
w
11
w
10
y
3
y
2
y
11
y
10
y
9
15

< br>w
4
w
3
w
12
w
11
y
4
y
3
y
12
y
11
y
10
35

wwwwyyyyy40
54112541 1211


w
6
w
5
w
2
w
1
y
6
y
5
y
2
y
1
y
12
40
st


w
7
w
6
w
3
w
2
y
7
y
6
y
3
y
2
y
1
40

wwwwyyyyy30
874387432


w9
w
8
w
5
w
4
y
9
y
8
y
5
y
4
y
3
31
wwwwyyyyy35
965109654

1 0

w
11
w
10
w
7
w
6
y
11
y
10
y
7
y
6
y
5
30


w
12
w
11w
8
w
7
y
12
y
11
y
8
y
7
y
6
20
12


(x
i1
i
y
i
)80


y
i
z
*

w
i
z
*

利用
LI NGO
软件求解，得到最少加班的服务员人数为26人，并求得各个时段开始
工作的人数、开始 工作的人数中不需要加班的人数及各个时段总工作人数如下表五所
示；
表五
不加班
要加班 开始工 不加班总加班总工 总工作
时间段 工作人
人数 作人数 工作人数 作人数 人数
数
00:00-02:00 2 3 5 12 3 15
02:00-04:00 7 0 7 12 3 15
04:00-06:00 8 0 8 15 0 15
06:00-08:00 16 4 20 31 4 35
08:00-10:00 0 8 8 25 15 40
10:00-12:00 9 11 20 18 22 40
12:00-14:00 2 0 2 26 14 40
14:00-16:00 0 0 0 26 4 30
16:00-18:00 3 0 3 19 12 31
18:00-20:00 0 0 0 12 23 35
20:00-22:00 0 0 0 11 19 30
22:00-00:00 7 0 7 9 11 20
要加班总工作
总人数 人数为
为26 80


图三

由以上结果知，若将服务员两次工作时间之间的休息时间延长为4 小时，优化后只
需要26人加班，比起初始模型中的40人，优化率为：


4026
40
*100%35%

模型VII：
考虑到在模型VI的调配方案下，虽然用
LINGO< br>软件求得需要加班的最少服务员人
数为26人，但此时凌晨0：00到早上6：00这段时间，安 排上班的人有39人，占总员
工的48.75%，占很大比例，会引起这段时间内上班的服务员的不满， 故需要以凌晨0：
00到早上6：00需要工作的服务员人数最少为目标函数，建立模型VII。 minx(1)x(2)x(3)x(12)x(11)x(10)x(9)x(8)
y(1)y(2)y(3)y(12)y(11)y(10)y(9) y(8)y(7);


y
i
y
i1
y
i4
y
i5
y
i
y
i1
y
i4
y
i5
y
i6
m
i
< br>12

st


(y
i
w
i)80

i1

yz
*
,wz
*i

i


利用
LINGO
软件求解，得到优 化后的凌晨0：00到早上6：00需要工作的服务员
人数最少为26名，占总员工数的32.5%。并 得出此方案下服务员每个时段的调配方案如
下表六和图四。


表六
不加班开始不加班
要加班加班总工作总工作人
时间段 工作人工作总工作
人数 人数 数
数 人数 人数
00:00-02:00 3 4 7 7 8 15
02:00-04:00 4 0 7 7 8 15
04:00-06:00 5 0 1 9 6 15
06:00-08:00 22 2 20 31 4 35
08:00-10:00 2 1 7 31 9 40
10:00-12:00 13 13 19 22 18 40
12:00-14:00 1 0 0 23 17 40
14:00-16:00 0 0 3 28 2 30
16:00-18:00 0 4 9 24 7 31
18:00-20:00 0 0 0 15 20 35
20:00-22:00 0 2 8 14 16 30
22:00-00:00 4 0 0 5 15 20

图四

优化率




*100%33.3%



六 模型的评价与推广
本文建立了六个模型，模型I和模型IV运用了整数规划模 型解决了在满足需求时
所需服务员人数最少和加班人数最少的问题。
模型II和模型VI是在 考虑实际工作中每个服务员休息4小时候再工作较为人性化
后在模型I和模型IV的基础上改进得到的。
模型III和模型VII在考虑服务员工作满意程度和在宾馆所需服务员人数最少和加
班人数最 少的情况下，分别对模型II、VI改进后，得到更为合理的工作时间安排表。

优点： < br>1、所建模型简单，通俗易懂，并为求得更为合理的时间工作调度表，并对模型I、
IV都进行了 两次优化，有较强的实用性；
2、利用
LINGO
软件，算法简便,编程实现简单；
3、推广容易，运筹学的题目都可以用整数规划模型解决；增强和减弱约束条件后
能运用到各个 方面的员工工作时间调度问题上，如减弱约束条件，工作日为早上9点到
晚上9点，分为6个时间段，所 建模型就可解决超市工作人员的时间调度问题。


缺点：
1.在实际工作中，服务员在工作时间内，可能会有特殊情况需要请假；
2.可能有突发事件导致所需服务员人数增加；
3.服务员上班时间可能不连续不连续，并不 是严格按照连续工作4小时休息一定时
间后又连续工作进行的。

模型的改进：
针对上述提出的本不足之处，可进一步对模型进行优化，如：
1.建立一个工作时间不连续的整数规划模型，用枚举法可得出在工作时间不连续的
情况下的最 优人数与工作时间安排。
2.针对服务员请假或突发事件导致所需服务员人数增多的问题，可以对该宾 馆一段
时间的调查，得到一系列数据，然后按照近似概率计算的方法，求出具有一定可靠度，
即 宾馆按照规划的调度方法能够应对所需服务员人数增多情况的概率的最优人数与工
作时间安排。

推广：
此类工作时间调度优化问题在实际中经常碰到，增强和减弱约束条 件后能运用到各
个方面的员工工作时间调度问题上，例如医院护士值班调配问题、商场的工作人员值班< br>的问题、生产过程中在制品库存问题等都可建立类似的线形规划模型。运筹学的题目都
可以用这类 整数规划模型解决。故该模型具有一定的实用性与推广型。


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

附表：


程序1：
model:
sets:
sjd1..12:m,x;
endsets
data:
m=15 15 15 35 40 40 40 30 31 35 30 20;
enddata
min=@sum(sjd(i):x(i));
@for(sj d(i):x(i)+x(@wrap(i-1,12))+x(@wrap(i-3,12))+x(@wra p(i-4,12))>=m(i));
@for(sjd(i):@gin(x(i)));
End

程序2
model:
sets:
sjd1..12:m,x;
endsets
data:
m=15 15 15 35 40 40 40 30 31 35 30 20;
enddata
min=@sum(sjd(i):x(i));
@for(sjd(i):x(i)+x( @wrap(i-1,12))+x(@wrap(i-4,12))+x(@wrap(i-5,12))>= m(i));
@for(sjd:@gin(x));
End

程序3：
model:
sets:
sjd1..12:x;
endsets
data:
enddata
min=x(1)+x(2 )++x(3)+x(12)+x(11)+x(10)+x(9)+x(8);
x(1)+x(8)+x(9)+x(12)>15;
x(1)+x(2)+x(9)+x(10)>15;
x(2)+x(3)+x(10)+x(11)>15;
x(3)+x(4)+x(11)+x(12)>35;
x(1)+x(4)+x(5)+x(12)>40;

x(1)+x(2)+x(5)+x(6)>40;
x(2)+x(3)+x(6)+x(7)>40;
x(3)+x(4)+x(7)+x(8)>30;
x(4)+x(5)+x(8)+x(9)>31;
x(5)+x(6)+x(9)+x(10)>35;
x(6)+x(7)+x(10)+x(11)>30;
x(7)+x(8)+x(11)+x(12)>20;
@sum(sjd:x)=88;
@for(sjd:@gin(x));


程序4：
model:
sets:
jb1..12:x,y;
endsets
data:
enddata
min=@sum(jb:y);
y(8) +x(1)+y(1)+x(9)+y(9)+x(10)+y(10)+x(12)+x(12)>15; < br>y(9)+x(1)+y(1)+x(2)+y(2)+x(10)+y(10)+x(11)+y(11 )>15;
y(10)+x(2)+y(2)+x(3)+y(3)+x(11)+y(11)+x( 12)+y(12)>15;
y(11)+x(1)+y(1)+x(3)+y(3)+x(4)+y (4)+x(12)+y(12)>35;
y(12)+x(1)+y(1)+x(2)+y(2)+ x(4)+y(4)+x(5)+y(5)>40;
y(1)+x(2)+y(2)+x(3)+y( 3)+x(5)+y(5)+x(6)+y(6)>40;
y(2)+x(3)+y(3)+x(4) +y(4)+x(6)+y(6)+x(7)+y(7)>40;
y(3)+x(4)+y(4)+x (5)+y(5)+x(7)+y(7)+x(8)+y(8)>30;
y(4)+x(5)+y(5 )+x(6)+y(6)+x(8)+y(8)+x(9)+y(9)>31;
y(5)+x(6)+ y(6)+x(7)+y(7)+x(9)+y(9)+x(10)+y(10)>35;
y(6)+ x(7)+y(7)+x(8)+y(8)+x(10)+y(10)+x(11)+y(11)>30; y(7)+x(8)+y(8)+x(9)+y(9)+x(11)+y(11)+x(12)+y(12) >20;
@sum(jb:(x+y))=80;
@for(jb:@gin(x));
@for(jb:@gin(y));


程序5
model:
sets:
jb1..12:x,y;
endsets
data:
enddata
min=@sum(jb:y);

x(1)+x( 8)+x(9)+x(12)+y(1)+y(7)+y(8)+y(9)+y(12)>15;
x( 1)+x(2)+x(9)+x(10)+y(1)+y(2)+y(8)+y(9)+y(10)>15; < br>x(2)+x(3)+x(10)+x(11)+y(2)+y(3)+y(9)+y(10)+y(11 )>15;
x(3)+x(4)+x(11)+x(12)+y(3)+y(4)+y(10)+y( 11)+y(12)>35;
x(1)+x(4)+x(5)+x(12)+y(1)+y(4)+y (5)+y(12)+y(11)>40;
x(1)+x(2)+x(5)+x(6)+y(1)+y (2)+y(5)+y(6)+y(12)>40;
x(2)+x(3)+x(6)+x(7)+y( 1)+y(2)+y(3)+y(6)+y(7)>40;
x(3)+x(4)+x(7)+x(8) +y(2)+y(3)+y(4)+y(7)+y(8)>30;
x(4)+x(5)+x(8)+x (9)+y(3)+y(4)+y(5)+y(8)+y(9)>31;
x(5)+x(6)+x(9 )+x(10)+y(4)+y(5)+y(6)+y(9)+y(10)>35;
x(6)+x(7 )+x(10)+x(11)+y(5)+y(6)+y(7)+y(10)+y(11)>30;
x (7)+x(8)+x(11)+x(12)+y(6)+y(7)+y(8)+y(11)+y(12)>20 ;
@sum(jb:(x+y))=80;
@for(jb:@gin(x));
@for(jb:@gin(y));

程序六
model:
sets:
jb1..12:x,y;
endsets
data:
enddata
min=x(1)+x(2)+x(3)+x(12)+x(11)+x(1 0)+x(9)+x(8)+y(1)+y(2)+y(3)+y(12)+y(11)+y(10)+y(9) +y
(8)+y(7);
x(1)+x(8)+x(9)+x(12)+y(1)+y(7) +y(8)+y(9)+y(12)>15;
x(1)+x(2)+x(9)+x(10)+y(1) +y(2)+y(8)+y(9)+y(10)>15;
x(2)+x(3)+x(10)+x(11 )+y(2)+y(3)+y(9)+y(10)+y(11)>15;
x(3)+x(4)+x(1 1)+x(12)+y(3)+y(4)+y(10)+y(11)+y(12)>35;
x(1)+ x(4)+x(5)+x(12)+y(1)+y(4)+y(5)+y(12)+y(11)>40;
x(1)+x(2)+x(5)+x(6)+y(1)+y(2)+y(5)+y(6)+y(12)>40;
x(2)+x(3)+x(6)+x(7)+y(1)+y(2)+y(3)+y(6)+y(7)>4 0;
x(3)+x(4)+x(7)+x(8)+y(2)+y(3)+y(4)+y(7)+y(8 )>30;
x(4)+x(5)+x(8)+x(9)+y(3)+y(4)+y(5)+y(8)+ y(9)>31;
x(5)+x(6)+x(9)+x(10)+y(4)+y(5)+y(6)+y (9)+y(10)>35;
x(6)+x(7)+x(10)+x(11)+y(5)+y(6)+ y(7)+y(10)+y(11)>30;
x(7)+x(8)+x(11)+x(12)+y(6 )+y(7)+y(8)+y(11)+y(12)>20;
@sum(jb:(x+y))=80;
@sum(jb:y)=26;
@for(jb:@gin(x));
@for(jb:@gin(y));

武汉大学2012年数模选拔赛赛题完整解答（参考）


题目：_________服务员工作时间调度最优模型_________
【摘 要】

本文主要建立整数规划模型解决服务员工作时间调度 的问题。在满足每个时段需要
工作的最少服务员人数的前提下，考虑到服务员工作4小时后只休息2小时 后又继续工
作四小时，休息时间较短和夜间上班服务员所占比例大，服务员对夜间加班的满意度问
题，进行两次人性化优化，得到最佳工作时间人员安排。

模型I、II、III：针 对问题1，考虑到每个服务员一天工作8小时，且连续工作4
小时后需要休息2小时，我们建立了以满足 需求时需要工作的最少服务员人数为目标函
数的整数规划模型。用
LINGO
软件求解 得到满足需求至少需要的服务员为100名。进
一步考虑到服务员两次工作4小时之间只休息2小时，休 息时间较短，不太合理，于是
将每个服务员工作中间的休息时间调为4小时，进行第一次优化，得到模型 II,用
LINGO
软件求得此时所需服务员至少为88名。
又考虑到第一次优化后 凌晨0：00到早上6：00这段时间，安排上班的人有35人，
占总数的39.8%，比较大，考虑到 人的生物钟，这段时间内需要睡眠，在这个时间段上
班的服务员需要从睡眠状态进入工作状态，会引起此 阶段上班的服务员对工作调度安排
的不满。为了降低不满意程度，需要进行第二次优化。以凌晨0：00 到早上6：00需要
工作的服务员人数最少为目标函数，建立模型III。用
LINGO
软件求得凌晨0：00到早
上6：00需要工作的服务员人数为30人，占总人数的34.6%，且这 三阶段工作的人数恰
好等于这阶段所需的最少人数。故此时得到的调度方案为此假设前提下最优解。

模型IV、VI、VII：针对问题2，在宾馆服务员人数不足的情况下需 要部分服务员
加班。同问题1类似分析，建立以需要加班的服务员人数最少为目标函数的整数规划模型。用
LINGO
软件求得需要加班的最少服务员人数为40人。
同模型II分 析，将每个服务员工作中间的休息时间调为4小时，将模型III进行
第一次优化，得到模型IV,用< br>LINGO
软件求得需要加班的最少服务员人数为26人。此
时凌晨0：00到早上6： 00这段时间，安排上班的人有39人，占总员工的48.75%。
同模型III分析，为了降低夜间 上班的不满意程度，以凌晨0：00到早上6：00需
要工作的服务员人数最少为目标函数，建立模型V II。用
LINGO
软件求得凌晨0：00到
早上6：00需要工作的服务员人数为2 6人，占总员工数的32.5%。并得出此方案下服务
员每个时段的调配方案。

最后讨论了本文所建模型的优点和缺点，针对其缺点提出了改进了方案并简述了该
模型的推广及应用。

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

一 问题重述
在某宾馆中,一个工作日分为12个两小时长的时段，每个时段的服务员要求都不同。
例如，在夜间只要求有很少几个服务员就够了，但在上午为了给客人提供退房和卫生服
务，需要较多服务 员。请你为宾馆制定服务员的工作时间表。下表列出了每个时段的人
员需求量。
问题 1：请计算出为满足需求最少需要多少个服务员，假定已知每个服务员每天工
作8小时，且在工作四小时 后需要休息两个小时。
问题2：此部门目前只有80名服务员，这个数目不足以满足给定的需 求。因此建议
每天安排部分服务员加班。每天加班时间为2小时，且紧随在后一个四小时工作时段之后，中间没有休息。请给出服务员工作时间安排方案，以使需要加班的服务员数目最少。
每个时间段的人员需求量
编号 时段 需要服务员人
数
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

二 模型假设
模型I、III的假设：
1、假设每个服务员都服从工作安排；
2、假设每个服务员都准时上、下班，在上班期间无特殊情况发生,不需要请假；
3、假设每 个服务员每天工作8小时，且连续工作4小时后只能休息2小时，在休息2
小时后连续工作；
模型II、IV的假设
在模型I的假设（1）（2）前提下，补充假设：
3 、假设每个服务员每天工作8小时，且连续工作4小时后休息4小时，在休息4小时
后连续工作；
模型III、VI的假设：
在模型II的前提下，补充假设：
4、凌晨0：00到早上6：00需要工作的服务员人数最少。

三 符号说明
Z
1
：为满足要求至少需要的服务员人数；
Z
2
：在服务员人数不满足要求时，至少需要加班的服务员人数；
m
i
：第
i
个时段宾馆需要服务员人数；
x
i< br>：第
i
个时段开始工作的服务员人数，(第1时段为00
am
—02< br>am
，第2时段
为02
am
—04
am

第12时段为10
pm
—12
am
；)，
(i1,2 12)
；
w
i
：第
i
个时段开始工作的服务员人数中不 需要加班的人数，
(i1,212)
；
y
i
：第
i
个时段开始工作的服务员人数中需要加班的人数，
(i1,212)
。

补充说明：
当
x
i1
、x
i3
、x
i4
分别等于 0、 -1、-2、-3时，
x
i1
、x
i3
、x
i4分别表示第12、11、
10、9个时段开始工作的服务员人数。


四 问题分析

问题1：
要保证在每个时段都有足够的服务员在工作。 考虑到服务员一天只工作8小时，且
连续工作4小时后需要休息2小时。
每个时段正在工作的服务员由四部分组成：
1.本阶段开始上班的服务员；
2.本阶段往前数第一个阶段开始上班的服务员；
3.本阶段往前数第三个阶段开始上班的服 务员，工作两时段后，休息两时段在本时
段开始继续工作；
4.本阶段往前数第四个阶段开始上班的服务员，工作两时段后，休息两时段后在本
时段工作。

用公式表达：
m
i
x
i
x
i1
x
i3
x
i4
（i1,2,3,4,12）

例如：

m
1
x
1
x
12x
10
x
9
m
2
x
2
x1
x
11
x
10
m
3
x
3x
2
x
12
x
11
依此类推。

以满足要求时需要工作的最少服务员人数为目标函数，服务员一天工作八小时，且
连 续工作四小时后需要休息2小时为约束条件，建立整数规划模型，求出满足需求时需
要服务员的最少人数 。此工作时间安排可以满足宾馆需求，但此工作时间调度表，服务
员两次工作4小时之间只休息2小时， 休息时间较短，不太合理，于是将每个服务员工
作中间的休息时间调为4小时，进行第一次优化。
改变约束条件为：
（i1,2,3,4,12）

进一步考 虑到第一次优化后凌晨0：00到早上6：00这段时间，安排上班的人有35
人，占总数的39.8% ，比较大，考虑到人的生物钟，这段时间内需要睡眠，在这个时间
段上班的服务员需要从睡眠状态进入工 作状态，会引起此阶段上班的服务员对工作调度
安排的不满。为了降低不满意程度，需要进行第二次优化 。以凌晨0：00到早上6：00
需要工作的服务员人数最少为目标函数，建立模型III。
在模型II的基础上，添加约束条件：

m
i
x
ix
i1
x
i4
x
i5

minx(1)x(2)x(3)x(12)x(11)x(10)x(9)x(8)
;
利用
LINGO
软件求出更为合理的服务员工作时间调度表。


问题2：
此宾馆目前只有80名服务员，这个数目不足以满足 需求，故需要安排部分人加班。
考虑到服务员每天只加班两小时，且紧跟随在后一个4小时工作时段之后 ，中间没有休
息。用
LINGO
软件建立模型VI求出最少加班人数以及合理的服务员 工作时间调度表。
同问题一类似分析，每一个时段的工作人员由以下5部分组成：
1.本阶段不加班的开始上班的服务员和要加班的开始上班的服务员；
2.本阶段往前数第一个阶段不加班的开始上班的服务员和要加班的开始上班的服
务员；
3.本阶段往前数第三个阶段不加班的开始上班的服务员，和要加班的开始上班的服
务员；
4.本阶段往前数第四个阶段不加班的开始上班的服务员，和要加班的开始上班的服
务员；
5.本阶段往前数第五个阶段要加班的开始上班的服务员。
用公式表达为：
mi
w
i
w
i1
w
i3
w
i4
y
i
y
i1
y
i3
y
i4
y
i5
（i1,2,3,4,12）


同问题一，可以将每个服务员工作中间的休息时间调为4小时，进行第一次优化。

得到模 型IV，求出此约束条件下最少加班人数以及合理的服务员工作时间调度表。。
改变约束条件为： < br>m
i
w
i
w
i1
w
i4
w
i5
y
i
y
i1
y
i4
y
i5
y
i6
（i1,2,3,4,12）


同样，同问题1，在模型IV的条件下，考虑到凌晨0：00到早上6：00这段时间，安排上班的人有39人，占总员工的48.75%，所占比例大。我们对模型IV进行改进得到
模型 VII,建立以凌晨0：00到早上6：00这段时间工作人数最少为目标函数的规划模型，
用
LINGO
软件处理求得更为合理的服务员工作时间调度表。
在模型IV的基础上，添加约束条件即可。约束条件为：
minx(1)x(2)x( 3)x(12)x(11)x(10)x(9)x(8)
y(1)y(2)y(3) y(12)y(11)y(10)y(9)y(8)y(7);

（i1,2,3,4,12）


五 模型的建立与求解
针对问题一，建立初始模型I和优化模型II、III。
针对问题二，建立初始模型IV和优化模型VI、VII。
模型I：
首先，知某宾馆的一个 工作日分为12个时段，每个时段所需服务员的人数不同，
所以，必须保证每个时段都有足够的服务员在 工作；其次，每个服务员一天只工作8小
时，且连续工作4小时后需要休息2小时，所以可以给出约束条 件；接下来，建立以满
足需求至少需要的服务员人数为目标函数的整数规划模型。模型如下：
minZ
1


x

i
i1
1 2

x
1
x
9
x
10
x
1 2
15


x
1
x
2
x
1 0
x
11
15

xxxx15
231112< br>

x
1
x
3
x
4
x
12
35

xx
2
x
4
x
5< br>40

1

x
2
x
3
x< br>5
x
6
40

s.t.

x
3
x
4
x
6
x
7
40


xxxx40
578

4

x
5x
6
x
8
x
9
31

< br>x
6
x
7
x
9
x
10
4 0

xxxx40
781011


x
8
x
9
x
11
x
12
40
< br>*

x
i
Z

用
LINGO
软件求解，得：
为满足需求，最少需要的服务员人数为10 0人，且第1、2、

11、12时段新
安排工作的人数
x
1、
x
2

x
11
、
x
12
和总的工作人数如下表一所示：
表一

时间段
00:00-02:00
02:00-04:00
04:00-06:00
06:00-08:00
08:00-10:00
10:00-12:00
12:00-14:00
14:00-16:00
16:00-18:00
18:00-20:00
20:00-22:00
22:00-00:00

开始工作人数
23
17
12
0
0
11
17
13
7
0
0
0
总人数100

总工作人数
30
40
29
35
40
40
40
41
35
35
30
20


模型II：
工作时间调度表1可以满足宾馆需求，但此工作时间调度表 ，服务员两次工作4小时之
间只休息2小时，休息时间较短，于是将每个服务员工作中间的休息时间调为 4小时，
进行第一次优化。
minZ
1


x

i
i1
12

x
1
x
12
 x
9
x
8
15

xx
1
x
10
x
9
15

2

x
3
x
2
x
11
x
10
15

x
4
x
3
x
12
x
11
35

xxxx40
54112


x
6x
5
x
2
x
1
40
st
< br>
x
7
x
5
x
3
x
2
40

xxxx30
8643


x
9
x
7
x
5
x
4
31

xxxx35
865

10

x
11
x
9
x
7
x
6
30


x< br>12
x
10
x
8
x
7
20

用
LINGO
软件求解，得：

为满足 需求，最少需要的服务员人数为100人，且第1、2、

11、12时段新
安排工 作的人数
x
1
、
x
2

x
11
、
x
12
和总的工作人数如下表一所示：
表二

时间段
00:00-02:00
02:00-04:00
04:00-06:00
06:00-08:00
08:00-10:00
10:00-12:00
12:00-14:00
14:00-16:00
16:00-18:00
18:00-20:00
20:00-22:00
22:00-00:00

开始工作人数
0
10
5
18
10
20
5
2
1
4
1
12
总人数88
总工作人数
15
15
20
36
40
40
40
30
31
35
30
20

需求人数
15
15
15
35
40
40
40
30
31
35
30
20


从表二可以看出，优化后只需要88名服务员即可满足 每个时段的工作需要。相比
于模型一所需的100人，优化率为



10088
100
*100%22%

故问题一优化后所需最少服务员数量为88名。



模型III：
模型二的缺点是凌晨0：00到早上6：00这段时间，安排上班的人有35人，占总
数的39.8%，比较大，考虑到人的生物钟，这段时间内需要睡眠，在这个时间段上班的
服务员需要从 睡眠状态进入工作状态，会引起此阶段上班的服务员对工作调度安排的不
满。为了降低不满意程度，需要 进行第二次优化。
为了更直白分析模型二中的数据，用图表表示：

图一

定义：凌晨0：00到早上6：00这三个时段上班人数的多少反映了宾馆服务员对工
作时间调度表的满意度。这段时间开始上班和下班的人数越多，服务员对工作时间调度
表的满意度越小 ，这段时间开始上班和下班的人数越少，服务员对工作时间调度表的满
意度越大。
通 过该图可以看出：凌晨0：00到早上6：00这段时间，安排上班的人有35人，
占总数的39.8% ，比较大，考虑到人的生物钟，这段时间内需要睡眠，在这个时间段上
班的服务员需要从睡眠状态进入工 作状态，会引起此阶段上班的服务员对工作调度安排
的不满。为了降低不满意程度，需要进行第二次优化 。
服务员在凌晨0：00—6：00开始上班和下班的人是由第1、2、3、8、9、10、11、< br>12个时段开始工作的服务员人组成，因此在满足宾馆各个时段服务员需求的条件下，在
模型II 的基础上宾馆有88名服务员，对服务员的满意度可建立模型III，如下：
minx(1 )x(2)x(3)x(12)x(11)x(10)x(9)x(8)


用
LINGO
软件求解，得到如下调配安排。求得凌晨0：00到早上6：00需要工 作
的服务员人数为30人，占总人数的34.6%，比模型II的工作调度表更为合理，能在一
定程度上降低服务员对工作时间安排的不满意度。得到模型改进后的最佳工作时间安排
表三所示：



x
i
x
i1
x
i 4
x
i5
m
i

12

st


x
i
88

i1

xz*

i

表三
时间段
00:00-02:00
02:00-04:00
04:00-06:00
06:00-08:00
08:00-10:00
10:00-12:00
12:00-14:00
14:00-16:00
16:00-18:00
18:00-20:00
20:00-22:00
22:00-00:00

图二
开始工作人数
3
7
3
20
8
22
8
0
3
2
3
9
总工作人数
15
15
15
35
40
40
40
31
31
35
35
20
需求人数
15
15
15
35
40
40
40
30
31
35
30
20



由以上图表可得，经模型III优化后，
minx(1)x(2)x(3)x(12 )x(11)x(10)x(9)x(8)30

优化率


3530
30
*100%16.7%

模型IV：
已知，宾馆只有80名服务员，这个数目不足以满足需 求。所以要部分人加班；其
次，同模型I，只不过此模型中，每个时段内工作的服务员人数（包括需要加 班的服务
员人数和不需要加班的服务员人数这两部分）不仅仅是前几个时段和相对应的此时段开
始工作的服务员人数之和，还应加上某时段开始工作的服务员人数中需要加班的那一部
分。例如：在第6 时段内工作的服务员人数等于此时段开始工作的服务员人数、第5时
段开始工作的人数、第2个和第3个 时段开始工作的服务员人数以及第1时段开始工作
的服务员人数中需要加班的那部分服务员人数之和；最 后，建立以加班的服务员人数最
少为目标函数的整数规划模型如下：
12
minZ
2


i1
y
i


w
1
w
12
w
10
w
9
y
1
y
12
y
10
y
9
y
8
15


w
2
w
1
 w
11
w
10
y
2
y
1
y
11
y
10
y
9
15

wwww yyyyy15
320


w
4
w
3
w
1
w
12
y
4
y
3
 y
1
y
12
y
11
35

ww wwyyyyy40
421542112

5

w< br>6
w
5
w
3
w
2
y
6y
5
y
3
y
2
y
1
40< br>
s

w
7
w
6
w
4
w
3
y
7
y
6
y
4
y
3
y
2
40

wwwwyyyyy3075487543

8
w
9
w
8
w6
w
5
y
9
y
8
y
6
y
5
y
4
31


w
10
w
9
w
7
w
6
y
10
y9
y
7
y
6
y
5
35
wwwwyyyyy30
111


w
12
w
11
w
9
w
8
y
12
y
11
y
9
y
8
y
7
20
*

y
i
z
12


( w
i1
i
y
i
)80
**

y
i
z,w
i
z

利用
LINGO< br>软件求解，得到最少加班的服务员人数为40人，并求得各个时段开始
工作的人数、开始工作的人 数中不需要加班的人数及各个时段总工作人数如下表四所
示；

表四
时间段 不加班工作人数 要加班人数 开始工作人数 总工作人数
00:00-02:00 0 6 6 23
02:00-04:00 7 0 7 21
04:00-06:00 1 0 1 16
06:00-08:00 20 0 20 35
08:00-10:00 0 7 7 40
10:00-12:00 0 19 19 40
12:00-14:00 0 0 0 40
14:00-16:00 3 0 3 39
16:00-18:00 9 0 9 38
18:00-20:00 0 0 0 35
20:00-22:00 0 8 8 30
22:00-00:00 0 0 0 20
总加班人数
总人数100
40


模型VI
同问题一，假设每个服务员每 天工作8小时，且连续工作4小时后休息4小时，在
休息4小时后连续工作；建立模型VI。
12
minZ
2


i1
y
i


w
1
w
12
w
9
w
8< br>y
1
y
12
y
9
y
8
y
7
15

ww
1
w
10
w
9
y
2
y
1
y
10
y
9
y
8
15

2

w
3
w
2
w
11
w
10
y
3
y
2
y
11
y
10
y
9
15

< br>w
4
w
3
w
12
w
11
y
4
y
3
y
12
y
11
y
10
35

wwwwyyyyy40
54112541 1211


w
6
w
5
w
2
w
1
y
6
y
5
y
2
y
1
y
12
40
st


w
7
w
6
w
3
w
2
y
7
y
6
y
3
y
2
y
1
40

wwwwyyyyy30
874387432


w9
w
8
w
5
w
4
y
9
y
8
y
5
y
4
y
3
31
wwwwyyyyy35
965109654

1 0

w
11
w
10
w
7
w
6
y
11
y
10
y
7
y
6
y
5
30


w
12
w
11w
8
w
7
y
12
y
11
y
8
y
7
y
6
20
12


(x
i1
i
y
i
)80


y
i
z
*

w
i
z
*

利用
LI NGO
软件求解，得到最少加班的服务员人数为26人，并求得各个时段开始
工作的人数、开始 工作的人数中不需要加班的人数及各个时段总工作人数如下表五所
示；
表五
不加班
要加班 开始工 不加班总加班总工 总工作
时间段 工作人
人数 作人数 工作人数 作人数 人数
数
00:00-02:00 2 3 5 12 3 15
02:00-04:00 7 0 7 12 3 15
04:00-06:00 8 0 8 15 0 15
06:00-08:00 16 4 20 31 4 35
08:00-10:00 0 8 8 25 15 40
10:00-12:00 9 11 20 18 22 40
12:00-14:00 2 0 2 26 14 40
14:00-16:00 0 0 0 26 4 30
16:00-18:00 3 0 3 19 12 31
18:00-20:00 0 0 0 12 23 35
20:00-22:00 0 0 0 11 19 30
22:00-00:00 7 0 7 9 11 20
要加班总工作
总人数 人数为
为26 80


图三

由以上结果知，若将服务员两次工作时间之间的休息时间延长为4 小时，优化后只
需要26人加班，比起初始模型中的40人，优化率为：


4026
40
*100%35%

模型VII：
考虑到在模型VI的调配方案下，虽然用
LINGO< br>软件求得需要加班的最少服务员人
数为26人，但此时凌晨0：00到早上6：00这段时间，安 排上班的人有39人，占总员
工的48.75%，占很大比例，会引起这段时间内上班的服务员的不满， 故需要以凌晨0：
00到早上6：00需要工作的服务员人数最少为目标函数，建立模型VII。 minx(1)x(2)x(3)x(12)x(11)x(10)x(9)x(8)
y(1)y(2)y(3)y(12)y(11)y(10)y(9) y(8)y(7);


y
i
y
i1
y
i4
y
i5
y
i
y
i1
y
i4
y
i5
y
i6
m
i
< br>12

st


(y
i
w
i)80

i1

yz
*
,wz
*i

i


利用
LINGO
软件求解，得到优 化后的凌晨0：00到早上6：00需要工作的服务员
人数最少为26名，占总员工数的32.5%。并 得出此方案下服务员每个时段的调配方案如
下表六和图四。


表六
不加班开始不加班
要加班加班总工作总工作人
时间段 工作人工作总工作
人数 人数 数
数 人数 人数
00:00-02:00 3 4 7 7 8 15
02:00-04:00 4 0 7 7 8 15
04:00-06:00 5 0 1 9 6 15
06:00-08:00 22 2 20 31 4 35
08:00-10:00 2 1 7 31 9 40
10:00-12:00 13 13 19 22 18 40
12:00-14:00 1 0 0 23 17 40
14:00-16:00 0 0 3 28 2 30
16:00-18:00 0 4 9 24 7 31
18:00-20:00 0 0 0 15 20 35
20:00-22:00 0 2 8 14 16 30
22:00-00:00 4 0 0 5 15 20

图四

优化率




*100%33.3%



六 模型的评价与推广
本文建立了六个模型，模型I和模型IV运用了整数规划模 型解决了在满足需求时
所需服务员人数最少和加班人数最少的问题。
模型II和模型VI是在 考虑实际工作中每个服务员休息4小时候再工作较为人性化
后在模型I和模型IV的基础上改进得到的。
模型III和模型VII在考虑服务员工作满意程度和在宾馆所需服务员人数最少和加
班人数最 少的情况下，分别对模型II、VI改进后，得到更为合理的工作时间安排表。

优点： < br>1、所建模型简单，通俗易懂，并为求得更为合理的时间工作调度表，并对模型I、
IV都进行了 两次优化，有较强的实用性；
2、利用
LINGO
软件，算法简便,编程实现简单；
3、推广容易，运筹学的题目都可以用整数规划模型解决；增强和减弱约束条件后
能运用到各个 方面的员工工作时间调度问题上，如减弱约束条件，工作日为早上9点到
晚上9点，分为6个时间段，所 建模型就可解决超市工作人员的时间调度问题。


缺点：
1.在实际工作中，服务员在工作时间内，可能会有特殊情况需要请假；
2.可能有突发事件导致所需服务员人数增加；
3.服务员上班时间可能不连续不连续，并不 是严格按照连续工作4小时休息一定时
间后又连续工作进行的。

模型的改进：
针对上述提出的本不足之处，可进一步对模型进行优化，如：
1.建立一个工作时间不连续的整数规划模型，用枚举法可得出在工作时间不连续的
情况下的最 优人数与工作时间安排。
2.针对服务员请假或突发事件导致所需服务员人数增多的问题，可以对该宾 馆一段
时间的调查，得到一系列数据，然后按照近似概率计算的方法，求出具有一定可靠度，
即 宾馆按照规划的调度方法能够应对所需服务员人数增多情况的概率的最优人数与工
作时间安排。

推广：
此类工作时间调度优化问题在实际中经常碰到，增强和减弱约束条 件后能运用到各
个方面的员工工作时间调度问题上，例如医院护士值班调配问题、商场的工作人员值班< br>的问题、生产过程中在制品库存问题等都可建立类似的线形规划模型。运筹学的题目都
可以用这类 整数规划模型解决。故该模型具有一定的实用性与推广型。


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

附表：


程序1：
model:
sets:
sjd1..12:m,x;
endsets
data:
m=15 15 15 35 40 40 40 30 31 35 30 20;
enddata
min=@sum(sjd(i):x(i));
@for(sj d(i):x(i)+x(@wrap(i-1,12))+x(@wrap(i-3,12))+x(@wra p(i-4,12))>=m(i));
@for(sjd(i):@gin(x(i)));
End

程序2
model:
sets:
sjd1..12:m,x;
endsets
data:
m=15 15 15 35 40 40 40 30 31 35 30 20;
enddata
min=@sum(sjd(i):x(i));
@for(sjd(i):x(i)+x( @wrap(i-1,12))+x(@wrap(i-4,12))+x(@wrap(i-5,12))>= m(i));
@for(sjd:@gin(x));
End

程序3：
model:
sets:
sjd1..12:x;
endsets
data:
enddata
min=x(1)+x(2 )++x(3)+x(12)+x(11)+x(10)+x(9)+x(8);
x(1)+x(8)+x(9)+x(12)>15;
x(1)+x(2)+x(9)+x(10)>15;
x(2)+x(3)+x(10)+x(11)>15;
x(3)+x(4)+x(11)+x(12)>35;
x(1)+x(4)+x(5)+x(12)>40;

x(1)+x(2)+x(5)+x(6)>40;
x(2)+x(3)+x(6)+x(7)>40;
x(3)+x(4)+x(7)+x(8)>30;
x(4)+x(5)+x(8)+x(9)>31;
x(5)+x(6)+x(9)+x(10)>35;
x(6)+x(7)+x(10)+x(11)>30;
x(7)+x(8)+x(11)+x(12)>20;
@sum(sjd:x)=88;
@for(sjd:@gin(x));


程序4：
model:
sets:
jb1..12:x,y;
endsets
data:
enddata
min=@sum(jb:y);
y(8) +x(1)+y(1)+x(9)+y(9)+x(10)+y(10)+x(12)+x(12)>15; < br>y(9)+x(1)+y(1)+x(2)+y(2)+x(10)+y(10)+x(11)+y(11 )>15;
y(10)+x(2)+y(2)+x(3)+y(3)+x(11)+y(11)+x( 12)+y(12)>15;
y(11)+x(1)+y(1)+x(3)+y(3)+x(4)+y (4)+x(12)+y(12)>35;
y(12)+x(1)+y(1)+x(2)+y(2)+ x(4)+y(4)+x(5)+y(5)>40;
y(1)+x(2)+y(2)+x(3)+y( 3)+x(5)+y(5)+x(6)+y(6)>40;
y(2)+x(3)+y(3)+x(4) +y(4)+x(6)+y(6)+x(7)+y(7)>40;
y(3)+x(4)+y(4)+x (5)+y(5)+x(7)+y(7)+x(8)+y(8)>30;
y(4)+x(5)+y(5 )+x(6)+y(6)+x(8)+y(8)+x(9)+y(9)>31;
y(5)+x(6)+ y(6)+x(7)+y(7)+x(9)+y(9)+x(10)+y(10)>35;
y(6)+ x(7)+y(7)+x(8)+y(8)+x(10)+y(10)+x(11)+y(11)>30; y(7)+x(8)+y(8)+x(9)+y(9)+x(11)+y(11)+x(12)+y(12) >20;
@sum(jb:(x+y))=80;
@for(jb:@gin(x));
@for(jb:@gin(y));


程序5
model:
sets:
jb1..12:x,y;
endsets
data:
enddata
min=@sum(jb:y);

x(1)+x( 8)+x(9)+x(12)+y(1)+y(7)+y(8)+y(9)+y(12)>15;
x( 1)+x(2)+x(9)+x(10)+y(1)+y(2)+y(8)+y(9)+y(10)>15; < br>x(2)+x(3)+x(10)+x(11)+y(2)+y(3)+y(9)+y(10)+y(11 )>15;
x(3)+x(4)+x(11)+x(12)+y(3)+y(4)+y(10)+y( 11)+y(12)>35;
x(1)+x(4)+x(5)+x(12)+y(1)+y(4)+y (5)+y(12)+y(11)>40;
x(1)+x(2)+x(5)+x(6)+y(1)+y (2)+y(5)+y(6)+y(12)>40;
x(2)+x(3)+x(6)+x(7)+y( 1)+y(2)+y(3)+y(6)+y(7)>40;
x(3)+x(4)+x(7)+x(8) +y(2)+y(3)+y(4)+y(7)+y(8)>30;
x(4)+x(5)+x(8)+x (9)+y(3)+y(4)+y(5)+y(8)+y(9)>31;
x(5)+x(6)+x(9 )+x(10)+y(4)+y(5)+y(6)+y(9)+y(10)>35;
x(6)+x(7 )+x(10)+x(11)+y(5)+y(6)+y(7)+y(10)+y(11)>30;
x (7)+x(8)+x(11)+x(12)+y(6)+y(7)+y(8)+y(11)+y(12)>20 ;
@sum(jb:(x+y))=80;
@for(jb:@gin(x));
@for(jb:@gin(y));

程序六
model:
sets:
jb1..12:x,y;
endsets
data:
enddata
min=x(1)+x(2)+x(3)+x(12)+x(11)+x(1 0)+x(9)+x(8)+y(1)+y(2)+y(3)+y(12)+y(11)+y(10)+y(9) +y
(8)+y(7);
x(1)+x(8)+x(9)+x(12)+y(1)+y(7) +y(8)+y(9)+y(12)>15;
x(1)+x(2)+x(9)+x(10)+y(1) +y(2)+y(8)+y(9)+y(10)>15;
x(2)+x(3)+x(10)+x(11 )+y(2)+y(3)+y(9)+y(10)+y(11)>15;
x(3)+x(4)+x(1 1)+x(12)+y(3)+y(4)+y(10)+y(11)+y(12)>35;
x(1)+ x(4)+x(5)+x(12)+y(1)+y(4)+y(5)+y(12)+y(11)>40;
x(1)+x(2)+x(5)+x(6)+y(1)+y(2)+y(5)+y(6)+y(12)>40;
x(2)+x(3)+x(6)+x(7)+y(1)+y(2)+y(3)+y(6)+y(7)>4 0;
x(3)+x(4)+x(7)+x(8)+y(2)+y(3)+y(4)+y(7)+y(8 )>30;
x(4)+x(5)+x(8)+x(9)+y(3)+y(4)+y(5)+y(8)+ y(9)>31;
x(5)+x(6)+x(9)+x(10)+y(4)+y(5)+y(6)+y (9)+y(10)>35;
x(6)+x(7)+x(10)+x(11)+y(5)+y(6)+ y(7)+y(10)+y(11)>30;
x(7)+x(8)+x(11)+x(12)+y(6 )+y(7)+y(8)+y(11)+y(12)>20;
@sum(jb:(x+y))=80;
@sum(jb:y)=26;
@for(jb:@gin(x));
@for(jb:@gin(y));