东北大学学报:自然科学版 ›› 2014, Vol. 35 ›› Issue (2): 184-189.DOI: 10.12068/j.issn.1005-3026.2014.02.008

• 信息与控制 • 上一篇    下一篇

求解多技能人力资源约束的项目调度问题的两阶段算法

王一帆,刘士新,陈迪   

  1. (东北大学 信息科学与工程学院, 辽宁 沈阳110819)
  • 收稿日期:2013-06-04 修回日期:2013-06-04 出版日期:2014-02-15 发布日期:2013-11-22
  • 通讯作者: 王一帆
  • 作者简介:王一帆(1987-),男,河南商丘人,东北大学博士研究生;刘士新(1968-),男,辽宁调兵山人,东北大学教授,博士生导师.
  • 基金资助:
    国家自然科学基金资助项目(71171038,71021061).

A TwoStage Algorithm for Project Scheduling Problems with Multiskilled Workforce Constraints

WANG Yifan, LIU Shixin, CHEN Di   

  1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China.
  • Received:2013-06-04 Revised:2013-06-04 Online:2014-02-15 Published:2013-11-22
  • Contact: WANG Yifan
  • About author:-
  • Supported by:
    -

摘要: 针对一类多技能人力资源约束的项目调度问题(PSPMSWC),提出了一种两阶段优化算法,并按算法步骤对模型进行了分解.算法针对分解后的子模型,应用遗传局域搜索及CPLEX优化软件对模型进行求解,并设计了整体迭代求解策略,从而确保所有问题案例都能够进行求解.通过引用基于标准问题库中的典型问题,生成了大量随机算例,并对算法进行了求解实验.实验结果显示,所有案例均能够迅速求解,部分案例可达到最优,从而证明该方法是一种求解PSPMSWC的有效方法,具有较强的实际意义.

关键词: 项目调度, 多技能人力资源, 两阶段求解方法, 遗传局域搜索, 指派问题

Abstract: A twostage optimization algorithm was represented to solve one type of project scheduling problems with multiskilled workforce constraints(PSPMSWC). The model of PSPMSWC was proposed and decomposed into submodels corresponding to the algorithm. By using hybrid genetic local search(GLS) and CPLEX optimization software, a strategy to iteratively solve the submodels in sequence was proposed to ensure that all the instances could be solved successfully. Instances were randomly generated from a standard problem library and utilized to test the performance of algorithm experimentally. Computational results show that all of instances can be solved efficiently, with some of instances having the optimal values. Therefore, the twostage algorithm is proved to be a good method to solve PSPMSWC with practical significance.

Key words: project scheduling, multiskilled workforce, twostage method, genetic local search, assignment problem

中图分类号: