Publication Type
Conference Proceeding Article
Publication Date
6-2016
Abstract
In this work, we consider RCPSP/max with durational uncertainty. We focus on computing robust Partial Order Schedules (or, in short POS) which can be executed with risk controlled feasibility and optimality, i.e., there is stochastic posteriori quality guarantee that the derived POS can be executed with all constraints honored and completion before robust makespan. To address this problem, we propose BACCHUS: a solution method on Benders Accelerated Cut Creation for Handling Uncertainty in Scheduling. In our proposed approach, we first give an MILP formulation for the deterministic RCPSP/max and partition the model into POS generation process and start time schedule determination. Then we develop Benders algorithm and propose cut generation scheme designed for effective convergence to optimality for RCPSP/max. To account for durational uncertainty, we extend the deterministic model by additional consideration of duration scenarios. In the extended MILP, the risks of constraint violation and failure to meet robust makespan are counted during POS exploration. We then approximate the uncertainty problem with computing a risk value related percentile of activity durations from the uncertainty distributions. Finally, we apply Pareto cut generation scheme and propose heuristics for infeasibility cuts to accelerate the algorithm process. Experimental results demonstrate that BACCHUS efficiently and effectively generates robust solutions for scheduling under uncertainty
Discipline
Computer Sciences | Theory and Algorithms
Research Areas
Intelligent Systems and Decision Analytics
Publication
Proceedings of the 26th International Conference on Automated Planning and Scheduling
City or Country
London
Citation
FU, Na; VARAKANTHAM, Pradeep; and Pradeep VARAKANTHAM.
Robust Partial Order Schedules for RCPSP/max with Durational Uncertainty. (2016). Proceedings of the 26th International Conference on Automated Planning and Scheduling. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3310
Copyright Owner and License
LARC
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.