Interruptible Algorithms for Multi-Problem Solving

1 Introduction

A designer of real-time systems should anticipate the situation in which there are limitations on the available execution time. Applications such as medical diagnosis systems, automated trading systems and game-playing programs require that the system may be queried at any time during its execution, at which point a solution must be reported. Anytime algorithms occur precisely in such settings, namely when a computationally difficult problem is addressed under uncertain running time availability. Such algorithms will produce an output whose quality improves as a function of the available computation time. Anytime algorithms were introduced by [Horvitz, 1987; 1988] and [Dean and Boddy, 1988] and arise in central AI problems such as heuristic search, and planning under uncertainty.

[Russell and Zilberstein, 1991] distinguish between two main classes of anytime algorithms. On one hand, the class of interruptible algorithms consists of algorithms that can be interrupted at any point during their execution, and can always report their current (albeit not necessarily optimal) solution. On the other hand, the class of contract algorithms consists of algorithms which specify the exact amount of allowable

Alejandro L´opez-Ortiz

Cheriton School of Computer Science University of Waterloo Waterloo, Canada alopez-o@uwaterloo.ca

computation time as part of their input. Such algorithms must terminate their execution before a meaningful solution can be produced. Interruptible algorithms offer more flexibility; in contrast, contract algorithms are typically much easier to design, implement and maintain.

A "black-box" method for converting any contract algorithm to its interruptible version consists of running a sequence of executions of the contract algorithm, of increasing execution times. More precisely, in the most general setting, we are presented with a set P of n problem instances which we want to solve, and a system of m identical processors on which we can schedule this sequence of contract algorithms. The goal is to devise an efficient schedule, that is a strategy that assigns each execution of a contract algorithm to a specific processor. In the standard setting, upon an interruption, a query for a problem in P is issued. The algorithmmust then report the solution of the (completed) contract algorithmwith the longest execution time for the queried problem. Naturally, these "lengths" or durations of completed contracts should be as large as possible, since the longer the execution time, the better the quality of the solution returned by the contract algorithm (and thus by the interruptible system as well).

The standard performance measure for a schedule of contract algorithms is the acceleration ratio. Informally, the measure describes the multiplicative increase in processor speed required for the schedule to compensate for the lack of knowledge of the interruption time. More formally, let lp,t denote the length of the largest contract for problem p completed by time t in the schedule. The acceleration ratio is then defined as supt maxp∈P t lp,t . This measure compares the quality of the solution returned by the schedule (that is, the quantity lp,t) to an ideal, optimal algorithm that knows the interruption t in advance and dedicates a single processor in order to run a contract of length t for problem p.

Simulating interruptible algorithms by means of schedules of contract algorithms has been a topic of extensive study. [Russell and Zilberstein, 1991] were the first to present such an explicit simulation. For the case of one problem instance and a single processor, they provided a schedule based on iterative doubling of contract lengths for which the corresponding interruptible algorithm has acceleration ratio at most four. [Zilberstein et al., 1999] showed that in this case the schedule is optimal, in the sense that no other schedule of better acceleration ratio exists.

[Zilberstein et al., 1999] addressed the generalization of multiple problem instances (assuming a single available processor), and [Bernstein et al., 2002] studied the generalization in which contracts for a single problem instance must be scheduled on a set of multiple processors. For both cases, optimal schedules are derived. [Bernstein et al., 2003] addressed the problem in its full generality, namely the setting in which n problem instances are given and the schedule is implemented on m processors. In particular, they showed an upper bound of nm ( m+n n ) m+n m on the acceleration ratio; in addition, they showed that the schedule is optimal for the class of cyclic schedules. The latter is a somewhat restricted, but still very rich and intuitive class of schedules. This restriction was removed by [L´opez-Ortiz et al., 2006], who showed that this acceleration ratio is indeed optimal among all possible schedules. More recently, Angelopoulos et al. [Angelopoulos et al., 2008] studied the setting in which interruptions are soft deadlines (instead of absolute ones), in the sense that the algorithm is allowed an additional window of time. Within this window, the algorithm may have the opportunity to complete the execution of a contract, or inititate a new one.

The central observation that motivates our work is that the acceleration ratio becomes problematic, as a performance measure, when at interruption time the algorithm is required to return a solution to all n problems in P instead of only to a specific queried problem. This arises, for instance, in systems that involve parallel executions of different heuristics (and at interruption time, the best heuristic is chosen). A similar setting has been considered in the context of portfolios of algorithms: see, e.g., the work of [Gomes and Selman, 2001]. Another example is a medical diagnostic system which must perform concurrent evaluations for a number of medical issues. Here, the decision of the expert may very well have to take into account all such evaluations.

