Using simulation 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 execu-tion. In this paper we will assume we have a represen-tation 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 simula-tions 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 com-pletely change the existing schedule except for those activities that have already started (or finished) execu-tion. 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