Reserve Driver Online Scheduling

Project summary:

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-empion), 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, this project aims to develop 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 is to develop an algorithm that performs well in both average and worst-case scenarios. For this reason, this approach includes discretionary parameters, which allow the user to achieve a balance between a myopic approach (accept all jobs that can be scheduled) and a strategic approach (consider accepting jobs only if jobs are longer than a certain threshold). The algorithm will be tested on data from a large transit agency to show that it performs well relative to the commonly used myopic approach. Although this project is motivated by a transit industry application, the approach developed will be applicable to a host of applications involving on-demand-processing of jobs.