In particular, suppose that n > m, and for the purposes of illustrating our argument, say that n ≫m. Note that it is not feasible for any ideal, optimal algorithm (that is, an algorithm with advance knowledge of the interruption time t) to schedule n contracts of length t to m processors, since n > m. In a sense, if we applied the acceleration ratio to this domain, we would compare the performance of an interruptible algorithm which is expected to make progress on all n problems to an algorithm which only makes optimal progress on at most m: such a comparison is simply not fair. This shortcoming was noticed by [Zilberstein et al., 2003], who defined the acceleration ratio for the case of n problems and one processor as supt maxp∈P t/n lp,t . This measure describes then an even distribution of the processor time among the n problem instances for the optimal (offline) schedule.

In this paper we address the problem of designing interruptible algorithms using schedules of executions of contract algorithms, assuming that m identical processors are available, and n problem instances, all equally significant must be solved. We begin by considering measures alternative to the acceleration ratio (Section 2), and we propose the deficiency of a schedule as our measure of choice. In Section 3 we present a schedule whose deficiency is very small and rapidly decreasing in the ratio n/m (in contrast, the acceleration ratio of every schedule is known to approach infinity when n/m → ∞). Moreover, for the case of a single processor (m = 1), we prove in Section 4 that our schedule is optimal.

Due to space limitations, throughout the paper we omit (or only sketch) certain technical proofs.

2 Problem formulation and comparison of measures

Consider an (infinite) schedule X of executions of contract algorithms (also called contracts). For an interruption time t we denote by l(X, p, t) the length of the longest contract for problem p ∈ P which is finished by time t in X (or simply lp,t when X is implied from context). We make the canonical assumption that at interruption time at least one contract per problem has already completed its execution.

We need to formalize the question: what is the best way to exploit the available resources (i.e., processors), in order to solve the set of problems P? Towards this end, consider a schedule Y , which, in contrast to X, is finite: more precisely, Y schedules n distinct contracts, one for each problem in P (if Y schedules more than one contract per problem, than we can transform Y to a schedule Y ′ which is at least as good as Y by keeping only the largest contract per problem that appears in Y ). Each contract in Y is scheduled in one of the m processors in M. We require that Y is feasible with respect to t, in the sense that the makespan of Y , namely the total sum of contract lengths on the most loaded processor used by Y does not exceed t. Let Yt denote the class of all schedules Y with the above properties. We will be calling Y an offline solution since it relies on advance knowledge of t.

Having defined Yt, we need a measure of how a schedule Y ∈ Yt compares to X, which will also dictate which is the best schedule in Yt compared to X. First observe that the acceleration ratio is not an appropriate measure for our setting, since under it the optimal offline schedule Y for interruption t dedicates all its resources to the contract that is worked on the least by X while failing to produce an answer for all other problems. This results in a large acceleration ratio which however does not truly reflect the quality of X (effectively, the optimal solution "cheats" by ignoring all but one problem instances, which is not acceptable in our setting).

Another alternative would be to compare the smallest contract completed by X to the smallest contract completed by Y , by time t. We will need some preliminary definitions first. Let StX denote the set {l(X, pi, t)|i ∈ [1, . . . , n]}, and let StX (i) denote the i-th smallest element of StX . Similarly, for Y ∈ Yt let StY denote the set of n contracts in Y , and StY (i) be the i-th smallest contract in Y , respectively (ties are resolved arbitrarily).

Formally, we define the performance ratio of X with respect to Y at time t as:

The performance ratio of X at time t is then defined as perf(X, t) = maxY perf(X, Y, t) where Y is a feasible schedule. Lastly, the performance ratio of X is then defined as perf(X) = supt perf(X, t).

The first observation is that under this measure there exists an "optimal" offline schedule in which all contracts have the same length: here, by "optimal" we mean a schedule Y ∈ Yt against which the performance ratio of X is maximized. Indeed given any offline schedule Y , consider any schedule Y ′ such that the length of all its contracts is mini StY (i). Note that such a feasible Y ′ exists, since all contracts in Y are at least that long, and Y itself is feasible. Then it follows from the definition that perf(X, Y, t) = perf(X, Y ′ , t). We can show a close relationship of the performance ratio to the acceleration ratio for the standard setting (namely when we seek the solution only to the queried problem).

