一类局域性多技能资源受限项目调度的新算法  

New algorithms for a partial multi-skill resource-constrained project scheduling problem

作　　者：苏志雄[1] 顾辉明 乞建勋[2] 魏汉英[1] SU Zhixiong;GU Huiming;QI Jianxun;WEI Hanying(Business Administration College,Nanchang Institute of Technology,Nanchang 330099,China;School of Economics and Management,North China Electric Power University,Beijing 102206,China)

机构地区：[1]南昌工程学院工商管理学院,南昌330099 [2]华北电力大学经济与管理学院,北京102206

出　　处：《系统工程理论与实践》2022年第5期1345-1365,共21页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71961020,71971173)。

摘　　要：多技能资源受限项目调度问题(简称MS-RCPSP)是项目管理中颇具代表性的调度问题,一般性问题以“资源全局受限”为特征.本文从新视角,针对实际中广泛存在的资源局域受限情况,以及反应性和应急性等情况,研究局域性MS-RCPSP;并重点考虑一类典型问题:项目某部分的平行活动,可用的资源量极少,甚至为1,但具备各活动所需技能,且可重复使用,需安排该资源顺序完成这一众活动,使项目工期最小化.虽是局域性调度,但项目系统性使其“牵一发而动全身”,难度可能不亚于全局性调度.本文从探索问题“局域性”特征入手,量化局域调度导致的项目工期延迟,并发展整数线性优化强对偶理论,结合Dantzig-Wolfe分解法,开发出伪多项式时间精确算法求解该问题;通过仿真模拟测试,验证该算法计算大规模问题案例精确解的优势.The multi-skill resource-constrained project scheduling problem(MS-RCPSP) is a representative project scheduling problem,and the general issues focus on global "resource-constrained".In this paper,we consider from a new perspective that partial "resource-constrained" for projects also widely exist in practice,which also concerning reactive emergency cases,and then study the partial MS-RCPSP,and the main emphasis is a type of issue that:There is a list of parallel activities in a department of a project,but the amount of renewable resources for them is minute and even only one,mastering all skills for these activities,then the task is to arrange the resource to sequentially execute these activities and minimize the project makespan.Although the scheduling is "partial",the systematic project causes the partial scheduling to be "far-reaching",and the problem may yield to no problems of global scheduling.First,we explore the characteristics of the "partial scheduling" to compute the project makespan determined by the partial scheduling.And then,we develop the strong duality theory of integer programming,and combine the Dantzig-Wolfe decomposition to present an exact pseudo-polynomial time algorithm for the project scheduling problem.And finally,we evaluate our algorithm by comparing with current approaches,and our algorithm is much more competitive especially to compute tie optimal solutions of large-size instances.

关 键 词：多技能资源受限项目调度 0-1混合线性优化 整数优化强对偶 伪多项式时间精确算法 Dantzig-Wolfe分解 内点法 

分 类 号：O221[理学—运筹学与控制论]