带约束的清洁排班问题模型及其求解

保洁服务公司的清洁任务往往具有不同级别、不同时长和不同周期等特点，缺乏通用清洁排班问题模型，现阶段主要依赖人工排班方案，存在耗时费力且排班质量不稳定等问题。因此提出了属于NP难问题的带约束的清洁排班问题的数学模型，并使用模拟退火算法（SA）、蜂群算法（BCO）、蚁群算法（ACO）和粒子群优化算法（PSO）对该模型进行求解，最后以某清洁服务公司实际排班情况进行了实证分析。实验结果表明，与人工排班方案进行对比，启发式智能优化算法求解带约束的清洁排班问题具有明显优势，获得的清洁排班表的人力需求明显减少。具体来说，在一年排班周期内这些算法比人工排班方案可节省清洁人力218.62~513.30 h。可见基于启发式智能优化算法的数学模型对带约束的清洁排班问题的求解可行且有效，能为保洁服务公司提供科学管理的决策支持。

Cleaning scheduling model with constraints and its solution

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.