EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1932. Solving an integrated project and personnel scheduling problem using Dantzig–Wolfe decomposition

Invited abstract in session MC-60: Project scheduling under uncertainty, stream Project Management and Scheduling.

Monday, 12:30-14:00
Room: S09 (building: 101)

Authors (first author is the speaker)

1. Brede Sørøy
Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology
2. Henrik Andersson
Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology
3. Anders N. Gullhav
Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology

Abstract

We are considering a scheduling problem which consists of both scheduling activities in one or more projects, and the allocation of personnel and transportable equipment demanded to complete the activities. The activities are multi-modal and discretely preemptive, and there are precedence constraints that need to be respected.

Due to the challenges of scalability and efficiency when scheduling using direct mixed-integer programming (MIP) formulation and a MIP solver, we investigate the benefits of decomposing the integrated problem using a Dantzig–Wolfe reformulation. This method decomposes the problem into a master problem and one or several subproblems to find improving solutions.

The subproblem involves scheduling the activities of individual projects, and its solution is fed to the master problem as a new column. The master problem uses the project-schedule columns generated by the subproblems to find the best project schedules to use so that personnel and equipment are allocated the most cost-efficiently. By decomposing the problem into project-specific subproblems that are quick to solve, the efficiency of the overall solution method is significantly increased. Our approach demonstrates promising performance in terms of computational time and solution quality when compared to solving the MIP formulation directly using a MIP solver.

Keywords

Status: accepted

Back to the list of papers