考虑人力资源排班的资源受限项目调度问题建模与优化  

Modeling and Optimization of Resource Constrained Project Scheduling Problem Considering Employee-Timetabling

作　　者：朱宏伟 陆志强[1] ZHU Hongwei;LU Zhiqiang(School of Mechanical and Energy Engineering,Tongji University,Shanghai 201804,China)

机构地区：[1]同济大学机械与能源工程学院,上海201804

出　　处：《上海交通大学学报》2020年第6期624-635,共12页Journal of Shanghai Jiaotong University

基　　金：国家自然科学基金资助项目(61473211,71171130)。

摘　　要：针对实际生产系统中人力资源以排班的形式进行生产活动的情况,提出考虑人力资源排班的资源受限项目调度问题,以最小化项目工期为目标建立了问题的数学模型.由于串行调度在传统任务列表编码对应的解空间下难以获得较优解,本文借鉴车间调度中析取弧的概念,提出了一种改进任务列表编码方式,通过在任务之间添加析取弧的方式扩大算法的搜索范围.此外,为提升遗传算法的局部搜索能力,在改进任务列表编码基础上设计分支定界搜索框架,对遗传算法得到的染色体进行分段深度搜索,并设计支配规则降低算法计算时间.结果表明:内嵌分支定界搜索框架的遗传算法能够提高求解质量,而设计的支配规则能有效降低算法的运算时间.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 agood 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.

关 键 词：资源受限项目调度 人力资源排班 改进编码方式 分支定界搜索框架 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置]