Lemma 1. There is a schedule X such that for any arbitrary interruption time t

Furthermore, X is optimal with respect to this measure.

Proof. Consider first the case m ≥ n, then an optimal offline schedule consists of executing one contract of length t per problem, each on its own processor and hence perf(X, t) = t mini SX(i) . Note then that perf(X) = supt perf(X, t) is precisely the definition of the acceleration ratio, for which the results of Bernstein et al. and L´opez-Ortiz et al. show the optimal value of nm ( m+n n ) m+n n .

On the other hand, if m < n then every offline schedule Y is such that there exists at least one processor in which at least ⌈n/m⌉ contracts are scheduled. As argued earlier, there exists an optimal offline schedule in which all contracts have the same length. It follows then that there is an optimal offline schedule with contract lengths equal to t/⌈n/m⌉. Therefore, perf(X, t) = t/⌈n/m⌉ mini SX(i) and perf(X) = supt perf(X, t) can then be described as 1 ⌈n/m⌉ times the expression of the acceleration ratio, and the lemma follows. Note that for the case of one processor and n problems, this matches the measure proposed by [Zilberstein et al., 2003], as mentioned in the introduction.

Interestingly, we can show that under this refined measure, the schedule in the proof of Lemma 1 is very efficient.

Lemma 2. The performance ratio of the schedule of Lemma 1 is bounded by 2e, if n > m, and by 4 , if n ≤ m.

Proof. In the case m≥ n, we have

In the case m < n we have that

In either case, perf(X) ≤ 2e.

Figure 1 shows a plot of perf(X) for n > m assuming for simplicity that m divides n. Note how the performance of the schedule is between 4 and e, and decreases rapidly as n/m increases. When m ≥ n, perf(X) decreases in a similar manner, as m/n increases, and takes values between 4 and 1.

While the performance ratio seems a better candidate for a measure in the context of our problem, it is far from being the best possible choice. Note that according to this measure, every contract in the optimal offline solution may have fixed length, namely t/⌈n/m⌉. While it is guaranteed that the smallest contract in StX indeed does not exceed t/⌈n/m⌉, the solution produced by X may be such that there exist several contracts in StX which exceed this length. More formally, there may exist j such that StX (j) > StY (j) for the optimal offline solution Y . It then becomes difficult to argue that the optimal offline solution Y at time t is indeed better than the solution produced by the interruptible algorithm at time t, even though, supposedly, Y is optimal!

The above illustrates the need for defining a further measure, one which takes into account the intuitive expectation that "the optimal offline solution should perform better than the interruptible algorithm on each problem". To accomplish this, we allow the offline solution to observe the behavior of X at each point in time t, and then produce an appropriate "optimal" offline solution, tailored to the specifications of our problem. In a sense we allow the offline solution vast powers for choosing its schedule, while at the same time we still require it to produce solutions to all problem instances. This yields a measure which we call deficiency, and which is: i) consistent with the requirements of the problem; and ii) powerful enough, in the sense that if an algorithm performs well with respect to the new measure, then there are very strict guarantees about its performance.

Formally, we say that Y is at least as good as X, denoted by Y ≥ X, if and only if StY (i) ≥ StX (i), for all i ∈ [1, n].

Then for a schedule Y ∈ Yt with Y ≥ X, we say that the deficiency of X wrt Y for interruption t is defined as

The deficiency of X given t is then defined as

We define the deficiency of X simply as

Not surprisingly, one can draw a connection between the problem of minimizing the deficiency of a schedule, and the problem of makespan minimization. In the latter, given m identical processors and n jobs j1, . . . , jn, each of a certain size (length), the objective is to assign each job to a processor such that the maximum load among all processors, is minimized. The following lemma establishes this relation.

Lemma 3. def(X, t) = t OPT(StX ) , where OPT(StX ) is the minimum makespan for scheduling n jobs in m processors, with job i having size (length) equal to StX (i).

For an informal interpretation of the lemma, consider the set of the n largest contract lengths (one per problem), completed by X at time t. Then the largest d > 1 such that if we multiply each of the n contract lengths by d, there exists a schedule of the "blown-up" contracts in m processors that has makespan at most t, is the deficiency of X given t.

3 A near-optimal schedule for general m

