主管:中国科学院
主办:中国优选法统筹法与经济数学研究会
   中国科学院科技战略咨询研究院

中国管理科学 ›› 2022, Vol. 30 ›› Issue (11): 159-169.doi: 10.16381/j.cnki.issn1003-207x.2020.0272

• 论文 • 上一篇    下一篇

基于整数规划强对偶求解一类局域性资源受限项目调度问题

苏志雄1, 魏汉英1, 张静文2, 乞建勋3   

  1. 1.南昌工程学院工商管理学院,江西 南昌330099;2.西北工业大学管理学院,陕西 西安710072;3.华北电力大学经济与管理学院,北京102206
  • 收稿日期:2020-02-25 修回日期:2020-09-27 出版日期:2022-11-20 发布日期:2022-11-28
  • 通讯作者: 苏志雄(1983-),男(汉族),山西朔州人,南昌工程学院工商管理学院,副教授,博士,研究方向:运筹学、项目调度,Email:happywhy@126.com. E-mail:happywhy@126.com
  • 基金资助:
    国家自然科学基金资助项目(71961020,71971173)

Optimization of a Type of Local Resource-Constrained Project Scheduling Problem Based on the Strong Duality Theory of Integer Programming

SU Zhi-xiong1, WEI Han-ying1, ZHANG Jing-wen2, QI Jian-xun3   

  1. 1. Business Administration College, Nanchang Institute of Technology, Nanchang 330099, China;2. School of Management, Northwestern Polytechnical University, Xi’an 710072, China;3. School of Economics and Management, North China Electric Power University, Beijing 102206,China
  • Received:2020-02-25 Revised:2020-09-27 Online:2022-11-20 Published:2022-11-28
  • Contact: 苏志雄 E-mail:happywhy@126.com

摘要: 资源受限项目调度问题(简称RCPSP)是最具代表性的项目调度问题之一,调度过程可理解为,将受资源约束的平行工序调整为顺序工序。本文针对实际中广泛存在的资源局域、而非全局受限的情况,研究局域性RCPSP,并重点考虑一类问题:项目某环节的一系列平行工序,可用资源量只有一半,各资源可重复利用且具有相应多功能,但最多能承担2个工序,需将这些工序两两排列成对,实现项目工期最短。本文首先探索问题“局域性”特征,量化局域调度对项目工期的影响;基于此,构建只涵盖“局域调度工序”的0-1规划模型;再者,发展整数规划强对偶理论,结合Dangzig-Wolfe分解等方法,提出多项式时间的精确算法;最后通过算例测试,验证算法优势,例如,计算大规模算例的最优解,运用该算法比常规精确方法可快数万倍以上。

关键词: 资源受限项目调度;整数规划强对偶;多项式时间精确算法;Dangzig-Wolfe分解

Abstract: Resource constraints are often broadly impacting, unavoidable impediments in project execution procedures. A number of recent, topical project management issues, such as the resource-constrainedproject scheduling problem (RCPSP), have their roots in the resource constraint problem. It is NP-hard in the strong sense. Current research on the RCPSP mainly focuses on the global problemin which all activities are constrained by resource constraints during the whole project process. Considering practical projects requiring numerous types of resources, the “resource constrained” designation may be for limited types of resources or during local project processes. The local “resource-constrained” designation may constrain activities in a part of the projectsuch that only a portion of activities need arrangement under resource restriction.The above representation denotes the local RCPSP.In this paper, a typical sub-problem of the local RCPSP is studied, which is generated by adding some special assumptions to the general local RCPSP.

Key words: resource-constrained project scheduling; strong duality of integer programming; exact polynomial time algorithm; Dangzig-Wolfe decomposition

中图分类号: