摘要
保洁服务公司的清洁任务往往具有不同级别、不同时长和不同周期等特点,缺乏通用清洁排班问题模型,现阶段主要依赖人工排班方案,存在耗时费力且排班质量不稳定等问题。因此提出了属于NP难问题的带约束的清洁排班问题的数学模型,并使用模拟退火算法(SA)、蜂群算法(BCO)、蚁群算法(ACO)和粒子群优化算法(PSO)对该模型进行求解,最后以某清洁服务公司实际排班情况进行了实证分析。实验结果表明,与人工排班方案进行对比,启发式智能优化算法求解带约束的清洁排班问题具有明显优势,获得的清洁排班表的人力需求明显减少。具体来说,在一年排班周期内这些算法比人工排班方案可节省清洁人力218.62~513.30 h。可见基于启发式智能优化算法的数学模型对带约束的清洁排班问题的求解可行且有效,能为保洁服务公司提供科学管理的决策支持。
Cleaning tasks of the cleaning service company often have the characteristics such as different levels,different durations and different cycles,and lack a general cleaning scheduling problem model.At present,the solving of cleaning scheduling problem is mainly relies on manual scheduling scheme,causing the problems such as time-consuming,labor-consuming and unstable scheduling quality.Therefore,a mathematical model of cleaning scheduling problem with constraints,which is a NP-hard problem,was proposed,then Simulated Annealing algorithm(SA),Bee Colony Optimization algorithm(BCO),Ant Colony Optimization algorithm(ACO),and Particle Swarm Optimization algorithm(PSO)were utilized to solve the proposed constrained cleaning scheduling problem.Finally,an empirical analysis was carried out by using the real scheduling state of a cleaning service company.Experimental results show that compared with the manual scheduling scheme,the heuristic intelligent optimization algorithms have obvious advantages in solving the constrained cleaning scheduling problem,and the manpower demand of the obtained cleaning schedule reduced significantly.Specifically,these algorithms can make the cleaning manpower in one year scheduling cycle be saved by 218.62 hours to 513.30 hours compared to manual scheduling scheme.It can be seen that the mathematical models based on heuristic intelligent optimization algorithms are feasible and efficient in solving cleaning scheduling problem with constraints,and provide making-decision supports for the scientific management of the cleaning service company.
作者
樊小毛
熊红林
赵淦森
FAN Xiaomao;XIONG Honglin;ZHAO Gansen(School of Computer Science,South China Normal University,Guangzhou Guangdong 510631,China;Business School,University of Shanghai for Science and Technology,Shanghai 200093,China;Key Laboratory on Cloud Security and Assessment Technology of Guangzhou,South China Normal University,Guangzhou Guangdong 510631,China)
出处
《计算机应用》
CSCD
北大核心
2021年第2期577-582,共6页
journal of Computer Applications
基金
国家重点研发计划项目(2018YFB1404402)
广东省科技计划项目(2019B010137003,2016B030305006,2018A07071702,201804010314)
广州市科技计划项目(201804010314,2012224-12)
唯链基金会资助项目(SCNU-2018-01)。
关键词
清洁排班
模拟退火算法
蜂群优化算法
蚁群优化算法
粒子群优化算法
群集智能
NP难问题
运筹优化
cleaning scheduling
Simulated Annealing(SA)algorithm
Bee Colony Optimization(BCO)algorithm
Ant Colony Optimization(ACO)algorithm
Particle Swarm Optimization(PSO)algorithm
swarm intelligence
NP hard problem
operational optimization
