Robust controllability of temporal constraint network with uncertainty

Abstract

Temporal constraint networks with uncertainty are embedded in many scheduling problems. The fundamental problem is to decide whether such network can be executed under different uncertainty scenarios. Few works in the literature raise the question of probabilistic dynamic execution. In this thesis, we propose the Robust Temporal Constraint Network (RTCN) model where durations of uncertain activities are represented by random variables. We wish to know the Robust Controllability problem whether such a network can be executed dynamically with failure probability less than or equals to a given $0\leq\epsilon\leq 1$. If so, how one might find a feasible schedule on the fly as the uncertainty variables are revealed dynamically. We present a computationally tractable and efficient approach to solve the RTCN controllability problem. Experimentally, we will examine how the failure probability $\epsilon$ is affected by several properties of RTCN, and how the failure probability of robust controllability differs from that of a weaker form of controllability. We will also propose some enhancements to improve the result.