Reserve driver scheduling

Transit agencies use reserve drivers to cover open work that arises from planned and unplanned time off, equipment breakdowns, weather, and special events. Work assignment decisions must be made sequentially without information about future job requests, a driver’s earlier assignment may not be interrupted to accommodate a new job (no pre-emption), and the scheduler may need to select a particular driver when multiple drivers can perform a job. Motivated by this instance of the interval scheduling problem, we propose a randomized algorithm that carries a performance guarantee relative to the best offline solution and simultaneously performs better than any deterministic algorithm. A key objective of this article is to develop an algorithm that performs well in both average and worst-case scenarios. For this reason, our approach includes discretionary parameters that allow the user to achieve a balance between a myopic approach (accept all jobs that can be scheduled) and a strategic approach (consider accepting only if jobs are longer than a certain threshold). We test our algorithm on data from a large transit agency and show that it performs well relative to the commonly used myopic approach. Although this article is motivated by a transit industry application, the approach we develop is applicable in a whole host of applications involving on-demand-processing of jobs. Supplementary materials are available for this article. Go to the publisher’s online edition of IIE Transactions for datasets, additional tables, detailed proofs, etc.