A Proactive Sampling Approach to Project Scheduling under Uncertainty

Authors

  • Pradeep Varakantham Singapore Management University
  • Na Fu Singapore Management University
  • Hoong Chuin Lau Singapore Management University

DOI:

https://doi.org/10.1609/aaai.v30i1.10404

Keywords:

Resource Constrained Project Scheduling, Sample Average Approximation, Optimization

Abstract

Uncertainty in activity durations is a key characteristic of many real world scheduling problems in manufacturing, logistics and project management. RCPSP/max with durational uncertainty is a general  model that can be used to represent durational uncertainty in a wide variety of scheduling problems where there exist resource constraints. However, computing schedules or execution strategies for RCPSP/max with durational uncertainty is NP-hard and hence we focus on providing approximation methods in this paper. We provide a principled approximation approach based on Sample Average Approximation (SAA) to compute proactive schedules for RCPSP/max  with durational uncertainty. We further contribute an extension to SAA for improving scalability significantly without sacrificing on solution quality. Not only is our approach able to compute schedules at comparable runtimes as existing approaches, it also provides lower α-quantile makespan (also referred to as α-robust makespan) values than the best known approach on benchmark problems from the literature.

Downloads

Published

2016-03-05

How to Cite

Varakantham, P., Fu, N., & Lau, H. C. (2016). A Proactive Sampling Approach to Project Scheduling under Uncertainty. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10404

Issue

Section

Technical Papers: Planning and Scheduling