A Dynamic Programming Formulation of Scheduling Non-Deterministic Activities with Stochastic Durations

Abstract

Scheduling personal activities is a non-deterministic stochastic constraint optimization problem. Activities may have discontinuous temporal domains and arbitrary stochastic duration distributions; they may be non-deterministic, that is they succeed with some probability; they have utilities, whereas several non-trivial constraints and preferences may hold over them, etc. In this article we propose a framework based on dynamic programming to model the problem and compute optimal policies. We also propose a heuristic-based relaxation of the dynamic programming model, trying to confront the curse of dimensionality. With the relaxed approach we obtain lower bounds of the overall utility in significantly less time. An empirical analysis compares the two approaches in terms of effectiveness and efficiency.