Zero-One Formulation for a Partial Resource-Constrained Project Scheduling Problem with Generalized Precedence Relations

Abstract

The resource-constrained project scheduling problem (RCPSP) aims to arrange activities to meet resource restrictions. In real life, not all resource types are constrained, nor do all activities face resource restrictions. The RCPSP may emerge in parts of the project, which could be named a partial RCPSP. A fundamental principle for RCPSPs is to sequence parallel activities to sequential ones under resource restrictions. This paper considers a typical partial RCPSP with generalized precedence relations (GPRs) and transforms it into a sequence problem that specifically sequences N given parallel activities to H sequential activity pairs with minimal impact on the project duration. The characteristics of activity time parameters are used to quantize the impact of sequencing parallel activities on the project duration. Furthermore, a 0-1 formulation model is presented for the partial RCPSP with GPRs, which includes only the N given parallel activities instead of all activities. The performance of this formulation is evaluated, and detailed computational results are presented for the sequence problem that evaluate the efficiency and competitiveness of this procedure. The obtained results may also serve as theoretical tools for other partial RCPSP with GPRs and may further improve project scheduling.