基于有条件随机分配下的时间表优化问题——以学校课表与某风电场工作排班表的制定为例

汪慧玲,谭子健,张韧(. 咸宁职业技术学院工学院,湖北 咸宁 4700;. 华中师范大学数学与统计学学院,湖北 武汉 40079;. 武汉华夏理工学院,湖北 武汉 40)



基于有条件随机分配下的时间表优化问题
——以学校课表与某风电场工作排班表的制定为例

汪慧玲1,谭子健2,张韧3
(1. 咸宁职业技术学院工学院,湖北 咸宁 437100;2. 华中师范大学数学与统计学学院,湖北 武汉 430079;3. 武汉华夏理工学院,湖北 武汉 430223)

时间表的优化问题广泛应用于各种社会生产活动中，但由于具体任务受制于具体的约束条件而难以周全地制定符合约束的工作时间表.本文中着眼于一般化的有条件约束下的随机分配特征，基于数学建模及相关软件的程序模拟，建立符合约束的目标函数与约束式，进行相关运算，并给出科学可行的执行时间表，以保证工作的有效完成.以学校课表安排与工作排班表的制定为例，论述解答有条件随机分配下的时间表优化问题，给出最终可操作工作流程及其效能评价.结论可应用于工程调度、时间编排、人员分配等方面，广泛涉及到众多相关行业，具有较大的应用价值.关键词：数学建模；时间表；课表制定；工作表安排；Lingo

在现如今的社会生活中，能够快速有效地制订得到可执行的符合约束条件的具体安排规划，是创造出效益最优化的前提.但事实上，由于各项工程事物建立在特定背景的框架下，对于约束条件的把握与针对此背景下的实际规划操作就显得并不容易.笔者基于运筹学理论，针对实际案例的一般性约束情形，试图分别列出其对应的目标函数(有些可能无明确目标函数)与约束条件式，通过计算机优化模拟运算，得出具体安排的数学化表达，最终制定出明确的计划时间表.本文中例举关于学校课程表的安排与企业工作表的制定方案规划，这两个问题具有普遍代表性.我们在此仅考虑针对这两类问题中一般的约束性条件，使得问题具有普适性，对于一般的问题都有一定的启发性和有效的借鉴价值.

1 基于有条件随机分配下的时间表优化问题

对于一般性的时间表规划问题[1]，我们可以将其归结于基于如下背景的表述：

目标函数：一般的无明确目标函数，或可根据进一步优化目标提出多目标函数；

约束条件：一般的具有如下约束限制：

1) 时间阈值：在规定的时间内完成既定任务；

2) 对象明确：在既定的可用对象中分配相应任务与执行时刻；

3) 冲突避免：针对某一时刻或某一时间段的人员冲突避免；

4) 任务阈值：根据实际需求，完成全部既定任务或可选性既定目标；

5) 效益约束：对于可能出现的多种可行方案下，选取综合效益最优的方案；

6) 其他约束条件.

对于有条件下的随机分配模型，可能存在多种并行的可行方案，一般地，这些方案在单一的完成既定任务(不考虑额外效益)的情况下，均是可行的有效规划.我们将在如上的框架下，具体研究相应的时间表优化问题[2].以上则给出了我们考虑此类问题的一般性问题的提出，并可结合实际，得到符合具体问题的问题背景与建模步骤.

2 基于有条件随机分配的课表制定问题

2.1 课表制定的主要难点 课表的制定，是要依据某学校一学期班级所需学习的全部课程，为各位授课教师，在每周均有课程的前提下，安排恰当的授课学习时间，使得如期完成本学期全部授课学习任务.在这其中，主要为了避免关于同一教师/学生同一时间段不同教室的冲突与同一教师/学生不可用时间段的规避.

2.2 课表制定的一般性问题求解

2.2.1 课表制定一般性问题的背景 某大学学院办公室需要为该学院某年级的两个平行班级制定该学期每周的课程表.该两平行班级中，除去数学和体育课之外，两个平行班级的其余各门课程的任课教师均相同.在此大学中，每节课时长为45分钟，课间10分钟.为简便计，我们不妨将一个上课周期记为2个小时(即包含小课间的两个课时).此外，同一个班级中的各个学生均需要参加相同课程的学习.

表1 各教师为各班级每周授课节数

该大学每周的课程安排为周一至周五，每个上课周期的具体时段分布分别为：8:00—10:00，10:05—12:05,14:00—16:00,16:05—18:05.

表1列出了该学院每个老师每周需要为此两个班所上的课程节数详情.此外，根据教务处统一安排，这两个班级的体育课程统一安排至每周四下午的14:00—16:00时段.每周一鉴于全校统一活动安排，8:00—10:00的第一个上课周期将保留空置，不作授课安排.Mr Gao老师由于在另一所学校兼职任教，故每周一上午不能来本院授课，需为此安排另外时段.Mrs Li老师每周三全天也因故不能来授课，需另择它时.最后，为了避免学生的课业疲劳，我们规定单日单科尽可占用一个授课时段.

问题提出：请为该学院两平行班级授课教师制定每周的课程表，以满足该学期全部授课任务.

以上问题即为典型的有条件的随机分配时间表优化问题.

由此，我们可通过Lingo 12.0计算得出符合规划的问题优化解.

2.2.3 课表制定一般性问题的结论 我们由此得出课表制定的一个结果，此结果如下所示：

表2 该学院1班课程表

