Constraint satisfaction and propositional satisfiability problems are often solved using backtracking search. Pre- vious studies have shown that portfolios of backtracking algorithms--a selection of one or more algorithms plus a schedule for executing the algorithms--can dramatically improve performance on some instances. In this paper, we consider a setting that often arises in practice where the in- stances to be solved arise over time, the instances all belong to some class of problem instances, and a limit or deadline is placed on the computational resources that the backtrack- ing algorithm can consume in solving any instance. For such a scenario, we present a simple scheme for learning a good portfolio of backtracking algorithms from a small sample of instances. We demonstrate the effectiveness of our approach through an extensive empirical evaluation on a real-world instruction scheduling testbed.