An Activity-based Branch-and-Price Method for the Continuous-Time Resource-Constrained Project Scheduling Problem with Flexible Resource Profiles

 |  Login

Show simple item record

dc.contributor Aalto University en
dc.contributor Aalto-yliopisto fi
dc.contributor.advisor Liesiö, Juuso
dc.contributor.advisor Naber, Anulark
dc.contributor.author Ngô, Lan
dc.date.accessioned 2020-06-14T16:00:45Z
dc.date.available 2020-06-14T16:00:45Z
dc.date.issued 2020
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/44848
dc.description.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. en
dc.format.extent 64+6
dc.language.iso en en
dc.title An Activity-based Branch-and-Price Method for the Continuous-Time Resource-Constrained Project Scheduling Problem with Flexible Resource Profiles en
dc.type G2 Pro gradu, diplomityö fi
dc.contributor.school Kauppakorkeakoulu fi
dc.contributor.school School of Business en
dc.contributor.department Tieto- ja palvelujohtamisen laitos fi
dc.subject.keyword project scheduling en
dc.subject.keyword resource-constrained en
dc.subject.keyword FRCPSP en
dc.subject.keyword branch-and-price en
dc.subject.keyword column generation en
dc.subject.keyword symmetry breaking en
dc.subject.keyword mixed-integer programming en
dc.subject.keyword optimization en
dc.identifier.urn URN:NBN:fi:aalto-202006143797
dc.type.ontasot Master's thesis en
dc.type.ontasot Maisterin opinnäyte fi
dc.programme Information and Service Management (ISM) en
dc.location P1 I fi
local.aalto.electroniconly yes
local.aalto.openaccess no


Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse