Efficient scheduling of evolving, nondeterministic process plans in dynamic environments

The management of dynamic processes, such as design processes, is problematic. These nondeterministic processes evolve over the lifetime of their execution. The frequency and scope of changes inherent in these types of processes hamper a manager\u27s ability to make decisions based on expected downstream behavior. Techniques for managing more stable processes have been applied to this problem with mixed success. A fundamental issue of this problem is determining the role of scheduling in these types of processes. Scheduling, in providing a manager with the resource allocations, start times, and end times of downstream tasks, empowers the manager to make proactive interventions based on expected downstream problems. Without scheduling, a manager is forced to address problems reactively when they occur. On the other hand, dynamics frequently invalidate schedules. The challenge is to develop a method of scheduling that can efficiently generate and maintain an up-to-date schedule for these evolving, nondeterministic processes while accounting for the detection of the dynamics, changes in the process plans, and the trade-offs between the cost of rescheduling and opportunities for better schedules. In this paper, we discuss the difficulties these processes present to their management and scheduling. We describe why a new class of schedulers needs to be developed that specifically accommodates the evolving, nondeterministic nature of these kinds of processes. Finally, we describe PROTEUS, the first instance of this new class of schedulers