An Activity-based Branch-and-Price Method for the Continuous-Time Resource-Constrained Project Scheduling Problem with Flexible Resource Profiles
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
School of Business |
Master's thesis
Authors
Date
2020
Department
Major/Subject
Mcode
Degree programme
Information and Service Management (ISM)
Language
en
Pages
64+6
Series
Abstract
The resource-constrained project scheduling problem (RCPSP) is an optimization problem that involves the scheduling of a set of activities over time, where each activity consumes a set of renewable resources, and there are dependent relationships among activities. The objective of the RCPSP is to minimize the project makespan, i.e., the total duration of the project. Specifically, this thesis aims at devising a new solution approach for a variant of the RCPSP in which resource allocations can vary throughout the activities' processing time, and the system time is continuous. This variant is termed the resource-constrained project scheduling problem with flexible resource profiles in continuous-time (CT-FRCPSP). Branch-and-Price (BAP) is the solution approach adopted for solving the CT-FRCPSP. BAP is a hybrid method between Branch-and-Bound (BAB) and column generation. BAB is a well-known method for solving mixed-integer programming problems by solving the LP-relaxation of the problem and then branching on the variables with fractional solutions. In BAP, instead of solving the LP-relaxation with the full set of variables at each node of the BAB tree, column generation is used to solve the LP-relaxation by iteratively adding improving columns to the problem until it reaches optimality. The goal of this thesis is to implement the Branch-and Price (BAP) algorithm to solve a simplified version of the CT-FRCPSP and evaluate the effectiveness of the algorithm in solving instances of the CT-FRCPSP. Moreover, in order to reduce the symmetries in the CT-FRCPSP, we propose two symmetry breaking constraints: left-shift and pattern-breaking symmetry breaking constraints. The computational experiment involves evaluating the improvement of the LP-relaxation at the root node and identifying the effectiveness of symmetry breaking constraints in improving the reformulated formulation. In addition, the results from the implemented algorithm are compared with the results from CPLEX's Branch-and-Cut to evaluate how well our BAP implementation can solve instances of the CT-FRCPSP.Description
Thesis advisor
Liesiö, JuusoNaber, Anulark
Keywords
project scheduling, resource-constrained, FRCPSP, branch-and-price, column generation, symmetry breaking, mixed-integer programming, optimization