Citation
Exact and heuristic methods for trading-off makespan and stability in stochastic project scheduling. In proceedings of the 7th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2015), 25 - 28 Aug 2015, Prague, Czech Republic, pages 25-41, 2015.
Paper
Abstract
This paper addresses a problem of practical value in project scheduling: trading expected makespan for stability, under stochastic activity duration uncertainty. We present the formal statement of a problem that we name Proactive Stochastic RCPSP (PS-RCPSP). Assuming activity durations follow known probability distributions, PSRCPSP asks to ?nd a so-called earliest-start (es) policy and a proactive schedule that together minimize the weighted sum of expected project makespan and expected instability (deviation of the realized from the proactive schedule). Extending an existing MILP model for the well-known deterministic Resource-Constrained Project Scheduling Problem (RCPSP), we present a MILP model for PS-RCPSP, which allows us to ?nd optimal (es-policy, proactive schedule) pairs. To deal with instances of practical size, we propose a Linear Programming (LP)-based and a Mixed-Integer LP (MILP)-based heuristic. Our LP-based heuristic optimizes the proactive schedule while keeping the es-policy part of the solution ?xed. Our MILP-based heuristic aims to optimize the structure of the policy together with the proactive schedule. In contrast to existing state-of-art approaches such as CCP [21] and STC [31], our heuristics rely on optimizing the proactive schedule together with the scheduling policy. Experiments show that the LP-based heuristic is e?cient and compares favorably with the state-of-art (i.e. achieves smaller expected makespan for a certain level of expected instability) when the aim is to achieve near-zero instability at the cost of higher makespan. The MILP-based heuristic seems more e?ective (albeit not as e?cient) when the aim is to achieve low expected makespan at the cost of moderate or high instability
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2015-025-041-P, author = { S. Mountakis and T. Klos and C. Witteveen and B. Huisman},
title = {Exact and heuristic methods for trading-off makespan and stability in stochastic project scheduling},
booktitle = {In proceedings of the 7th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2015), 25 - 28 Aug 2015, Prague, Czech Republic},
year = {2015},
editor = {Z. Hanzalek and G. Kendall and B. McCollum and P. Sucha},
pages = {25--41},
note = {Paper},
abstract = {This paper addresses a problem of practical value in project scheduling: trading expected makespan for stability, under stochastic activity duration uncertainty. We present the formal statement of a problem that we name Proactive Stochastic RCPSP (PS-RCPSP). Assuming activity durations follow known probability distributions, PSRCPSP asks to ?nd a so-called earliest-start (es) policy and a proactive schedule that together minimize the weighted sum of expected project makespan and expected instability (deviation of the realized from the proactive schedule). Extending an existing MILP model for the well-known deterministic Resource-Constrained Project Scheduling Problem (RCPSP), we present a MILP model for PS-RCPSP, which allows us to ?nd optimal (es-policy, proactive schedule) pairs. To deal with instances of practical size, we propose a Linear Programming (LP)-based and a Mixed-Integer LP (MILP)-based heuristic. Our LP-based heuristic optimizes the proactive schedule while keeping the es-policy part of the solution ?xed. Our MILP-based heuristic aims to optimize the structure of the policy together with the proactive schedule. In contrast to existing state-of-art approaches such as CCP [21] and STC [31], our heuristics rely on optimizing the proactive schedule together with the scheduling policy. Experiments show that the LP-based heuristic is e?cient and compares favorably with the state-of-art (i.e. achieves smaller expected makespan for a certain level of expected instability) when the aim is to achieve near-zero instability at the cost of higher makespan. The MILP-based heuristic seems more e?ective (albeit not as e?cient) when the aim is to achieve low expected makespan at the cost of moderate or high instability},
owner = {Graham},
timestamp = {2017.01.16},
webpdf = {2015-025-041-P.pdf} }