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. © 2014
|Original language||English (US)|
|Number of pages||15|
|Journal||IIE Transactions (Institute of Industrial Engineers)|
|State||Published - Nov 2 2014|
Bibliographical noteFunding Information:
This material is based upon work supported in part by grants from the Center for Urban and Regional Affairs’ Faculty Interactive Research Program, the Center for Transportation Studies, and the National Science Foundation under grant no. CMMI-1332680.
The above assumptions were supported by data from the collaborating transit agency. For example, 1 minute was the smallest unit of time and jobs whose lengths exceeded the work-time limit of 8 hours were assigned first to those operators who were willing to accept overtime. Assignment of such jobs thus occurred independently of the extra-board operator scheduling and work assignment problem addressed in this paper.
- Operational fixed job scheduling problem
- approximation ratio
- decomposition algorithm
- work-time and spread-time constraints