Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (2): 577-582.DOI: 10.11772/j.issn.1001-9081.2020050735

Special Issue: 前沿与综合应用

• Frontier and comprehensive applications • Previous Articles     Next Articles

Cleaning scheduling model with constraints and its solution

FAN Xiaomao1, XIONG Honglin2, ZHAO Gansen1,3   

  1. 1. School of Computer Science, South China Normal University, Guangzhou Guangdong 510631, China;
    2. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China;
    3. Key Laboratory on Cloud Security and Assessment Technology of Guangzhou, South China Normal University, Guangzhou Guangdong 510631, China
  • Received:2020-05-30 Revised:2020-08-05 Online:2021-02-10 Published:2020-09-15
  • Supported by:
    This work is partially supported by the National Key Research and Development Program of China (2018YFB1404402), the Guangdong Science and Technology Program (2019B010137003,2016B030305006,2018A07071702,201804010314), the Guangzhou Science and Technology Program (201804010314, 2012224-12), the VeChain Foundation (SCNU-2018-01).

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

樊小毛1, 熊红林2, 赵淦森1,3   

  1. 1. 华南师范大学 计算机学院, 广州 510631;
    2. 上海理工大学 管理学院, 上海 200093;
    3. 华南师范大学 广州市云计算安全与测评技术重点实验室, 广州 510631
  • 通讯作者: 赵淦森
  • 作者简介:樊小毛(1981-),男,江西进贤人,研究员,博士,主要研究方向:智能优化、机器学习、健康信息学;熊红林(1984-),男,湖南常宁人,博士研究生,主要研究方向:决策支持、智能算法;赵淦森(1977-),男,广东东莞人,教授,博士生导师,博士,主要研究方向:云计算基础设施平台、区块链、云计算安全。
  • 基金资助:
    国家重点研发计划项目(2018YFB1404402);广东省科技计划项目(2019B010137003, 2016B030305006,2018A07071702,201804010314);广州市科技计划项目(201804010314, 2012224-12);唯链基金会资助项目(SCNU-2018-01)。

Abstract: 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.

Key words: 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

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

关键词: 清洁排班, 模拟退火算法, 蜂群优化算法, 蚁群优化算法, 粒子群优化算法, 群集智能, NP难问题, 运筹优化

CLC Number: