{'fraction_non_alphanumeric': 0.03902323811523271, 'fraction_numerical': 0.017792707089527758, 'mean_word_length': 4.1310846293678045, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 39, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
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.


Introduction
Assume that our task is to learn a concept with a predefined success rate, measured on a given test set. Assume that we can use two alternative learning algorithms, one which learns fast but requires some preprocessing, and another which works more slowly but requires no preprocessing. Can we possibly benefit from using both learning algorithms in parallel to solve one learning task on a single-processor machine?
Another area of application is that of constraint satisfaction problems. Assume that a student tries to decide between two elective courses by trying to schedule each of them with the set of her compulsory courses. Should the student try to solve the two sets of constraints sequentially or should the two computations be somehow interleaved?
Assume now that a crawler searches for a specific page in a site. If we had more than one starting point, the process could be speeded up by simultaneous application of the crawler from a few (or all) of them. However, what would be the optimal strategy if the bandwidth were restricted? What do the above examples have in common?
• There are potential benefits to be gained from the uncertainty in the amount of resources that will be required to solve more than one instance of the algorithmproblem pair. We can use different algorithms (in the first example) and different problems (in the last two examples). For non-deterministic algorithms, we can also use different runs of the same algorithm.
• Each process is executed with the purpose of satisfying a given goal predicate. The task is considered accomplished when one of the runs succeeds.
• If the goal predicate is satisfied at time t * , then it is also satisfied at any time t > t * . This property is equivalent to utility monotonicity of anytime algorithms (Dean & Boddy, 1988;Horvitz, 1987), where solution quality is restricted to Boolean values.
Our objective is to provide a schedule that minimizes the expected cost, possibly under some constraints (for example, processes may share resources). Such problem definition is typical for rational-bounded reasoning (Simon, 1982;Russell & Wefald, 1991). This problem resembles those faced by contract algorithms (Russell & Zilberstein, 1991;Zilberstein, 1993). There, given the allocated resources, the task is to construct an algorithm providing a solution of the highest quality. In our case, given quality requirements, the task is to construct an algorithm that solves the problem using minimal resources.
There are several research works that deal with similar problems. Simple parallelization, with no information exchange between the processes, may speed up the process due to high diversity in solution times. For example, Knight (1993) showed that using many reactive agents employing RTA* search (Korf, 1990) is more beneficial than using a single deliberative agent. Another example is the work of Yokoo and Kitamura (1996), who used several search agents in parallel, with agent rearrangement after preallotted periods of time. Janakiram, Agrawal, and Mehrotra (1988) showed that for many common distributions of solution time, simple parallelization leads to at most linear speedup. One exception is the family of heavy-tailed distributions (Gomes, Selman, & Kautz, 1998) for which it is possible to obtain superlinear speedup by simple parallelization.
A superlinear speedup can also be obtained when we have access to the internal structure of the processes involved. For example, Clearwater, Hogg, and Huberman (1992) reported superlinear speedup for cryptarithmetic problems as a result of information exchange between the processes. Another example is the works of Kumar and Rao Rao & Kumar, 1993), devoted to parallelizing standard search algorithms, where superlinear speedup is obtained by dividing the search space.
An interesting domain-independent approach is based on "portfolio" construction (Huberman, Lukose, & Hogg, 1997;Gomes & Selman, 1997). In this approach, a different amount of resources is allotted to each process. This can reduce both expected resource consumption and its variance.
In the case of non-deterministic algorithms, another way to benefit from solution time diversity is to restart the same algorithm in attempt to switch to a better trajectory. Such a framework was analyzed in detail by Luby, Sinclair, and Zuckerman (1993) for the case of a single processor and by Luby and Ertel (1994) for the multiprocessor case. In particular, it was proven that for a single processor, the optimal strategy is to periodically restart the algorithm after a constant amount of time until the solution is found. This strategy was successfully applied to combinatorial search problems by Gomes, Selman, and Kautz (1998).
There are several settings, however, where the restart strategy is not optimal. If the goal is to schedule a number of runs of a single non-deterministic algorithm, such that this number is limited due to the nature of the problem (for example, robotic search), the restart strategy is applicable but not optimal. A special case of the above settings is scheduling a number of runs of a deterministic algorithm with a finite set of available initial configurations (inputs). Finally, the case where the goal is to schedule a set of algorithms different from each other is out of the scope of the restart strategy.
The goal of this research is to develop a methodology for designing an optimal scheduling policy for any number of instances of algorithm-problem pairs, where the algorithms can be either deterministic or non-deterministic. We present a formal framework for scheduling parallel anytime algorithms for the case where the processes share resources (a singleprocessor model), based on the statistical characteristics of the algorithms involved. The framework assumes that we know the probability of the goal condition to be satisfied as a function of time (a performance profile (Simon, 1955;Boddy & Dean, 1994) restricted to Boolean quality values). We analyze the properties of optimal schedules for the suspendresume model, where allocation of resources is performed on mutual exclusion basis, and show that in most cases an extension of the framework to intensity control, where resources may be allocated simultaneously and proportionately to multiple demands, does not yield better schedules. We also present an algorithm for building optimal schedules. Finally, we demonstrate experimental results for the optimal schedules.

Motivation
Before starting the formal discussion, we would like to illustrate how different scheduling strategies can affect the performance of a system of two search processes. The first example has a very simple setup which allows us to perform a full analysis. In the second example, we show quantitative results for a real CSP problem.

Scheduling DFS Search Processes
Assume DFS with random tie-breaking is applied to a simple search space shown in Figure 1, but that only two runs of the algorithm are allowed 1 . There is a very large number of paths to the goal, half of them of length 10, quarter of them of length 40, and quarter of them of length 160. When one of the processes finds the solution, the task is considered accomplished. We consider a single-processor system, where the two processes cannot run simultaneously. Let us denote the processes by A 1 and A 2 , and by L 1 and L 2 the actual path lengths for A 1 and A 2 respectively for the particular run.
The application of a single processes (without loss of generality, A 1 ) gives us the expected execution time of 1/2 × 10 + 1/4 × 40 + 1/4 × 160 = 55, as is shown in Figure 2. We can improve the performance by simulating a simultaneous execution of two processes. For this purpose, we allow each of the processes to expand a single node, and to switch to the other process (without loss of generality, A 1 starts first). In this case, the expected execution time is 1/2 × 19 + 1/4 × 20 + 1/8 × 79 + 1/16 × 80 + 1/16 × 319 = 49.3125, as is shown in Figure 3.
Finally, if we know the distribution of path lengths, we can allow A 1 to open 10 nodes; if A 1 fails, we can stop it and allow A 2 to open 10 nodes; if A 2 fails as well, we can allow A 1 to open the next 30 nodes, and so forth. In this scenario, A 1 and A 2 switch after 10 and 40 nodes (if both processes fail to find a solution after 40 nodes, it is guaranteed to be found by A 1 after 160 nodes). This scheme is shown in Figure 4, and the expected time is 1/2 × 10 + 1/4 × 20 + 1/8 × 50 + 1/16 × 80 + 1/16 × 200 = 33.75.