In this section we propose an exponential schedule of very small deficiency. The overall schedule is as follows. Let b > 1 be a real number,

• problems are assigned to processors in a cyclic, roundrobin order, i.e. the ith time a processor j ∈ {0, . . .m1} executes a contract it does so on problem (im + j) mod n and for a length of time bim+j .
• the sequence of contract lengths is {bi }i=0,1,2,...,
• the length of the k-th contract in this round-robin sequence is bk for some b > 1.
• the value b is the base of the schedule,

The remainder of this section is devoted on finding the best value of b, i.e., the value that minimizes the deficiency of the exponential schedule. We denote by Gk the finish time of the k-th contract of X, in the cyclic order, whereas Lk = bk denotes the length of the k-th contract.

The following lemma shows that it suffices to evaluate the deficiency of any schedule (not necessarily exponential) at interruption times right before a contract terminates. Let G-c denote a time infinitesimally smaller than the finish time Gc of contract c ∈ X. Recall also that OPT({·}) denotes the optimal makespan for a schedule of a given set of jobs in m processors.

In the context of an exponential schedule it is easy to see that Lemma 4 becomes

where Li = bi is the length of the i-th contract in the cyclic order.

The next lemma gives a lower bound on the optimal makespan, which will be useful in deriving an upper bound for the deficiency, as given by (5).

Proof. We will evaluate the makespan of the wellknown greedy algorithm which schedules jobs of sizes Lk, . . .Ln+k-1, in m identical processors numbered 0, . . .m- 1, assuming the jobs are considered in this particular order (i.e., in increasing order of size). More precisely, the algorithm will assign each job to the machine of least current load. It is easy to see that the decisions of the greedy algorithm are such that the job of size Lk+i is scheduled on processor i mod m. Moreover, the incurred makespan is determined by the total load of jobs scheduled on the same processor as job Ln+k-1, namely processor (n-1) mod m. Denote by Gr(Lk, . . . Ln+k-1) the makespan of the greedy algorithm. We obtain

To complete the proof, we need to argue that the greedy scheduling policy does not achieve a makespan worse that (1/κ) times the optimal makespan. Graham's fundamental theorem on the performance of the greedy scheduling policy [Graham, 1966] states that the greedy algorithm has an approximation ratio of 2-1/m. Moreover, we know that the optimal makespan is at least bn+k-1 , which in conjunction with (6) yields that the greedy algorithm is also a bm/(bm -1) approximation (for our specific instance). The lemma follows by combining the above two approximation guarantees.

We now proceed to bound the deficiency of the exponential schedule X. It is easy to show that for exponential schedules, Gn+k = bk+n+m-b(k+n) mod m bm-1 . Let λ = 1/κ = min {2 - 1m , bm bm-1 }. Combining with (5) and Lemma 5 we obtain

where γ is defined as (n - 1) mod m.

We thus seek the value of b that minimizes the RHS of (7). It is not clear how to do this analytically, since the factor λ depends on b, and the derivative of the RHS does not have roots that can be identified analytically. Instead, let f(b) denote the function bn+m/(bn+m-1 - bγ ). Is is easy to show that f(b) is minimized for a value of b equal to β = (n + m - γ) 1 n+m+γ-1 . Let ρ be such that n - 1 = ρm + γ, then β = (m(ρ + 1) + 1) 1 m(ρ+1) . Observe also that f (b) = 1/(b-1 - bγ-n-m) = 1/(b-1 -b-m(ρ+1)-1 ). Summarizing, for b = β we obtain a schedule of deficiency

Figure 2 shows a plot of the deficiency of the schedule (or, more accurately, the RHS of (8) for the interesting case where n > m) as function of m and ρ. Note that for fixed m, the deficiency increases as a function of n, until a point at which it becomes relatively stable with n (this can be explained by the factor λ that is the minimum of two functions, one of which does not depend on n). For large m, and even larger n, the deficiency is close to 2. From the plot, the maximum value of deficiency is 3/8 · 55/4 ∼ 2.803.

We will now provide an analytical bound on the maximum value of the deficiency, by showing that def(X) is at most 3.74 when n > m and at most 4 when n ≤ m. Substituting m(ρ + 1) with y in (8) we obtain

