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

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