The Latin Square Example
The task in the Latin Square problem is to place N symbols on an N × N square such that each symbol appears only once in each row and each column. An example is shown in Figure 5.
A more interesting problem arises when the square is partially filled. The problem in this case may be solvable (see the left side of Figure 6) or unsolvable (see the right side of Figure 6). The problem of satisfiability of a partially filled Latin Square is a typical constraint-satisfaction problem. We consider a slight variation of this task. Let us assume that two partially filled squares are available, and we need to decide whether at least one of them is solvable. We assume that we are allocated a single processor. We attempt to speed up the time of finding a solution by starting to solve the two problems from two different initial configurations in parallel.
Each of the processes employs a deterministic heuristic DFS with the First-Fail heuristic (Gomes & Selman, 1997). We consider 10%-filled 20 × 20 Latin Squares. The behavior of a single process measured on a set of 50,000 randomly generated samples is shown in L 1 = 160, L 2 = 160, cost = 319 L 1 = 160, L 2 = 160 0 1 2 3 4 5 6 7 8 9 10 Figure 3: Path lengths, probabilities and costs for simulating a simultaneous execution L 1 = 10, L 2 ≥ 10, cost = 10 L 1 ≥ 40, L 2 = 10, cost = 20  each run is limited to 25,000 search steps (only 88.6% of the problems are solvable under this condition). If we apply the algorithm only on one of the available two initial configurations, the average number of search steps is 3777. If we run two processes in parallel (alternating after each step), we obtain a result of 1358 steps. If we allow a single switch at the optimal point (an analogue of the restart technique (Luby et al., 1993;Gomes et al., 1998) for two processes), we get 1376 steps on average (the optimal point is after 1311 steps). Finally, if we interleave the processes, switching at the points corresponding to 679, 3072, and 10208 of total steps, the average number of steps is 1177. The above results were averaged over a test set of 25,000 pairs of initial configurations.
The last sequence of switch points is an optimal schedule for the process with behavior described by the graphs in Figure 7. In the rest of the paper we present an algorithm for deriving such optimal schedules.

A Framework for Parallelization Scheduling
In this section we formalize the intuitive description of parallelization scheduling. The first part of this framework is similar to our framework presented in (Finkelstein & Markovitch, 2001).
Let S be a set of states, t be a time variable with non-negative real values, and A be a random process such that each realization (trajectory) A(t) of A represents a mapping from R + to S. Let X 0 be a random variable defined over S. Since an algorithm Alg starting from an initial state S 0 corresponds to a single trajectory (for deterministic algorithms), or to a set of trajectories with an associated distribution (for non-deterministic algorithms), the pair X 0 , Alg , where X 0 stands for the initial state, can be viewed as a random process. Drawing a trajectory for such a process corresponds, without loss of generality, to a twostep procedure: first an initial state S 0 is drawn for X 0 , and then a trajectory A(t) starting from S 0 is drawn for Alg. Thus, the source of randomness is either the randomness of the initial state, or the randomness of the algorithm (which can come from the algorithm itself or from the environment), or both.
Let S * ⊆ S be a designated set of states, and G : S → {0, 1} be the characteristic function of S * called the goal predicate. The behavior of a trajectory A(t) of A with respect to the goal predicate G can be written as G(A(t)), which we denote by G A (t). We say that A is monotonic over G if and only if G A (t) is a non-decreasing function for each trajectory A(t) of A. Under the above assumptions G A (t) is a step function with at most one discontinuity point.
Let A be monotonic over G. From the definitions above we can see that the behavior of G for each trajectory A(t) of A can be described by a single point t A,G , the first point after which the goal predicate is true, i.e, t A,G = inf t {t| G A (t) = 1}. If G A (t) is always 0, we say that t A,G is not defined. Therefore, we can define a random variable, which for each trajectory A(t) of A with t A,G defined, corresponds to t A,G . The behavior of this variable can be described by its distribution function F (t). At the points where F (t) is differentiable, we use the probability density f (t) = F ′ (t).
It is important to note that in practice not every trajectory of A leads to the goal predicate satisfaction even after infinitely large time. That means that the set of the trajectories where t A,G is undefined is not necessarily of measure zero. That is why we define the probability of success p as the probability of A(t) to have t A,G defined 2 . For the Latin Square example described in Section 2.2, the probability of success is 0.886, and the graphs in Figure 7 correspond to pF (t) and pf (t).
Assume now that we have a system of n random processes A 1 , . . . A n with corresponding distribution functions F 1 , . . . , F n and goal predicates G 1 , . . . , G n . If the distribution functions F i and F j are identical, we refer to A i and A j as F -equivalent.
We define a schedule of the system as a set of binary functions {θ i }, where at each moment t, the i-th process is active if θ i (t) = 1 and idle otherwise. We refer to this scheme as suspend-resume scheduling. A possible generalization of this framework is to extend the suspend/resume control to a more refined mechanism that allows us to determine the intensity with which each process acts. For software processes, this means varying the fraction of CPU utilization; for tasks like robot navigation this implies changing the speed of the robots. Mathematically, using intensity control is equivalent to replacing the binary functions θ i (t) with continuous functions with a range between zero and one 3 .
Note that scheduling makes the term time ambiguous. On one hand, we have the subjective time for each process, consumed only when the process is active. This kind of time corresponds to some resource consumed by the process. On the other hand, we have an objective time measured from the point of view of an external observer. The distribution function F i (t) of each process is defined over its subjective time, while the cost function (see below) may use both kinds of times. Since we are using several processes, all the formulas in this paper are based on the objective time.
Let us denote by σ i (t) the total time that process i has been active before t. By definition, (1) In practice σ i (t) provides the mapping from the objective time t to the subjective time of the i-th process, and we refer to these functions as subjective schedule functions. Since θ i can be obtained from σ i by differentiation, we often describe schedules by , and therefore A is monotonic over G. We denote the distribution function of the corresponding random variable by F n (t, σ 1 , . . . , σ n ), and the corresponding distribution density by f n (t, σ 1 , . . . , σ n ).
Assume that we are given a monotonic non-decreasing cost function u(t, t 1 , . . . , t n ), which depends on the objective time t and the subjective times per process t i . We also assume that u(0, t 1 , . . . , t n ) = 0. Since the subjective times can be calculated by σ i (t), we actually have u = u(t, σ 1 (t), . . . , σ n (t)).
The expected cost of schedule {σ i } can be expressed, therefore, as 4 E u (σ 1 , . . . , σ n ) = +∞ 0 u(t, σ 1 , . . . , σ n )f n (t, σ 1 , . . . , σ n )dt (2) (for the sake of readability, we omit t in σ i (t)). Under the suspend-resume model assumptions, σ i must be differentiable (except for a countable set of process switch points) and have derivatives of 0 or 1 that would ensure correct values for θ i . Under intensity control assumptions, the derivatives of σ i must lie between 0 and 1. We consider two alternative setups for resource sharing between the processes: 1. The processes share resources on a mutual exclusion basis. That means that exactly one process can be active at each moment, and the processes will be active one after another until the goal is reached by one of them. In this case the sum of derivatives 3. A special case of such a setup using constant intensities was described by Huberman, Lukose, and Hogg (1997). 4. The generalization to the case where the probability of success p is not 1 is considered at the end of the next section.
of σ i is always one 5 . The case of shared resources corresponds to the case of several processes running on a single processor.
2. The processes are fully independent: there are no additional constraints on σ i . This case corresponds to n independent processes running on n processors.
Our goal is to find a schedule which minimizes the expected cost (2) under the corresponding constraints. The current paper is devoted to the case of shared processes. The case of independent resources was studied in (Finkelstein, Markovitch, & Rivlin, 2002). The scheduled algorithms considered in this framework can be viewed as anytime algorithms. The behavior of anytime algorithms is usually characterized by their performance profile -the expected quality of the algorithm output as a function of the alloted resources. The goal predicate G can be viewed as a quality function with two possible values, and thus the distribution function F (t) meets the definition of performance profile, where time plays the role of resource.

Suspend-Resume Based Scheduling
In this section we consider the case of suspend-resume based control (σ i are continuous functions with derivatives 0 or 1).

