针对实际生产系统中人力资源以排班的形式进行生产活动的情况，提出考虑人力资源排班的资源受限项目调度问题，以最小化项目工期为目标建立了问题的数学模型.由于串行调度在传统任务列表编码对应的解空间下难以获得较优解，本文借鉴车间调度中析取弧的概念，提出了一种改进任务列表编码方式，通过在任务之间添加析取弧的方式扩大算法的搜索范围.此外，为提升遗传算法的局部搜索能力，在改进任务列表编码基础上设计分支定界搜索框架，对遗传算法得到的染色体进行分段深度搜索，并设计支配规则降低算法计算时间.结果表明：内嵌分支定界搜索框架的遗传算法能够提高求解质量，而设计的支配规则能有效降低算法的运算时间.
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.
［1］BLAZEWICZ J, LENSTRA J, KAN A. Scheduling subject to resource constraints: Classification and complexity［J］. Discrete Applied Mathematics, 1983, 5(1): 11-24.
［2］BRUCKER P, KNUST S, SCHOO A, et al. A branch and bound algorithm for the resource-constrained project scheduling problem［J］. Mathematical Methods of Operations Research, 2000, 52(3): 413-439.
［3］REYCK B, HERROELEN W. A branch-and-bound procedure for the resource-constrained project sche-duling problem with generalized precedence relations［J］. European Journal of Operational Research, 1998, 111(1): 152-174.
［4］ZAMANI R. A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem［J］. European Journal of Operational Research, 2013, 229(2): 552-559.
［5］CHEN R. Particle swarm optimization with justification and designed mechanisms for resource-constrained project scheduling problem［J］. Expert Systems with Applications, 2011, 38(6): 7102-7111.
［6］何杰光, 陈新度, 陈新, 等. 求解资源受限项目调度的双种群准粒子群算法［J］. 计算机集成制造系统, 2015, 21(9): 2446-2457.
HE Jieguang, CHEN Xindu, CHEN Xin, et al. Double-population quasi particle swarm optimization for solving resource-constrained scheduling problem［J］. Computer Integrated Manufacturing Systems, 2015, 21(9): 2446-2457.
［7］WANG L, FANG C. A hybrid estimation of distribution algorithm for solving the resource-constrained project scheduling problem［J］. Expert Systems with Applications, 2012, 39(3): 2451-2460.
［8］HE J, CHEN X D, CHEN X. A filter-and-fan approach with adaptive neighborhood switching for resource-constrained project scheduling［J］. Compu-ters and Operations Research, 2016, 71(1): 71-81.
［9］BERGH J, BELIN J, BRUECKER P, et al. Personnel scheduling: A literature review［J］. European Journal of Operational Research, 2013, 226(3): 367-385.
［10］HANAFI R, KOZAN E. A hybrid constructive heuristic and simulated annealing for railway crew sche-duling［J］. Computers and Industrial Engineering, 2014, 70(1): 11-19.
［11］AL-YAKOOB S, SHERALI H. Mixed-integer programming models for an employee scheduling problem with multiple shifts and work locations［J］. Annals of Operations Research, 2007, 155(1): 119-142.
［12］BILGIN B, CAUSMAECKER P, ROSSIE B, et al. Local search neighbourhoods for dealing with a novel nurse rostering model［J］. Annals of Operations Research, 2012, 194(1): 33-57.
［13］MATTAA R, PETERS E. Developing work sche-dules for an inter-city transit system with multiple driver types and fleet types［J］. European Journal of Operational Research, 2009, 192(3): 852-865.
［14］DREZET L, BILLAUT J. A project scheduling problem with labour constraints and time-dependent activities requirements［J］. International Journal of Production Economics, 2008, 112(1): 217-225.
［15］ARTIGUES C, GENDREAU M, ROUSSEAU L, et al. Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound［J］. Computers and Operations Research, 2009, 36(8): 2330-2340.
［16］GUYON O, LEMAIRE P, PINSON E, et al. Cut generation for an integrated employee timetabling and production scheduling problem［J］. European Journal of Operational Research, 2010, 201(2): 557-567.
［17］AHMADI-JAVID A, HOOSHANGI-TABRIZI P. Integrating employee timetabling with scheduling of machines and transporters in a job shop environment: A mathematical formulation and an anarchic society optimization algorithm［J］. Computers and Operations Research, 2017, 84(1): 73-91.
［18］潘全科, 高亮, 李新宇. 流水车间调度及其优化算法［M］. 武汉: 华中科技大学出版社, 2013.
PAN Quanke, GAO Liang, LI Xinyu. Flow shop scheduling and optimization algorithm［M］. Wuhan: Huazhong University of Science and Technology Press, 2013.
