同济大学 机械与能源工程学院， 上海 201804
出版日期:2020-06-28发布日期:2020-07-03通讯作者:陆志强，男，教授，博士生导师，电话(Tel.): 021-69589485;E-mail: zhiqianglu@tongji.edu.cn.作者简介:朱宏伟(1993-)，男，浙江省温州市人，博士生，主要研究资源受限项目调度问题.基金资助:国家自然科学基金资助项目(61473211，71171130)Modeling and Optimization of Resource Constrained Project Scheduling Problem Considering Employee-Timetabling
ZHU Hongwei,LU ZhiqiangSchool of Mechanical and Energy Engineering, Tongji University, Shanghai 201804, China
Online:2020-06-28Published:2020-07-03摘要/Abstract
摘要： 针对实际生产系统中人力资源以排班的形式进行生产活动的情况，提出考虑人力资源排班的资源受限项目调度问题，以最小化项目工期为目标建立了问题的数学模型.由于串行调度在传统任务列表编码对应的解空间下难以获得较优解，本文借鉴车间调度中析取弧的概念，提出了一种改进任务列表编码方式，通过在任务之间添加析取弧的方式扩大算法的搜索范围.此外，为提升遗传算法的局部搜索能力，在改进任务列表编码基础上设计分支定界搜索框架，对遗传算法得到的染色体进行分段深度搜索，并设计支配规则降低算法计算时间.结果表明：内嵌分支定界搜索框架的遗传算法能够提高求解质量，而设计的支配规则能有效降低算法的运算时间.
关键词: 资源受限项目调度, 人力资源排班, 改进编码方式, 分支定界搜索框架
Abstract: Aimed at the practical situation where human resources conduct production activities in the form of shifts in production systems, this paper addresses the resource constrained project scheduling problem considering employee-timetabling and establishes a mathematical model with the objective of minimizing project makespan. Since the serial schedule generation scheme has difficulty in generating a good solution under the solution space delivered by traditional activity list, an improved activity list coding method based on the concept of disjunctive arc in job shop scheduling problem is designed to expand the search extent. Moreover, to improve the local search capability of the genetic algorithm, a branch-and-bound-based search framework based on the improved activity list coding method is designed to sectionally and deeply search the chromosome obtained by the genetic algorithm, and dominant rules are designed to reduce the computational time. The results show that the genetic algorithm with the branch-and-bound-based search framework could improve the solution quality, and the dominant rules could reduce the computing time efficiently and effectively.
Key words: resource-constrained project scheduling, employee-timetabling, improved coding method, branch-and-bound-based search framework
PDF全文下载地址:
点我下载PDF