Claim 1
The expressions for the goal-time distribution F n (t, σ 1 , . . . , σ n ) and the expected cost E u (σ 1 , . . . , σ n ) are as follows 6 : Proof: Let t i be the time it would take the i-th process to meet the goal if acted alone (if the process fails to reach the goal, we consider t i = ∞). Let t * be the time it takes the system of n processes to reach the goal. In this case, t * is distributed according to F n (t, σ 1 , . . . , σ n ), and t i are distributed according to F i (t). Thus, because the processes, given a schedule, are independent, we obtain (1 − F i (σ i (t))), which corresponds to (3). Since F (t) is a distribution over time, we assume F (t) = 0 for t ≤ 0.
5. This fact is obvious for the case of suspend-resume control, and for intensity control it is reflected in Lemma 3. 6. u ′ t and u ′ σ i stand for partial derivatives of u by t and by σi respectively.
Note that in the case of σ i (t) = t and F i (t) = F (t) for all i (parallel application of n F -equivalent processes), we obtain the formula presented in (Janakiram et al., 1988), i.e., F n (t) = 1 − (1 − F (t)) n .
In the rest of this section we show a formal solution (necessary conditions and an algorithm) for the framework with shared resources. We start with two processes and present the formulas and the algorithm, and then generalize the solution for an arbitrary number of processes. For the case of two processes, we only assume that u is differentiable.
For the more elaborated setup of n processes, we assume that the total cost is a linear combination of the objective time and all the subjective times, and the subjective times are of the same weight: Since time is consumed if and only if there is an active process, and the trivial case where all the processes are idle may be ignored, we obtain (without loss of generality) This assumption is made to keep the expressions more readable. The solution process remains the same for the general form of u.

Necessary Conditions for an Optimal Solution for Two Processes
Let A 1 and A 2 be two processes sharing a resource. While working, one process locks the resource, and the other is necessarily idle. We can show that such dependency yields a strong constraint on the behavior of the process, allowing the building of an effective algorithm for solving the minimization problem.
For the suspend-resume model, therefore, only two states of the system are possible: A 1 is active and A 2 is idle (S 1 ); and A 1 is idle and A 2 is active (S 2 ). We ignore the case where both processes are idle, since removing such a state from the schedule will not increase the cost. Therefore, the system continuously alternates between the two states: S 1 → S 2 → S 1 → S 2 → . . .. We call the time interval corresponding to each pair S 1 , S 2 a phase and denote phase k by Φ k . If we denote the process switch points by t i , the phase Φ k corresponds to [t 2k−2 , t 2k ]. See Figure 8 for an illustration.
Figure 8: Notations for times, states and phases for two processes By this scheme, Let us denote by ζ 2k−1 the total time that A 1 has been active before t 2k−1 , and by ζ 2k the total time that A 2 has been active before t 2k . By phase definition, ζ 2k−1 and ζ 2k correspond to the cumulative time spent in phases 1 to k in states S 1 and S 2 respectively. There exists a one-to-one correspondence between the sequences ζ i and t i : Moreover, by definition of ζ i we have Under the process switch scheme as defined above, the subjective schedule functions σ 1 and σ 2 in time intervals [t 2k , t 2k+1 ] (state S 1 of phase Φ k+1 ) have the form Similarly, in the intervals [t 2k+1 , t 2k+2 ] (state S 2 of phase Φ k+1 ), the subjective schedule functions are defined as Let us denote To provide an optimal solution for the suspend/resume model, we may split (4) to phases Φ k and write it as The last expression may be rewritten as Using (9) on interval [t 2k , t 2k+1 ], performing substitution x = t − ζ 2k , and using (7), we obtain Substituting (13) and (14) into (12), we obtain a new form for the minimization problem: (for the sake of generality, we assume ζ −1 = 0).
The minimization problem (15) is equivalent to the original problem (4), and the dependency between their solutions is described by (9) and (10). The only constraint for the new problem follows from the fact that the processes are alternating for non-negative periods of time: The expression (15) reaches its optimal values either when or on the border described by (16). However, for two processes we can, without loss of generality, ignore the border case. Indeed, assume that ζ i = ζ i+2 for some i > 1 (one of the processes skips its turn). We can construct a new schedule by removing ζ i+1 and ζ i+2 : It is easy to see that the process described by this schedule is exactly the same process as described by the original one, but the singularity point has been removed.
Thus, at each step the time spent by the processes is determined by (17). We can see that ζ 2k appears in three subsequent terms of E u (σ 1 , . . . , σ n ): A similar expression can be derived by differentiating (15) by ζ 2k+1 . Combining these expressions with (17) gives us the following theorem: Theorem 1 (The chain theorem for two processes) The value for ζ i+1 for i ≥ 2 can be computed for given ζ i−1 and ζ i using the formulas Corollary 1 For the linear cost function (5), the value for ζ i+1 for i ≥ 2 can be computed for given ζ i−1 and ζ i using the formulas The proof follows immediately from the fact that v i (t 1 , t 2 ) = a + b.
Theorem 1 allows us to formulate an algorithm for building an optimal solution. This algorithm is presented in the next subsection.

Optimal Solution for Two Processes: an Algorithm
The goal of the scheduling algorithm is to minimize the expression (15) Assume that A 1 acts first (ζ 1 > 0). From Theorem 1 we can see that the values of ζ 0 = 0 and ζ 1 determine the set of possible values for ζ 2 , the values of ζ 1 and ζ 2 determine the possible values for ζ 3 , and so on.
Therefore, a non-zero value for ζ 1 provides us with a tree of possible values of ζ k . The branching factor of this tree is determined by the number of roots of (18) and (19). Each possible sequence ζ 1 , ζ 2 , . . . can be evaluated using (15).
For the cases where the total time is limited as discussed in Section 4.5, or where the series in that expression converge, e.g., when each process has a finite cost of finding a solution, the algorithm stops after a finite number of points. In some cases, however, such as for extremely heavy-tailed distributions, it is possible that the above series diverge. To ensure a finite number of iterations in such cases, we set an upper limit on the maximal expected cost.
Another limit is added for the probability of failure. Since t i = ζ i−1 + ζ i , the probability that both runs would not be able to find a solution after t i is becomes small enough, we can conclude that both runs failed to find a solution and stop the execution.
For each value of ζ 1 we can find the best sequence using one of the standard search algorithms, such as Branch-and-Bound. Let us denote the value of the best sequence for each ζ 1 by E u (ζ 1 ). Performing global optimization of E u (ζ 1 ) by ζ 1 provides us with an optimal solution for the case where A 1 acts first. Note that the value of ζ 1 may also be 0 (A 2 acts first), so we need to compare the value obtained by optimization of ζ 1 with the value obtained by optimization of ζ 2 where ζ 1 = 0.
The flow of the algorithm is illustrated in Figure 9, the formal scheme is presented in Figure 10, and the description of the main routine (realized by the DFS Branch and Bound method) in Figure 11.
The algorithm considers two main branches, one for A 1 and one for A 2 , and they are processed by procedure minimize sequence by f irst point (Figure 10). At each step, we initialize the array of ζ values, and pass it, through the procedure build optimal sequence, to the recursive procedure df sbnb, which represents the core of the algorithm ( Figure 11).
The df sbnb procedure, shown in Figure 11, acts as follows. It obtains as an input the array of ζ values, the cost involved up to the current moment, and the best value reached till now. If the cost exceeds this value, the procedure performs a classical Branch-and-Bound cutoff (lines 1-2).
The inner loop (lines 4-19) corresponds to different roots of the expressions (18) and (19). The new value of ζ corresponding to ζ k is calculated by the procedure calculate next zeta (line 5), and it cannot exceed the previously found root saved in last zeta (for the first iteration, last zeta is initialized to ζ k−2 ), lines 3 and 8. Lines 6-7 correspond to the case where the lower bound passed to calculate next zeta exceeds the maximal available time, and in this case the procedure is stopped.
After the new possible value of ζ is found, the procedure updates the current cost (line 9), and the stopping criteria mentioned above are validated for the new array of ζ values, which is denoted as a concatenation of the old array and the new value of ζ (line 10). If the task is accomplished, the cost is verified versus the best known value (which is updated if necessary), and the procedure returns (lines 10-16). Otherwise, ζ is temporarily added to the array of ζ, and the Branch-and-Bound procedure is called recursively for calculation ζ k+1 .
When the whole tree is traversed (except the cutoffs), the best known cost is returned (line 20). The corresponding array of ζ is the required solution. Figure 13 shows a trace of a single Branch-and-Bound run for the example shown in Section 2.2 starting with the optimal value of ζ 1 . The optimal schedule derived from the the run is 679, 2393, 7815, 17184 with expected cost of 1216.49 steps. The scheduling points are given in subjective times. Using objective (total) time the schedule can be written as 679, 3072, 10208, and 25000. In this particular run there were no Branch-and-Bound cutoffs due to the small number of roots of (18) and (19).

