Using simuation for execution monitoring and on-line rescheduling with uncertain durations

The problem we tackle is on-line rescheduling with temporal uncertainty, activity durations are uncertain and activity end times must be observed during execution. In this paper, we will assume we have a representation of the uncertainty of each activity duration in the form of probability distributions which are used in the simulation of schedule execution. We use the simulations to monitor the execution of the schedule and in particular to estimate the quality of the schedule and the end times of the activities. Given an initial schedule, the schedule starts execution and we must decide when to reschedule. We propose and explore a non-monotonic technique where each time we reschedule we can completely change the existing schedule except for those activities that have already started (or finished) execution. This paper explicitly addresses the basis on which the decision to reschedule is made by investigating three simple measures of the data provided by simulation