Using standard calculus it is straightforward to show that the functions (y + 1)-1/y and (y + 1)- y+1 y are increasing and decreasing functions of y, respectively. Therefore, the denominator of the RHS of (9) is an increasing function of y = m(ρ + 1). It turns out that for n > m this upper bound on def(X) is maximized when m = 2 and ρ = 1, hence def(X) ≤ 3.74. When n ≤ m, the (2 - 1/m) factor vanishes, since the greedy schedule achieves optimal makespan (in other words, λ = 1). In this case def(X) is at most 4. These upper bounds are not tight as the figure below shows. The plot shows tight numerical bounds for the plotted ranges of n and m. The analytical method in contrast gives an exact but not tight upper bound for all n and m. The two results differ slightly because the true exact maximum of the function could not be found analytically.

Note that the strategy proposed in this work outperforms known strategies proposed for other settings. For example, the optimal schedule for the acceleration ratio of [Bernstein et al., 2003; L´opez-Ortiz et al., 2006] has unbounded deficiency for m ≫ n. When n > m, this schedule has constant deficiency, but larger than ours (4.24 in the worst case). Moreover, it is provably non-optimal for m = 1 as it does not achieve the bounds of Theorem 9 in Section 4. For a single problem and processor, Eq. (7) becomes def(X) ≤ b2 /(b - 1), which equals the acceleration ratio of exponential schedules with base b, as expected.

4 Optimality for the case of a single processor

In this section we show that the exponential schedule we described in Section 3 is optimal for the case of a single processor. Denote by X any given schedule of contracts on a single processor. For a fixed problem p ∈ P, we will denote by lower-case d and upper case D the lengths of consecutively completed contracts for problem p in X, respectively. More formally, if (pi, di) is a contract in X, then the next contract for pi scheduled after (pi, di) will be denoted by (pi,Di).

We begin the proof by introducing some "normalization" in the schedules. In particular, the following technical lemma demonstrates that any schedule (hence the optimal schedule as well) can be transformed to a schedule of no worse deficiency, which also observes certain useful properties. Ideally, we would like the resulting schedule to have as simple a structure as a cyclic (or even better, an exponential) schedule, because the analysis would then become very easy. However, this not possible in general. Instead, we derive schedules which although not as "canonical" as cyclic schedules, are much more amenable to analysis than the original schedule ( which may observe no properties at all). We call the resulting schedules normalized. Similar normalization reductions have been applied in [L´opez-Ortiz et al., 2006] and [Angelopoulos et al., 2008].

Lemma 6. For every schedule of contracts X in a single processor, there exists a schedule X′ such that def(X′ ) ≤ def(X), and furthermore X′ satisfies the following properties: Let (pi, di) and (pj , dj ) denote two contracts in X′ , with i ̸= j. Let also Ti and Tj denote the start times of contracts (pi,Di) and (pj,Dj) in X′ . Then

• (i) If di < dj then Ti +Di < Tj +Dj, which also implies that Ti < Tj .
• (ii) If di < dj then Di <Dj.

Proof sketch. If X is not normalized, then we can transform it to a normalized one by defining an appropriate series of contract swaps, similar to the ones of [L´opez-Ortiz et al., 2006]. These swaps introduce the normalized proprties and do not worsen the deficincy of the original schedule. ✷

In the next step, we establish a lower bound on the deficiency of any schedule, as a function of contract lengths.

Lemma 7. For any normalized schedule X for n problems on a single processor, we have

where Xs = (xs0 , xs1 , . . .) is the sequence of contract lengths in X, in increasing order, and xsi := 0 if i < 0.

Proof. Suppose that at time T0, a contract C0 for problem p0 ∈ P is about to start in X; let D0 denote the length of this contract. Denote by Cj , with j ∈ [1, n-1], the latest contract for problem pj , which completes before time T0 in X, and by Dj its corresponding length.

Note that the lengths of contracts which are completed by time T0 + D0 in X are elements in the sequence Xs . In particular, it must be that d0 = xsk for some k > 0. Let I denote the set of indices in Xs of these lengths. We can then say that def(X) (for an interruption right before T0 +D0) is

We will proceed by lower-bounding the numerator and upperbounding the denominator of (11). First, observe that the numerator contains as summands all xsi which have been completed by time T0 + D0. Lemma 6 implies then that every contract smaller than d0 = xsk has been scheduled by time T0 +D0, and appears as a summand in the numerator. The same lemma guarantees also that for all j ∈ [1, n-1], Dj cannot be smaller than d0, otherwise the next contract for problem j to complete after Dj would also complete before time T0 +D0, which would contradict the definition of Dj as the earliest contract for problem j to finish before time T0 +D0. Hence we conclude that the numerator contains all contract lengths smaller than xsk , as well as at least n - 1 contract lengths (one for each j ∈ [1, n-1]) larger than xsk , and, last, contains a contract length equal to D0 > d0. The smallest values the latter n lengths can attain are then xsk+1 , . . . xsk+n . We thus obtain that ∑i∈I xsi ≥ ∑k+n i=0 xsi .

