基于蜂群算法的排班方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号(10)申请公布号CN104517021A(43)申请公布日(43)申请公布日2015.04.15(21)申请号201310464590.9(22)申请日2013.09.30(71)申请人中国科学院深圳先进技术研究院地址518055广东省深圳市南山区西丽大学城学苑大道1068号(72)发明人樊小毛李烨何晨光苗芬(74)专利代理机构深圳市科进知识产权代理事务所(普通合伙)44316代理人沈祖锋郝明琴(51)Int.Cl.G06F19/00(2011.01)G06N3/00(2006.01)权利要求书1页说明书8页附图3页(54)发明名称基于蜂群算法的排班方法(57)摘要本发明提供一种基于蜂群算法的排班方法，包括：（1）建立清洁工排班模型，目标为所有清洁区域的每时期的工作时总和与每时期的所有清洁区域的平均工作时之差的平方和最小；其约束如下：同一区域、同一排班周期内，级别高与级别低的清洁工作相遇，则保留级别高的清洁工作，丢弃级别低的清洁工作；同一区域内，不同级别的清洁工作在其清洁周期内，安排一次对应的清洁工作，除非同一时间内，已经安排了更高级别清洁工作；（2）利用蜂群算法求解排班模型获得最优值，使每周平均工时相同的情况下，总工时尽可能的最小；（3）将获得最优值的解作为基准排班。本发明可以全局考虑不同地点不同楼层不同清洁方式的约束，使得在平均每周的工时尽量稳定的前提下实现了总工时最小。CN104517021ACN104517021A权利要求书1/1页1.一种基于蜂群算法的排班方法，其特征在于，包括如下步骤：（1）建立清洁工排班模型，并设定排班周期T、清洁工作a、清洁区域b，所述排班模型的目标为所有清洁区域的每时期的工作时总和与每时期的所有清洁区域的平均工作时之差的平方和最小：设定所述模型的约束关系如下：同一区域、同一排班周期内，级别高与级别低的清洁工作相遇，则保留所述级别高的清洁工作，丢弃所述级别低的清洁工作，即，同一区域内，不同级别的清洁工作在其清洁周期内，安排一次对应的清洁工作，除非在同一时间内，已经安排了更高级别的清洁工作，即其中，aij：第j个清洁区域的第i种级别的清洁工作的单位面积的清洁工作时间；bj：第j个清洁区域的面积；xijk：决策变量，第j个清洁区域的第i种级别的清洁工作在第k个时期内是否安排排班，安排为1，否则为0；sij：第j个清洁区域的第i种级别的清洁工作的开始时期；Fij：第j个清洁区域的第i种级别的清洁工作的周期；lij：为大于等于0的整数；（2）利用蜂群算法求解排班模型获得最优值，使得每周平均工时相同的情况下，总工时尽可能的最小；（3）将获得最优值的解作为基准排班。2.如权利要求1所述的基于蜂群算法的排班方法，其特征在于，所述蜂群算法，包括：（2.1）初始时刻，所有的蜜蜂（n）都是侦察蜂；（2.2）评估食物源的收益度；（2.3）选择在收益度排名在前θ的食物源作为搜索邻域的食物源（m），其中，（2.4）确定搜索邻域（ngh）；（2.5）招募跟随蜂到食物源（m）采蜜；（2.6）每个邻域搜索的食物源只保留一个引领蜂；（2.7）继续在邻域内搜索，转到步骤2.3直到条件不满足；（2.8）剩余（n－m）个的蜜蜂随机搜索新的食物源；（2.9）形成新的侦察蜂群体，转步骤2.2，直至条件不满足；（2.10）记录所述最优值。2CN104517021A说明书1/8页基于蜂群算法的排班方法技术领域[0001]本发明涉及排班方法，尤其涉及一种基于蜂群算法的排班方法。背景技术[0002]近年来，国内外研究较多的排班问题有护士排班问题，航空公司飞机排班问题，轨道交通线路排班问题，排课问题等，然鲜有对清洁排班问题进行研究。[0003]科学合理的安排清洁人员的工作时间不仅能够缓解其压力，能够提高服务质量、降低清洁公司运营成本。但是，在实际清洁排班问题当中存在一系列约束，比如每周可用的清洁人员工作时，某个服务区有多个清洁区域，每个清洁区域有多个服务楼层及多个不同的服务内容等等，因此清洁排班问题是个极为复杂的组合优化问题，属NP难题。[0004]目前，清洁公司主要依靠手工排班，不仅所需花费的时间长，而且一般还缺乏有效的优化机制，难以综合考虑不同地点不同楼层不同清洁方式的约束。发明内容[0005]有鉴于此，本发明主要针对上述清洁公司所面临的排班手段落后问题，提供了一种基于蜂群算法的清洁工排班方法。[0006]本发明的基于蜂群算法的排班方法，包括如下步骤：[0007]（1）建立清洁工排班模型，并设定排班周期T、清洁工作a、清洁区域b，所述排班模型的目标为所有清洁区域的每时期的工作时总和与每时期的所有清洁区域的平均工作时之差的平方和最小：[0008][0009]设定所述模型的