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 drivers 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 publishers online edition of IIE Transactions for datasets, additional tables, detailed proofs, etc.
|Original language||English (US)|
|Number of pages||12|
|Journal||IIE Transactions (Institute of Industrial Engineers)|
|State||Published - Mar 3 2016|
Bibliographical noteFunding Information:
The authors are grateful to the IIE Transactions? review team and Departmental Editor Professor Sanjay Mehrotra for helping us improve the manuscript. This material is based upon work supported in part by the National Science Foundation under grant no. CMMI-1332680. Furthermore, this material is also based upon work completed, in part, while Diwakar Gupta was on detail at the National Science Foundation under the terms of an Intergovernmental Personnel Assignment, Award no.CMMI-1452877. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
- Competitive ratio
- Fixed job scheduling
- Online algorithms
- Reserve driver scheduling