Necessary Conditions for an Optimal Solution for n Processes
In this section we generalize our solution from the case of two processes to the case of n processes.
Assume that we have n processes A 1 , . . . , A n using shared resources. One of the possible ways to present a schedule is to use a sequence where A i j is the j-th active process, and ∆t j is the time allocated for this invocation of A i j .
To simplify the formalization of the problem, however, we use the following alternative representation. First, we allow ∆t j to be 0, which makes possible it to represent every schedule as

Branch and Bound non-leaf nodes
Leaf nodes (terminating condition satisfied) and cutoff nodes (expected result is worse than the already known). The cost is calculated in accordance with (15).
Get optimal schedule costs for ζ 1 = 0 and for ζ 1 = 0, and return the best value with the corresponding schedule Figure 9: The flow of the algorithm for constructing optimal schedules for 2 processes procedure optimize Input: F 1 (t), F 2 (t) (performance profiles). Output: An optimal sequence and its value.
Using one of the standard minimization methods, find zetas, minimizing the value of the function build optimal sequence(zetas), and the corresponding cost. end Figure 10: Procedure optimize builds an optimal sequence for the case when A 1 starts, an optimal sequence for the case when A 2 starts, compares the results, and returns the best one. Procedure minimize sequence by f irst point returns an optimal sequence and its value.
procedure build optimal sequence(zetas) curr cost ← calculate cost(zetas) return df sbnb(zetas, curr cost, M AX V ALU E) end procedure df sbnb(zetas, curr cost, thresh) 1: if (curr cost ≥ thresh) then 2: return M AX V ALU E // Cutoff 3: last value ← zetas[length(zetas) − 2] // The previous time value 4: repeat 5: ζ ← calculate next zeta(zetas, last value) 6: if (ζ = last value) then // Skip 7: return thresh 8: last value ← ζ 9: delta cost ← calculate partial cost(zetas, ζ) 10: if (  1. calculate cost(zetas) computes the cost of the sequence (or its part) in accordance with (15), 2. calculate partial cost(zetas, ζ) computes the additional cost obtained by adding ζ to the sequence, 3. calculate next zeta(zetas, last value) uses (18) or (19) to calculate the value of the next ζ that is greater than last value. If no such a solution exists, the maximal time value is returned, 4. task accomplished(zetas) returns true when the task may be considered to be accomplished (e.g., either maximal possible time is over, or the probability of error is negligible, or the upper limit on the cost is exceeded). Therefore, the system alternates between n states S 1 → S 2 → . . . → S n → S 1 → . . ., where the state S i corresponds to the situation where A i is active and the rest of the processes are idle. The time spent in the k-th invocation of S i is ∆t kn+i . As in the case of two processes, we call the time interval corresponding to the sequence of states S 1 → S 2 → . . . → S n a phase and denote phase k by Φ k . We denote the process switch points of Φ k by t 1 k , t 2 k , . . . , t n k , where , and the entire phase lasts from t 0 k to t n k . The corresponding scheme is shown in Figure 14. To simplify the following discussion, we would like to allow indices i in t i k to be less than 0 or greater than n. For this purpose, we denote and the index of the process active in the interval [t i−1 k , t i k ] we denote by #i. For i mod n = 0 we obtain #i = i mod n, while for i mod n = 0 we have #i = n. Notation (22) claims that the shift by n in the upper index is equivalent to the shift by 1 in the phase number: As in the case of two processes, we denote by ζ i k the total time that A #i has been active up to t i k . ζ i k corresponds to the cumulative time spent in phases 1 to k in state S #i , and there is a one-to-one correspondence between the sequences of ζ i k and t i k : The first equation corresponds to the fact that the time between t i−1 k and t i k is accumulated into the ζ values of process A #i , while the second equation claims that at each switch the objective time of the system is equal to the sum of the subjective times of each process. For the sake of uniformity we also denote By construction of ζ i k we can see, that at time interval [t i−1 k , t i k ] the subjective time of process A j has the following form: The subjective time functions for a system with 3 processes are illustrated in Figure 15. Figure 15: Subjective time functions for a system with 3 processes To find an optimal schedule for a system with n processes, we need to minimize the expression given by (6). The only constraints are the monotonicity of the sequence of ζ for each process i: Given the expressions for σ j , we can prove the following lemma: Lemma 1 For a system of n processes, the expression for the expected cost (6) can be rewritten as The proof is given in Appendix A.1. This lemma makes it possible to prove the chain theorem for an arbitrary number of processes: Theorem 2 (The chain theorem) The value for ζ l−1 m+1 may either be ζ l−1 m , or can be computed given the previous 2n − 2 values of ζ using the formula The proof of the theorem is given in Appendix A.2.

Optimal Solution for n Processes: an Algorithm
The goal of the presented algorithm is to minimize the expression (27) As in the case of two processes, assume that A 1 acts first. By Theorem 2, given 2n − 2 values of ζ ζ 0 1 , ζ 1 1 , . . . , ζ n 1 , ζ 1 2 , ζ 2 2 , ζ n−3 2 , we can determine all the possibilities for the value of ζ n−2 2 (either ζ n−2 1 if the process skips its turn, or one of the roots of (28)). Given the values up to ζ n−2 2 , we can determine the values for ζ n−1 2 , and so on. The idea of the algorithm is similar to the algorithm for two processes. The first 2n − 2 variables (including ζ 0 1 = 0) determine the tree of possible values for ζ. Optimization over 2n−3 first variables, therefore, provides us with an optimal schedule (as before, we compare the results for the case where the first k < n variables are 0). The only difference from the case of two processes is that a process may skip its turn. However, we can ignore the case when all the processes skip their turn, since we can remove such a loop from the schedule. The scheme of the algorithm is presented in Figure 16, and the description of the main routine (realized by the DFS Branch and Bound method) is presented in Figure 17.

Optimal Solution in the Case of Additional Constraints
Assume now that the problem has additional constraints: the solution time is limited by T and the probability of success of the i-th process p i is not necessarily 1.
It is possible to show that the expressions for the distribution function and the expected cost have almost the same form as in the regular framework: Claim 2 Let the system solution time be limited by T , and let p i be the probability of success for the i-th process. Then the expressions for the goal-time distribution and expected cost Procedure optimize builds n optimal schedules (each process may start first), compares the results, and returns the best one procedure optimize best val ← M AX V ALU E best sequence ← ∅ loop for i from 1 to n do [sequence, val] ← minimize sequence by f irst points(i) if (val < best val) then best val ← val best sequence ← sequence end return [best sequence, best val] end // Procedure minimize sequence by f irst points gets as a parameter // the index of a process which starts, and returns an optimal // sequence and its value procedure minimize sequence by f irst points(process to start) loop for i from 0 to n − 1 zetas[−i] ← 0 end loop for i from 1 to process to start − 1 zetas[i] ← 0 end Using one of the standard minimization methods, find zetas, minimizing the value of the function build optimal sequence(zetas). end   are as follows: The proof is similar to the proof of Claim 1. This claim shows that all the formulas used in the previous sections are valid for the current settings, with three differences: 1. We use p j F j instead of F j and p j f j instead of f j .
2. All the integrals are from 0 to T instead of from 0 to ∞.