We will now upper bound the denominator of (11). By definition of T0, for every j ̸= 0, we have Tj +Dj ≤ T0 +D0. Hence Lemma 6 implies that dj < d0, and also Dj < D0. We also know (as argued earlier) that Dj > d0. Let l > k be an index such that D0 = xsl > xsk = d0. We will argue that for every j ∈ [1, n-1], there is at most one contract for problem j of length equal to xsi , for i ∈ (k, l). Indeed, if this was not the case, then for problem j there would exist two consecutive contracts (relative to problem j) of lengths greater than d0 and smaller than D0, which contradicts Lemma 6. We conclude that the largest values D1, . . .Dn-1 can attain are xsk+1 , . . . xsk+n-1 , hence d0 + ∑n-1 i=1 Di ≤ ∑n-1 i=0 xsk+i .

The lemma follows from the above bounds on the numerator and the denominator of (11).

As a last main step in the proof, we will apply the following result due to [Gal, 1980] and [Schuierer, 2001], which provides a lower bound for the supremum of a sequence of functionals. This result will help us relate the deficincy of normalized schedules to the deficiency of exponential ones. Define Ga = (1, a, a2 , . . .) to be the geometric sequence in a and X+i = (xi, xi+1, . . .) the suffix of sequence X starting at xi.

Theorem 8 ([Schuierer, 2001],[Gal, 1980]). Let X = (x0, x1, . . .) be a sequence of positive numbers, r an integer, and a = limn→∞(xn)1/n , for a ∈ R ∪ {+∞}. If Fk, k ≥ 0, is a sequence of functionals which satisfy

1. Fk(X) only depends on x0, x1, . . . , xk+r,
2. Fk(X) is continuous, for all xi > 0, with 0 ≤ i ≤ k+r,
3. Fk(αX) = Fk(X), for all α > 0,
4. Fk(X +Y ) ≤max(Fk(X), Fk(Y )), and

5. Fk+i(X) ≥ Fk(X+i ), for all i ≥ 1,

then

Define now Fk(Xs ) := k+n ∑ i=0 xsi / n-1 ∑ i=0 xsk+i . It is easy to show that Fk satisfies the conditions of Lemma 8. Therefore,

Note that if a ≤ 1, then the above ratio tends to infinity as k → ∞. Hence, we can assume that a > 1 and obtain

Recall that from (7), the deficiency of the exponential schedule of Section 3 is bounded by bn+1 /(bn - 1), for a value of b that minimizes this ratio, namely b = (n + 1) 1n . Comparing this expression to the lower bound of (12), we deduce that the exponential schedule is indeed optimal.

Theorem 9. For a single processor, the optimal deficiency is (n+1) n+1 n n , and is achieved by the exponential schedule.

5 Conclusion

In this paper we addressed the problem of devising interruptible algorithms in a setting in which solutions to all problem instances are required and all problems are equally important. Even though our proposed solutions are efficient, it would be nevertheless interesting to know whether our schedule is optimal for any number of processors. This appears to be a complicated task: for general m, minimizing makespan is NP-hard. More importantly, the known efficient makespanscheduling algorithms do not yield a closed-form expression of the makespan as a function of the sizes of jobs (Graham's greedy algorithm is an exception to this, but it is no better than a 2-approximation).

Another direction for further research is to consider the generalization in which at interruption time a subset of i ≤ n problems are queried for their solution. We are also interested in a related setting in the context of robot searching in multiple concurrent rays. [Bernstein et al., 2003] showed important connections between this problem and contract scheduling under the acceleration ratio. Suppose, however, that instead of a single target, i targets are located, at unknown positions from the common origin. We have m robots available to explore the rays. What is the best strategy for the robots so as to locate all targets? There are interesting parallels between the two problems, e.g., the optimal solution in the multi-target variant can be formulated as a makespan scheduling problem, with job sizes a function of the distances of the targets from the origin. We believe the results of this paper can be useful in addressing this problem.