表3 该学院2班课程表

此课表制定结果有多个平行的可行解.

3 基于有条件随机分配的工作排班表问题

3.1 工作表排班的主要难点 本案例的主要难点类似于上一案例，只是此处更加着重的凸显了排班在满足要求下的随机性与各工作人员分班的均匀性，以保证排班的公平，并适当合理可预留出机动的人员与时间[4].

表4 本节变量表

表5 风电场全年人员值守/维护排班表

3.2 工作表排班的一般性问题求解

3.2.1 工作表排班一般性问题的背景 在某风电场中，已先后进行了一期、二期建设，现有风机124台，总装机容量约20万kW.为安全生产的需要，各风机每年需进行两次停机维护，且两次维护之间风机不得连续工作超过270天.每次维护需要一组维修人员连续工作2天，同时为了应对突发情况，风电场每天需要有一组维护人员值班[5].现该风电场有4组维护人员可从事值班或维修任务，且每组人员的连续工作时长不超过6天.则我们据此背景制定维修人员的排班方案与风机维护计划，使得各组维修人员的工作任务相对均衡，且风电场具有较好经济效益[6].

3.2.2 工作表排班一般性问题的求解我们将待解决的问题归纳为以下约束条件

：1) 我们仅安排值班和维护人员表格，对于条件中的“每台风机每年需在270天内维护至少两次”，我们根据计算得出，一年中约有42周(共52周)时间需安排每周至少6天维修方可完成任务，故除去节假日和某些不可控等因素，我们近似认为基本每周都有人员参与维护与值守任务，故本问题关键在于处理好“人员连续工作不超过6天”的约束条件，并合理均衡的安排班次；

2) 若某天某组人员值守，则此组人员在未来6天不可能连续值班；

3) 若某天及次日某组人员维护，则此组人员在未来6天不可能连续维护；

4) 值守任务与维护任务同一天不可能为同一组人员；

5) 每天至少有一组人员值守，且至少两组人员维护；

6) 某天某组人员是否值守/维护，设为一0-1变量处理.

本节中涉及的变量有：

相应的约束条件为：

3. ∀j∈days,k∈groups：zhibanjk+weihujk≤1-值守与维护不得冲突；

6. ∀j∈days,k∈groups:zhibanjk,weihujk∈{0,1}-0-1变量.则我们最终将给出一个完整具体的4组人员全年值守/维护排班表.

3.2.3 工作表排班一般性问题的结论经过相应运算，我们得出了全年该风电场基于已知条件下的可行的人员排班表，如表5所示(仅以1月为例)，按此表排班，即可完成全年值班与维护任务，且人员安排较为均衡；风电场由此可正常安全进行生产生活，且使得具有尽可能多的经济效益，符合案例诉求.

4 结束语

排班表问题的优化求解，是实际工作生活中重要的应用方面.我们根据不同的要求和现实的背景，制定出切实可行的目标函数与约束条件，并利用计算机相关软件进行线性与非线性优化计算，得出最终的排班结果.要求我们对于普遍的工作人员来安排的工作任务量较为均匀，使之工作地位和分量均等，从而体现出公平合理的排班原则.

[1] 赵东方.数学模型与计算[M].北京:科学出版社,2007.

[2] 黄干平，姚自珍，张轶静.使用模拟退火算法解课表问题[J].武汉大学学报(自然科学版),2000,46(5):559-563.

[3] Christelle Gueret,Christian Prins，Marc Sevaux.运筹学案例[M].北京林森科技发展有限公司(译),2006.

[4] 熊伟清，魏平，赵杰煜.用遗传算法求解时间表问题[J].中国卫生质量管理,2001,1(5):29-32.

[5] 杜实,赵金路.多跑道进场航班调度研究[J].科技和产业,2013,13(4):135-139.

[6] 刘朝晖,俞文鮆.关于工件组的两机自由作业时间表问题[J].华东理工大学学报，2000，26(6):665-669.

(责任编辑 赵燕)

Timetable optimization based on conditional random allocation: a case study of school schedule and work schedule of a wind farm

WANG Huiling1,TAN Zijian2,ZHANG Ren3

(1. College of Engineering, Xianning Vocational and Technical College, Xianning 437100, China；2. School of Mathematics & Statistics, Central China Normal University, Wuhan 430079, China；3. Wuhan Huaxia Institute of Technology, Wuhan 430223,China)

The schedule optimization problem is widely used in various social production activities, however, due to specific tasks are subject to specific constraints, it is difficult to develop a comprehensive schedule of work in line with constraints. In this paper, we focused on the generalized stochastic distributions under conditional constraints. Based on the mathematical modeling and the simulation of the related software, we established the objective function and constraint type according to the constraint, and carried out the correlation operation, and give a scientific and feasible execution schedule. To ensure the effective completion of the work. We take the school schedule and work schedule as an example to illustrate the schedule under the conditions of random distribution optimization problem, give the final operable work process and its effectiveness evaluation.the results can be applied to engineering scheduling, time scheduling, personnel distribution and so on. It has wide application value in many related industries.Key words: mathematical modeling; timetable; class schedule; work schedule; Lingo

2017-02-26

湖北省自然科学基金(2016CFC747)资助

汪慧玲(1981-)，女，讲师；张韧，通信作者，讲师，E-mail:43862746@qq.com

1000-2375(2017)03-0253-05

O221.2

A

10.3969/j.issn.1000-2375.2017.03.008