In this paper, we introduce a novel variant of the Resource-Constrained Project Scheduling Problem (RCPSP), called RCPSP with Transfer Times using Secondary Resources with Instant Self-transfers (RCPSPTT-2I). This variant extends the classical RCPSP by modeling resource transfers between activities and hierarchical resource interactions. Specifically, we consider two types of resources: (i) the primary resources used to execute the activities and (ii) secondary resources that help facilitate transfers of primary resources between activities they execute. Transfer lengths depend on both the pair of activities and the primary resource being transferred. Secondary resources can facilitate part or all of the transfer process, and their own transfers without primary resource are assumed instant. This problem definition captures practical scenarios, such as digital or decision-making secondary resources, that (i) do not require physical movement or (ii) have negligible/constant transfers, combining elements of RCPSP with Transfer Times and RCPSP with First- and Second-Tier Transfers variants from the literature. We formalize RCPSPTT-2I using both Integer Linear Programming and Constraint Programming (CP). These models obtain feasible solutions for most 30-activity instances within a 10-minute runtime but struggle to scale to larger instances. To address this limitation, we introduce a heuristic warm-start and a multi-phase procedure that incrementally refines partial solutions. Computational results show that the multi-phase procedure, combined with the Constraint Programming model, significantly improves scalability and solution quality, while preserving optimality guarantees, making it well-suited for practical instance sizes.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Resource-Constrained Project Scheduling Problem with Transfer Times Using Secondary Resources with Instant Self-transfers

  • Vilém Heinz,
  • Zdeněk Hanzálek,
  • Christian Artigues,
  • Emmanuel Hebrard

摘要

In this paper, we introduce a novel variant of the Resource-Constrained Project Scheduling Problem (RCPSP), called RCPSP with Transfer Times using Secondary Resources with Instant Self-transfers (RCPSPTT-2I). This variant extends the classical RCPSP by modeling resource transfers between activities and hierarchical resource interactions. Specifically, we consider two types of resources: (i) the primary resources used to execute the activities and (ii) secondary resources that help facilitate transfers of primary resources between activities they execute. Transfer lengths depend on both the pair of activities and the primary resource being transferred. Secondary resources can facilitate part or all of the transfer process, and their own transfers without primary resource are assumed instant. This problem definition captures practical scenarios, such as digital or decision-making secondary resources, that (i) do not require physical movement or (ii) have negligible/constant transfers, combining elements of RCPSP with Transfer Times and RCPSP with First- and Second-Tier Transfers variants from the literature. We formalize RCPSPTT-2I using both Integer Linear Programming and Constraint Programming (CP). These models obtain feasible solutions for most 30-activity instances within a 10-minute runtime but struggle to scale to larger instances. To address this limitation, we introduce a heuristic warm-start and a multi-phase procedure that incrementally refines partial solutions. Computational results show that the multi-phase procedure, combined with the Constraint Programming model, significantly improves scalability and solution quality, while preserving optimality guarantees, making it well-suited for practical instance sizes.