= Algorithm portfolio schedule
An \b[algorithm portfolio schedule] specifies how computational resources are assigned to members of an <algorithm portfolio> over time. For a <sequential algorithm portfolio>, it states which <algorithm> receives each time interval, whether interrupted work is resumed or discarded, and when computation stops. A <parallel algorithm portfolio> also needs a processor allocation and a rule for accepting and combining results. Listing candidate <algorithms> alone does not specify a schedule.
An original interleaving example makes the distinction between processor time and elapsed time explicit. Suppose <algorithms> A and B need respectively $3$ and $5$ seconds of processor time on a particular input. Give A one second, then B one second, repeating while preserving both states and stopping at the first accepted result. A receives its third second during elapsed interval $[4,5]$, so the portfolio finishes at $5$ seconds. At that point A has used $3$ processor-seconds and B has used $2$. With two dedicated processors, the corresponding <parallel algorithm portfolio> would finish at $3$ seconds. These calculations assume no <algorithm portfolio switching overhead> and no resource contention.
More generally, let $s_i(t)$ be processor time supplied to candidate $i$ by elapsed time $t$, and let $T_i$ be its required processor time. In the resumable, interference-free model, the completion time is
$$
C=\inf\{t:\text{some }i\text{ has }s_i(t)\ge T_i\}.
$$
Discarding a state on every interruption changes this model: separate short runs do not necessarily accumulate into one longer run. The original portfolio study compared parallel, interleaved and restart execution precisely because these are different policies.<Algorithm portfolios by Carla P. Gomes and Bart Selman>[Sections 4–5: allocation policies and empirical runtime profiles.]{ref}
Choose an objective before comparing <algorithm portfolio schedules>: <expected value> of <running time>, probability of finishing by a deadline, and total computing work need not favor the same allocation. A schedule chosen using retrospective runtimes also requires evaluation on inputs that did not determine the schedule.
Back to article page
