Optimal Schedules for Parallelizing Anytime Algorithms: The Case of
  Shared Resources
  The performance of anytime algorithms can be improved by simultaneously
solving several instances of algorithm-problem pairs. These pairs may include
different instances of a problem (such as starting from a different initial
state), different algorithms (if several alternatives exist), or several runs
of the same algorithm (for non-deterministic algorithms). In this paper we
present a methodology for designing an optimal scheduling policy based on the
statistical characteristics of the algorithms involved. We formally analyze the
case where the processes share resources (a single-processor model), and
provide an algorithm for optimal scheduling. We analyze, theoretically and
empirically, the behavior of our scheduling algorithm for various distribution
types. Finally, we present empirical results of applying our scheduling
algorithm to the Latin Square problem.
