The extraboard operator scheduling and work assignment problem

Abstract

An instance of the operational fixed job scheduling problem arises when open work caused by unplanned events such as bus breakdowns, inclement weather, and driver (operator) absenteeism need to be covered by reserve (extraboard) drivers. Each work-piece, which is referred to as a job, requires one operator who must work continuously between specified start and end times to complete the job. Each extraboard operator may be assigned up to w hours of work, which may not to be continuous so long as the total work time is within a s-hour time window of that operator’s shift start time. Parameters w and s are called allowable work-time and spread-time, respectively. The objective is to choose operators’ shift start times and work assignments, while honoring work-time and spread-time constraints, such that the amount of work covered as part of regular duties is maximized. This paper argues that the extraboard operator scheduling problem is NP-hard and three heuristic approaches are presented for the solution of such problems. These include a decomposition-based algorithm whose worst-case performance ratio is proved to lie in [1 − 1/e, 19/27], where e ≈ 2:718 is the base of the natural logarithm. Numerical experiments are presented that use data from a large transit agency, which show that the average performance of the decomposition algorithm is good when applied to real-world data.

Keywords:

• Operational fixed job scheduling problem
• work-time and spread-time constraints
• decomposition algorithm
• approximation ratio

Additional information

Notes on contributors

Fei Li

Fei Li is a Ph.D. candidate in the Industrial & System Engineering Department of the University of Minnesota. His research focuses on algorithms for solving combinatorial optimization problems.

Diwakar Gupta

Diwakar Gupta is a Professor of Industrial & Systems Engineering at the University of Minnesota. He also holds a courtesy appointment as an affiliate senior member in the Health Services Research, Policy, and Administration Division of the School of Public Health. He earned a Ph.D. in Management Sciences from the University of Waterloo. His research focuses on healthcare delivery systems, state transportation agencies’ operations, and supply chain and revenue management. His research has been funded by a variety of federal and state agencies (e.g., DHHS, NSF, AHRQ, VHA, Mn/DOT, NSERC, SSHRC, and CHSRF), as well as companies, and his papers have appeared in all major journals in the field of Operations Research/Management. He was elected in 2011 and 2013 to be the chair of the Healthcare Operations Management Special Interest Group of the Manufacturing and Service Operations Management Society. More information about his research projects can be found by visiting the web page of his research lab, Supply Chain and Operations Research Laboratory, at http://www.isye.umn.edu/labs/scorlab.