All time variables are limited by T .
The first two conditions may be easily incorporated into all the algorithms. The last condition implies additional changes in the chain theorems and the algorithms. The chain theorem for n processes now becomes: Theorem 3 The value for ζ j k can either be ζ j k−1 , or it can be computed given the previous 2n − 2 values of ζ using formula (28), or it can be calculated by the formula The first two alternatives are similar to Theorem 2, while the third one corresponds to the boundary condition given by Equation (24). This third alternative adds one more branch to the DFS Branch and Bound algorithm; the rest of the algorithm remains unchanged. Similar changes in the algorithms are performed in the case of the maximal allowed time T i per process. In practice, we always use this limitation, setting T i such that the probability for A i to reach the goal after T i , p i (1 − F i (T i )), becomes negligible.

Process Scheduling by Intensity Control
In this section we analyze the problem of optimal scheduling for the case of intensity control, which is equivalent to replacing the binary scheduling functions θ i (t) with continuous functions with a range between 0 and 1. In this paper we assume a linear cost function of the form (5). We believe, however, that similar analysis is applicable to the setup with any differentiable u.
It is easy to see that all the formulas for the distribution function and the expected cost from Claim 1 are still valid under intensity control settings.
For the linear cost function (5), the minimization problem has the form Without loss of generality, we can assume a + b = 1. This leads to the equivalent minimization problem where c = b/(a + b) can be viewed as a normalized resource weight. The constraints, however, are more complicated than for the suspend/resume model: 1. As before, σ i must be continuous, and σ i (0) = σ ′ i (0) = 0 (at the beginning all the processes are idle).
2. We assume σ i to have a partially-continuous derivative σ ′ i , and this derivative should lie between 0 and 1. This requirement follows from the definition of intensity and the fact that σ ′ i = θ i : no process can work for a negative amount of time, and no process can work with the intensity greater than the one allowed. Since we consider a framework with shared resources, and the total intensity is limited, we have an additional constraint: the sum of all the derivatives σ ′ i at any time point cannot exceed 1.
Thus, this optimization problem has the following boundary conditions: We are looking for a set of functions {σ i } that provide a solution to minimization problem (33) under constraints (34).
A traditional method for solving problems of this type is to use the Euler-Lagrange necessary conditions: a set of functions σ 1 , . . . , σ n provides a weak (local) minimum to the functional only if σ 1 , . . . , σ n satisfy a system of equations of the form We can prove the following lemma: Lemma 2 The Euler-Lagrange conditions for minimization problem (33) yield two strong invariants: 1. For processes k 1 and k 2 for which σ k 1 and σ k 2 are not on the border described by (34), the distribution and density functions satisfy 2. If the schedules of all the processes are not on the border described by (34), then either c = 1 or f k (σ k ) = 0 for each k.
The proof of the lemma is given in Appendix A.3. The above lemma provides necessary conditions for a local minimum in the inner points described by constraints (34). These conditions, however, are very restricting. Therefore, we look for more general conditions, suitable for boundary points as well 7 . We start with the following lemma: (34) exists, then there exists an optimal solution σ 1 , . . . , σ n , such that at each time t all the resources are consumed, i.e.,

Lemma 3 If an optimal solution for minimization problem (33) under constraints
In the case where time cost is not zero (c = 1), the equality above is a necessary condition for solution optimality.
The proof of the lemma is given in Appendix A.4.
Lemma 3 corresponds to our intuition: if a resource is available, it should be used. Without loss of generality, we restrict our discussion to schedules satisfying (38), even in the case where time cost is zero. This leads to the following invariant: Assume now that we have two F -equivalent processes A 1 and A 2 with density function f (t) satisfying the normal distribution law with mean value m. Let t 1 and t 2 be the cumulative time consumed by each of the processes at time t, i.e., σ 1 (t) = t 1 and σ 2 (t) = t 2 . The question is, which process should be active at t (or should they be active in parallel with partial intensities)?
7. Note also that even if the conditions above hold, they do not necessarily provide the optimal solution.
Moreover, problems in variation calculus do not necessarily have a minimum, since there is no analogue for the Weierstrass theorem for continuous functions on a closed set.
Without loss of generality, t 1 < t 2 , which means that the first process is required to cover a larger area to succeed: 1 − F (t 1 ) > 1 − F (t 2 ). This supports a policy that at time t activates the second process. This policy is further supported if A 1 has a lower distribution density, f 1 (t 1 ) < f 2 (t 2 ), as illustrated in Figure 18(a). If, however, the first process has a higher density, as illustrated in Figure 18(b), it is not clear which of the two processes should be activated at time t. What is the optimal policy in the general case 8 ? The answer relies  Figure 18: (a) Process A 1 (currently at t 1 ) has lower density and larger area to cover, and therefore is inferior. (b) Process A 1 has lower density, but smaller area to cover, and the decision is unclear.
heavily on the functions that appear in (37). These functions, described by the equation are known as hazard functions, and they play a very important role in the following theorem describing necessary conditions for optimal schedules.

Theorem 4 Let the set of functions {σ i } be a solution of minimization problem (6) under constraints (34). Let t 0 be a point where the hazard functions of all the processes h i (σ i (t))
are continuous, and let A k be the process active at t 0 (σ ′ k (t 0 ) > 0), such that for any other Then at t 0 process k consumes all the resources, i.e. σ ′ k (t 0 ) = 1.
The proof of the theorem is given in Appendix A.5. By Theorem 4 and Equation (37), intensity control may only be useful when hazard functions of at least two processes are equal. However, even in this case the equilibrium is not always stable. Assume that within some interval [t ′ , t ′′ ] processes A i and A j are working with partial intensity, which implies h i (σ i (t)) = h j (σ j (t)). Assume now that both 8. Analysis of normal distribution given in Section 6.3 shows that the optimal policy in the example above is to give all the resources to process A2 in both cases.
h i (t) and h j (t) are monotonically increasing. If at some moment t we give a priority to one of the processes, it will obtain a higher value of the hazard function, and will get all the subsequent resources. The only case of stable equilibrium is when h i (σ i (t)) and h j (σ j (t)) are monotonically decreasing functions or constants. The intuitive discussion above is formulated in the following theorem: Theorem 5 An active process will remain active and consume all resources as long as its hazard function is monotonically increasing.
The proof is given in Appendix A.6. This theorem imply the important corollary: Corollary 3 If the hazard function of one of the processes is greater than or equal to that of the others at t = 0 and is monotonically increasing by t, this process should be the only one to be activated.
We can conclude that the extension of the suspend-resume model to intensity control in many cases does not increase the power of the model and is beneficial only for monotonically decreasing hazard functions. If no time cost is taken into account (c = 1), however, the intensity control permits us to connect the two concepts: that of the model with shared resources and that of the model with independent agents:

