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.
ZHU Hongwei, LU Zhiqiang
. Modeling and Optimization of Resource Constrained Project
Scheduling Problem Considering Employee-Timetabling[J]. Journal of Shanghai Jiaotong University, 2020
, 54(6)
: 624
-635
.
DOI: 10.16183/j.cnki.jsjtu.2018.134
［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.
