|
New Modelling for a Local Resource-Constrained Project Scheduling Problem with “Parallel Structure”
WEI Hanying, YUAN Mengdi, SU Zhixiong
2025, 34 (2):
428-445.
doi: 10.3969/j.issn.2097-4558.2025.02.011
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.
Related Articles
|