Theorem 6 If no time cost is taken into account (c = 1), the model with shared resources under intensity control settings is equivalent to the model with independent processes under suspend-resume control settings. Namely, given a suspend-resume solution for the model with independent processes, we may reconstruct an intensity-based solution with the same cost for the model with shared resources and vice versa.
The proof of the theorem is given in Appendix A.7.
Theorem 4 claims that if the process with the maximal value of h k (σ k (t)) is active, it will take all the resources. Why, then, would we not always choose the process with the highest value of h k (σ k (t)) to be active? It turns out that such a strategy is not optimal. Let us consider two processes with the distribution densities shown in Figure 19(a). The corresponding values of the hazard functions are shown in Figure 19(b). If we were using the above strategy, A 2 would be the only active process. Indeed, at time t = 0, h 2 (σ 2 (0)) > h 1 (σ 1 (0)), which would lead to the activation of A 2 . After that moment, A 1 would remain idle and its hazard function remain 0. This strategy would result in an expected time of 2. If, on the other hand, we would have activated A 1 only, the result would be an expected time of 1.5. Thus, although h 1 (σ 1 (0)) < h 2 (σ 2 (0)), it is better to give all the resources to A 1 from the beginning due to its superiority in the future.
A more elaborate example is shown in Figure 20. It corresponds to the case of two processes that are not F -equivalent, one of which is a linear combination of two normal distributions, f (t) = 0.5f N (0.6,0.2) (t) + 0.5f N (4.0,2.0) (t), where f N (µ,σ) (t) is the distribution density of normal distribution with mean value µ and standard deviation σ, and the second process is uniformly distributed in [1.5, 2.5]. Activating A 1 only results in 0.5 × 0.6 + 0.5 × 4.0 = 2.3, activating A 2 only results in an expected time of 2.0, while activating A 1 for time 1.2 followed by activating A 2 results in (approximately) 0.6 × 0.5 + (1.2 + 2.0) × 0.5 = 1.9.  Figure 19: The density function and the hazard function for two processes. Although h 1 (σ 1 (0)) < h 2 (σ 2 (0)), it is better to give all the resources to A 1 .
The best solution is, therefore, to start the execution by activating A 1 , and at some point t ′ transfer the control to A 2 . In this case we interrupt an active process with a greater value of hazard function, preferring an idle process with a zero value of hazard function (since h 1 (σ 1 (t ′ )) > h 2 (σ 2 (t ′ )) = 0). These examples show that a straightforward use of hazard functions for building optimal schedules can be very problematic. However, since the suspend-resume model is a specific case of the intensity control model, the hazard functions still may be useful for understanding the behavior of optimal schedules, and this is used in the next section.

Optimal Scheduling for Standard Distributions
In this section we present the results of the optimal scheduling strategy for a system of processes whose performance profiles meet one of the well-known distributions: uniform, exponential, normal and lognormal. Then we show the results for processes with bimodal and multimodal distribution functions.
We have implemented three scheduling policies for two agents: 1. Sequential strategy, which schedules the processes one after another, initiating the second process when the probability that the first one will find a solution becomes negligible. For processes that are not F -equivalent, we choose the best order of process invocation.
2. Simultaneous strategy, which simulates a simultaneous execution of both processes.
3. Optimal strategy, which is an implementation of the algorithm described in Section 4.2.
In the rest of this section we compare these three strategies, when no deadline is given, and the processes are stopped when the probability that they can still find a solution becomes negligible. Our goal is to compare different scheduling strategies and not to analyze the behavior of the processes. Absolute quantitative measurements, such as average cost, are very process dependent, and therefore are not appropriate for scheduling strategy evaluation. We therefore would like to normalize the results of the application of different scheduling methods to minimize the effect of the process behavior. In the case of F -equivalent processes, a good candidate for the normalization coefficient is the expected time of the individual process. For processes that are not F -equivalent, however, the decision is not straightforward, and therefore we use the results of the sequential strategy as the normalization factor.
We define the relative quality q ref (S) of strategy S with respect to strategy S ref as whereū(S) is the average cost of strategy S. This measurement corresponds to the gain (maybe negative) of strategy S relative to the reference strategy. In this section we use the sequential strategy as our reference strategy.

Uniform Distribution
Assume that the goal-time distribution of the processes meets the uniform law over the interval [t 0 , T ], i.e., has distribution functions and density functions The density function of a process uniformly distributed in [0, 1] is shown in Figure 21(a). The hazard function of the uniform distribution has the form which is a monotonically increasing function. By Corollary 3, only one process will be active, and the optimal strategy should be equivalent to the sequential strategy. If the processes are not F -equivalent, the problem can be solved by choosing the process with the minimal expected time. A more interesting setup involves a uniformly distributed process that is not guaranteed to find a solution. This case corresponds to a probability of success p that is less than 1. As it was claimed in Section 4.5, the corresponding distribution and density function should be multiplied by p. As a result, the hazard function becomes This function is still monotonically increasing by t, and the conclusions remain the same. The graphs for hazard functions of processes uniformly distributed in [0, 1] with probability of success of 0.5, 0.8 and 1 are shown in Figure 21(b).

Exponential Distribution
The exponential distribution is described by the density function and the distribution function has the form Substituting these expressions into (6) gives For a system with F -equivalent processes, by Lemma 3 and therefore Thus, for a system with F -equivalent processes all the schedules are equivalent. This interesting fact is reflected also in the behavior of the hazard function, which is constant: However, if the probability of success is smaller than 1, the hazard function becomes a monotonically decreasing function: Such processes should work simultaneously (with identical intensities for F -equivalent processes, and with intensities maintaining the equilibrium of hazard functions otherwise), since each process which has been idle for a while has an advantage over its working teammate. Figure 22(a) shows the density function of an exponentially distributed process with λ = 1. The graphs for the hazard functions of processes exponentially distributed with λ = 1 and probability of success of 0.5, 0.8 and 1 are shown in Figure 22(b).
Let us consider a somewhat more elaborate example, involving processes that are not F -equivalent. Assume that we have two learning systems, both with an exponential-like performance profile typical of such systems. We also assume that one of the systems requires a delay for preprocessing but works faster. Thus, we assume that the first system has a distribution density f 1 (t) = λ 1 e −λ 1 t , and the second one has a density f 2 (t) = λ 2 e −λ 2 (t−t 2 ) , such that λ 1 < λ 2 (the second is faster), and t 2 > 0 (it also has a delay). Assume that both learning systems are deterministic over a given set of examples, and that they may fail to learn the concept with the same probability of 1 − p = 0.5. The graphs for the density and hazard functions of the two systems are shown in Figure 23.
We applied the optimal scheduling algorithm of Section 4.2 for the values λ 1 = 3, λ 2 = 10, and t 2 = 5. The optimal schedule is to activate the first system for 1.15136 time units, then (if it found no solution) to activate the second system for 5.77652 time units. Then the first system will run for additional 3.22276 time units, and finally the second system will run for 0.53572 time units. If at this point no solution has been found, both systems have failed with a probability of 1 − 10 −6 each. Figure 24(a) shows the relative quality of the simultaneous and optimal scheduling strategies as a function of t 2 for p = 0.8 (for 10000 simulated examples). For large values of t 2 the benefit of switching from the first algorithm to the second decreases, and this is reflected in the relative quality of the optimal strategy. The simultaneous strategy, as we can see, is beneficial only for relatively small values of t 2 . Figure 24(b) reflects the behavior of the strategies for a fixed value of t 2 = 5.0 as a function of probability of success p. The simultaneous strategy is inferior, and its quality decreases while p increases. Indeed, when the probability of success is 1, running the second algorithm and the first one simultaneously will be a waste of time. On the other hand, the optimal strategy has a positive benefit, which means that the resulting schedules are not trivial.

Normal Distribution
The normal distribution with mean value m and deviation σ is described by the density function and its distribution function is Since we use t 0 = 0, we should have used a truncated normal distribution with a distribution density and a distribution function but if m is large enough, µ may be considered to be 0. The density function of a normally distributed process with m = 5 and σ = 1 is shown in Figure 25(a). The hazard function of a normal distribution is monotonically increasing, which leads to the same conclusions as for a uniform distribution. However, a probability of success of less than 1 completely changes the behavior of the hazard function: after some point, it starts to decrease. The graphs for hazard functions of processes normally distributed with a mean value of 5, standard deviation of 1 and probabilities of success of 0.5, 0.8 and 1 are shown in Figure 25  hazard functions for normally distributed processes with m = 5 and σ = 1, with the probabilities of success of 0.5, 0.8 and 1.
As in the previous example, we now consider a case of two processes that are not Fequivalent, running with the same deviation σ = 1 and the same probability of success p. The first process is assumed to have m 1 = 1, while the second process is started with some delay ∆m. The relative quality for 10000 simulated examples is shown in Figure 26. Figure 26(a) shows the relative quality as a function of ∆m for p = 0.8; Figure 26(b) shows the relative quality as a function of p for ∆m = 2. Unlike exponential distribution, the gain for this example for the optimal strategy is rather small.

