Mixed Integer Linear Programming Formulations For A Resource Constrained Project Scheduling Problem

Abstract

The Resource Constrained Project Scheduling Problem (RCPSP) is an NP-hard job scheduling problem. This thesis finds and compares mixed integer linear programming formulations for an extension to the standard RCPSP with the weighted tardiness objective. We experiment computationally on test instances inspired by real data to find a formulation that gives good and stable solver performance. A new Big-M formulation for disjunctive constraints is introduced. This ''permutation formulation'' has limited purpose and needs further study, but nevertheless outperforms a time-indexed formulation on some large instances. We deduce cutting planes from the set of disjunctive, resource, precedence and tardiness constraints and inspect how adding them to a formulation impacts solver performance. A family of strong cutting planes is deduced from the precedence constraints, and for these we describe a separation algorithm and a separation heuristic. Furthermore, we prove that these inequalities along with general constraints suffice to describe the convex hull of a specific integral set. A Block Decomposition Heuristic is designed to find feasible solutions to RCPSP instances where the precedence relations give rise to chains. Overall, we find that a classic full time-indexed binary formulation is suitable for solving RCPSP instances of various sizes and constraint characteristics. This result also holds when our RCPSP is formulated as a rescheduling problem.