Publication Type

Journal Article

Version

publishedVersion

Publication Date

12-2015

Abstract

The resource-constrained project scheduling problem with minimum and maximum time lags (RCPSP/max) is a general model for resource scheduling in many real-world problems (such as manufacturing and construction engineering). We consider RCPSP/max problems where the durations of activities are stochastic and resources can have unforeseen breakdowns. Given a level of allowable risk, (Formula presented.), our mechanisms aim to compute the minimum robust makespan execution strategy. Robust makespan for an execution strategy is any makespan value that has a risk less than (Formula presented.). The risk for a makespan value, (Formula presented.) given an execution strategy, is the probability that a schedule instantiated from the execution strategy will not finish before (Formula presented.) given the uncertainty over durations and resources. We make three key contributions: (a) firstly, we provide an analytical evaluation of resource breakdowns and repairs on executions of activities; (b) we then incorporate such information into a local search framework and generate execution strategies that can absorb resource and durational uncertainties; and (c) finally, to improve robustness of resulting strategies, we propose resource breakdown aware chaining procedure with three different metrics. This chaining procedure computes resource allocations by predicting the effect of breakdowns on robustness of generated strategies. Experiments show effectiveness of our proposed methods in providing more robust execution strategies under uncertainty.

Keywords

Project scheduling, Risk management, Robustness and sensitivity analysis, Uncertainty modeling

Discipline

Artificial Intelligence and Robotics | Computer Sciences | Operations Research, Systems Engineering and Industrial Engineering

Publication

Journal of Scheduling

Volume

18

Issue

6

First Page

607

Last Page

622

ISSN

1094-6136

Identifier

10.1007/s10951-015-0425-1

Publisher

Springer Verlag

Additional URL

http://doi.org/10.1007/s10951-015-0425-1

Download

Share

COinS