Lognormal Distribution
The random variable X is lognormally distributed, if ln X is normally distributed. The density function and the distribution function with the corresponding parameters m and σ can be written as Lognormal distribution plays a significant role in AI applications since in many cases search time is distributed under the lognormal law. The density function of the lognormal distribution with mean value of log(5.0) and standard deviation of 1.0 is shown in Figure 27(a), and the hazard functions for different values of p are shown in Figure 27(b). Let us consider a simulated experiment similar to its analogue for normal distribution. We consider two processes that are not F -equivalent, with the parameters σ = 1 and the same probability of success p. The first process is assumed to have m 1 = 1, while the second process is started with some delay, such that m 2 − m 1 = ∆m > 0. The relative quality for 10000 simulated examples is shown in Figure 28. Figure 28(a) shows the relative quality as a function of ∆m for p = 0.8; Figure 28(b) shows the relative quality as a function of p for ∆m = 2. The graphs show that for small values of ∆m both the optimal and the simultaneous strategy have a significant benefit over the sequential one. However, for larger values, the performance of the optimal strategy approaches the performance of the sequential strategy, while the simultaneous strategy becomes inferior.

Bimodal and Multimodal Density Functions
Experiments show that in the case of F -equivalent processes with a unimodal distribution function, the sequential strategy is often optimal. In this section we consider less trivial distributions. Assume first that we have a non-deterministic algorithm with a performance profile expressed by a linear combination of two normal distributions with the same deviation: An example of the density and hazard functions of such distributions with µ 1 = 2, µ 2 = 5, and σ = 0.5 is given in Figure 29. the density function f (t) = 0.5f N (2,0.5) + 0.5f N (5,0.5) with the probability of success of p = 0.8.
Assume that we invoke two runs of this algorithm with fixed values of µ 1 = 2, σ = 0.5, and p = 0.8, and the free variable µ 2 . Figure 30 shows how the relative quality of the scheduling strategies is influenced by the distance between the peaks, µ 2 − µ 1 . The results correspond to the intuitive claim that the larger distance between the peaks, the more attractive the optimal and the simultaneous strategies become. Relative quality (in percent) Distance between the peaks Optimal Simultaneous Figure 30: Bimodal distribution: relative quality as a function of the distance between the peaks. Now let us see how the number of peaks of the density function affects the scheduling quality. We consider a case of partial uniform distribution, where the density is distributed over k identical peaks of length 1 placed symmetrically in the time interval from 0 to 100. (Thus, the density function will be equal to 1/k when t belongs to one of such peaks, and 0 otherwise.) In this experiment we have chosen p = 1. Figure 31 shows the relative quality of the system as a function of k, obtained for 10000 randomly generated examples. We can see from the results, that the simultaneous strategy is inferior, due to the "valleys" in the distribution function. The optimal strategy returns schedules where the processes switch after each peak, but the relative quality of the schedules decreases as the number of peaks increases.

Experiments: Using Optimal Scheduling for the Latin Square Problem
To test the performance of our algorithm in a realistic domain, we applied it to the Latin Square problem described in Section 2.2. We assume that we are given a Latin Square problem with two initial configurations, and a fully deterministic algorithm with distribution function and distribution density shown in Figure 7.
We compare the performance of the schedule produced by our algorithm to the performance of the sequential and simultaneous strategies described in Section 6. In addition, we test a schedule which runs the processes one after another, allowing a single switch at the optimal point (an analogue of the restart technique for two processes). We refer to this schedule as a single-point restart schedule.
Note that the case of two initial configurations corresponds to the case of two processes in our framework. In general, we could think of a set of n initial configurations that would correspond to n processes. For sufficiently large n, the restart strategy where each restart starts with a different initial configuration, becomes close to optimal.
Our experiments were performed for different values of N , with 10% of the square precolored. The performance profile was induced based on a run of 50, 000 instances, and the remaining 50, 000 instances were used as 25, 000 testing pairs. All the schedules were applied with a fixed deadline T , which corresponds to the maximal allowed number of generated nodes.
Since the results of the sequential strategy in this type of problems are much worse than the results of other strategies for sufficiently large values of T , we instead used the simultaneous strategy as the reference in the relative quality measure. For small values of T , both single-point restart and the optimal strategy have about a 25% gain over the simultaneous strategy, since they produce schedules which are close to the sequential one. However, when available time T increases, the benefit of parallelization becomes more significant, and the simultaneous strategy overcomes the single-point restart strategy. The relative quality of the optimal schedule also decreases when T increases, since the resulting schedule contains more switches between the two problem instances being solved. Figure 33 illustrates how the optimal and single-point restart schedules relate to the simultaneous schedule for different size Latin Squares (given T = 25, 000). The initial gain of both strategies is about 50%. However, for the problems with N = 20 the single-point restart strategy becomes worse than the simultaneous one. For larger sizes the probability of solving the Latin Square problem with a time limit of 25, 000 steps becomes smaller and smaller, and the benefit of the optimal strategy also approaches zero.  Luby, Sinclair, and Zuckerman (1993) showed that the restart strategy is optimal if an infinite number of identical runs are available. When this number is limited, the restart strategy is not optimal. Sometimes, however, we have a mixed situation. Assume that we have two initial states, a non-deterministic algorithm, and a linear time cost. On one hand, we can perform restarts of a run corresponding to one of the initial states. On the other hand, we can switch between the runs corresponding to the two initial states. What would be an optimal policy in this case?

Combining Restart and Scheduling Policies
The expected time of a run based on a single initial state is where t * is the restart point and F (t) is the distribution function. This formula is obtained by a simple summation of the geometric series with coefficient 1− F (t * ), and is a continuous form of the formula given by Luby, Sinclair, and Zuckerman (1993). Minimization of (53) by t * gives us the optimal restart point. Assume first that the sequence of restarts on a single initial state is a process interruptible only at the restart points. Since the probability of failure of i successive restarts is (1 − F (t * )) i , this process is exponentially distributed. Thus, the problem is reduced to scheduling of two exponentially distributed processes. According to the analysis in Section 6.2, all schedules are equivalent if the problems corresponding to the two initial states are solvable. Otherwise, the optimal policy is to alternate between the two processes at each restart point.
A more interesting case is when we allow rescheduling at any time point. In general, it is not beneficial to switch between the processes in non-restart points (otherwise these rescheduling points would have been chosen for restart). Such rescheduling, however, can be beneficial if the cost associated with restarts is higher than the rescheduling cost 9 .
Let us assume that each restart has a constant cost C. Similarly to (53), we can write the expected cost of a policy performing restarts at point t * * as where the second term corresponds to the series Let t * * and t * be the optimal restart points for the setups with and without associated costs respectively. t * * should be greater than t * due to the restart cost. Let us consider the following schedule: the first process runs for t * , then the second process runs for t * , then the first process runs (with no restart) for additional t * * − t * , then the second process runs for additional t * * − t * . Then the first process restarts and runs for t * and so forth.
Let us compare the expected time of such schedule with the time of the pure restart policy, where the first process runs for t * * , then the second process runs for t * * , then the first process restarts and runs for t * * and so forth.
Similarly to (15), the expected time of the first schedule in the interval [0, 2t * * ] can be written as On the other hand, the expected time of the second schedule in the same interval is 9. An example for such setup is robotic search, where returning the robot to the initial position is more expensive than suspending and resuming the robot.
E sched can be rewritten as Thus, we obtain and since t * provides minimum for (53), the last expression is positive, which means that scheduling improves a simple restart policy.
Note, that we do not claim that the proposed scheduling policy is optimal -our example just shows that the pure restart strategy is not optimal. There should be an optimal combination interleaving restarts on the global level and scheduling on the local level, but finding this combination is left for future research.

