Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

2-2016

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 pro- vide 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.

Discipline

Artificial Intelligence and Robotics | Computer Sciences | Operations and Supply Chain Management

Publication

Proceedings of the AAAI Conference on Artificial Intelligence 2016: Phoenix, Arizona, February 12-17, 2016

First Page

3195

Last Page

3201

Publisher

AAAI Press

City or Country

Menlo Park, CA

Copyright Owner and License

LARC

Download

Share

COinS