Abstract: The classical resource-constrained project scheduling problem (RCPSP) focuses on the “global resource- constrained” setting. However, with the development of productivity, project size expansion, and the increasing diversification and complexity of resource capacities, the “local resource-constrained” feature has become more prominent in project resource management. For example, while the capacities of common resources are generally guaranteed, the availability of scarce and expensive resources is often constrained, which restricts certain related activities that require these resources. The recent extensions of RCPSP have begun to reflect these “locality” features of “resource-constrains”, such as reactive RCPSP, RCPSP with varying resource capacities and demands, and multi-RCPSP. Despite this, the exploration of the “locality” feature remains limited, resulting in inefficiencies in computing optimal solutions for these problems. This paper summarizes and classifies these RCPSP with the “locality” feature as local RCPSP in order to jointly analyze their common characteristics and explore effective approaches for these problems. Specifically, it mainly focuses on a scenario where activities under the “local resource-constrained” condition have a “parallel structure”, i.e., the activities run in parallel (many other scheduling problems, such as the waterway ship scheduling problem, are also equivalent to RCPSPs with “parallel structure”). The required renewable resources are unit-capacity resources. The aim is to minimize the project makespan by efficiently allocating these constrained renewable resources to execute these local activities. First, this paper explores the “locality” feature of the problem to determine the project duration based on local scheduling. Then, based on the characteristics, it formulates a new sequence-position-based 0-1 mixed linear programming model for local RCPSP, which achieves global optimization through local scheduling. This model has the potential to incorporate recent advancements in integer programming literature. Finally, it demonstrates the significant competitiveness of the propose models by applying them to solve large-scale problem instances and obtaining optimal solutions.

Key words: resource-constrained project scheduling, local scheduling, 0-1 mixed linear programming, network planning technology, project duration

摘要： 经典资源受限项目调度问题（RCPSP）以“资源全局受限”为特征。随着生产力发展、项目规模增大、资源供需多样化和复杂化，项目面临的资源供应逐渐呈现出“局域受限”特征，如一般性资源有条件供应充足，但稀缺、昂贵资源供应有限，影响对其有需求的部分工序。RCPSP的最新拓展问题也普遍体现出资源受限的“局域性”特征，如反应性RCPSP、资源供应/需求非定额RCPSP、多项目环境下的RCPSP等，由于现有方法对该“局域性”特征探索不足，求解问题最优解的效率明显受限。鉴于此，将具有“局域性”特征的RCPSP归类为局域性RCPSP，进行统一分析，揭示其共同特性，并开发适用于此类问题的有效方法。重点考虑一类问题：项目中受局域性资源限制的工序具备“平行结构”，即工序相互平行（港口船舶调度等问题也等价于具备“平行结构”的RCPSP），且资源为单产能类型资源。如何安排受限资源完成该局部工序，从而使项目全局工期最短。探索问题的“局域性”特征，量化“局域调度”对“项目全局”的影响，并基于此构建“用局部调度实现全局最优化”的基于工序排序位置的新0-1混合线性规划模型，该模型具有更强的优化潜力。算例测试表明，该模型在计算较大型案例的最优解方面具有显著的竞争力。

关键词: 资源受限项目调度, 局域性调度, 0-1混合线性规划, 网络计划技术, 项目工期