Conclusions
In this work we present an algorithm for optimal scheduling of anytime algorithms with shared resources. We first introduce a formal framework for representing and analyzing scheduling strategies. We begin by analyzing the case where the only allowed scheduling operations are suspending and resuming processes. We prove necessary conditions for schedule optimality and present an algorithm for building optimal schedules that is based on those conditions. We then analyze the more general case where the scheduler can increase or decrease the intensity of the scheduled processes. We prove necessary conditions and show that intensity control is only rarely needed. We then 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.
The results show that the optimal strategy indeed outperforms other scheduling strategies. For lognormal distribution, we showed an improvement of more than 50% over the naive sequential strategy. In general, our algorithm is particularly beneficial for heavy-tailed distributions, but even for exponential distribution we show a benefit of more than 35%.
In some cases, however, simple scheduling strategies yield results similar to those obtained by our algorithm. For example, the optimal schedule for uniform distribution is to apply one of the processes with no switch. When the probability to succeed within the given time limit approaches 1, this simple scheduling strategy also becomes close to optimal, at least for unimodal distributions with no strong skew towards zero. On the other hand, when the probability of success approaches zero, another simple strategy that applies the processes simultaneously becomes close to optimal.
Such a behavior meets the intuition. For heavy-tailed distributions, switching between the runs is promising because the chance to be on a bad trajectory is high enough. The same is correct for distributions with low probability of success. However, if the probability to be on a bad trajectory is too high, the best strategy is to switch between the runs as fast as possible, which is equivalent to the simultaneous strategy. On the other hand, if the distribution is too skewed to the right, often there is no sense to switch between the runs, since the new run should pay a high penalty before it reaches the "promising" distribution area. In general, when the user is certain that the particular application falls under one of the categories above, the cost of calculating the optimal schedule can be saved.
The high complexity of computation is one of the potential weaknesses of the presented algorithm. This complexity can be represented as a multiplication of three factors: function minimization, Branch-and-Bound search, and solving Equations (18) and (19) for the case of two agents or Equation (28) for the general case. For two agents, the only exponential component is the Branch-and-Bound search. We found, however, that in practice the branching factor, which is roughly the number of roots of the equations above, is rather small, while the depth of the search tree can be controlled by iterative-deepening strategies. For an arbitrary number of agents, function minimization may also be exponential. In practice, however, it depends on the behavior of the minimized function and the minimization algorithm.
Since the optimal schedule is static and can be applied to a large number of problem instances, its computation is beneficial even when associated with high cost. Moreover, in some applications (such as robotic search) the computational cost can be outweighed by the gain obtained from a single invocation.
The previous work most related to our research is the restart framework (Luby et al., 1993). The most important difference between our algorithm and the restart policy is the ability to handle the cases where the number of runs is limited, or where different algorithms are involved. When only one algorithm is available and the number of runs is infinite, the restart strategy is optimal. However, as we have shown in Section 8, some problems may benefit from the combination of these two approaches.
Our algorithm assumes the availability of the performance profiles of the processes. Such performance profiles can be derived analytically using theoretical models of the processes or empirically from previous experience with solving similar problems. Online learning of performance profiles, which could expand the applicability of the proposed framework, is a subject of ongoing research.
The framework presented here can be used for a wide range of applications. In the introduction we presented three examples. The first example describes two alternative learning algorithms working in parallel. The behavior of such algorithms is usually exponential, and the analysis for such setup is given in Section 6.2. The second example is a CSP problem with two alternative initial configurations, which is analogous to the Latin Square example of Sections 2.2 and 7. The last example includes crawling processes with a limited shared bandwidth. Unlike the first two examples, this setup falls under the framework of intensity control described in Section 5. Similar schemes may be applied for more elaborate setups: • Scheduling a system of n anytime algorithms, where the overall cost of the system is defined as the maximal cost of its components (unlike the analysis in Section 4, this function is not differentiable); • Scheduling with non-zero process switch costs; • Providing dynamic scheduling algorithms able to handle changes in the environment; • Building effective algorithms for the case of several resources of different types, e.g., multiprocessor systems.

A.1 Proof of Lemma 1
The claim of the lemma is as follows: For a system of n processes, the expression for the expected cost (6) can be rewritten as Proof: Splitting the whole integration range [0, ∞) to the intervals [t i−1 k , t i k ] yields the following expression: (56), (57) and (58) gives us (55). Q.E.D.

A.2 Proof of the Chain Theorem for n Processes
The chain theorem claim is as follows: The value for ζ l−1 m+1 may either be ζ l−1 m , or can be computed given the previous 2n − 2 values of ζ using the formula Proof: By Lemma 1, the expression we want to minimize is described by the equation The expression above reaches its optimal values either when dE u dζ j = 0 for j = 1, . . . , n, . . . , or on the border described by (26).
Reaching the optimal values on the border corresponds to the first alternative described in the theorem. Let us now consider a case when the derivative of E u by ζ j is 0.
Each variable ζ j may be presented as ζ mn+l = ζ l m , where 0 ≤ l ≤ n − 1. Let us see which summation terms of (60) ζ l m is participating in.
1. ζ l m may be a lower bound of the integral from (60). This happens when k = m + 1 and i = l. The corresponding term is (1 − F #j (ζ j m )).
2. ζ l m may be an upper bound of the same integral, which happens when k = m and i = l. The corresponding term is (1 − F #j (ζ j m−1 )).
For i = 1 . . . l − 1, this may happen when k = m + 1 and j = l, and the corresponding term is For i = l + 1 . . . n, k = m and j = l + n. The corresponding term is (1 − F i (x))dx.

A.3 Proof of Lemma 2
The claim of the lemma is as follows: The Euler-Lagrange conditions for the minimization problem (33) yield two strong invariants: 1. For processes k 1 and k 2 for which σ k 1 and σ k 2 are not on the border described by (34), the distribution and density functions satisfy 2. If the schedules of all the processes are not on the border described by (34), then either c = 1 or f k (σ k ) = 0 for each k.
We can ignore the case where one of the terms 1 − F j (σ j ) is 0. Indeed, this is possible only if the goal is reached by process j with probability of 1, and in this case no optimization is needed. Therefore, we obtain f k 1 (σ k 1 )(1 − F k 2 (σ k 2 )) = f k 2 (σ k 2 )(1 − F k 1 (σ k 1 )), which is equivalent to (65).
meaning that the set { σ i } provides a solution of at least the same quality as {σ i }. If c = 1, this contradicts to the optimality of the original schedule, and if c = 1, the new schedule will also be optimal. Q.E.D.
We want to construct the functions σ i incrementally. For each time interval [t j , t j+1 ] we define a corresponding point t j and a set of functions σ i , such that E u j ( σ 1 , . . . , σ n ) = (1 − F l ( σ l ))dt = E u j (σ 1 , . . . σ n ).
Let us denote σ ij = σ i (t j ) and σ ij = σ i (t j ). At the beginning, σ i0 = 0 for each i, and t 0 = 0. Assume now that we have t j ′ defined for j ′ < j, and σ i (t) defined on each interval [ t j ′ , t j ′ +1 ]. Let us show how to define t j and σ j on [ t j , t j+1 ].
Let t j+1 = t j + k(t j+1 − t j ), and let us define σ i (t) on the segment [ t j , t j+1 ] as follows: In this case, on this segment n l=1 σ i ′ (t) = 1, which means that the σ i satisfy the resource sharing constraints. By definition, and therefore for processes active on [t j , t j+1 ] we obtain