Algorithm portfolio schedule

An 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 isDiscarding 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.^[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.