Automated Manpower Rostering: Techniques and Experience

C.m. Khoong, Hoong Chuin Lau, L.w. ChewInternational Transactions in Operational Research 1994 · DOI

TL;DR

This paper introduces ROMAN, a comprehensive and flexible toolkit for automating manpower rostering in service organizations. It integrates various techniques from AI and operations research to handle a wide spectrum of work policies, offering a significant improvement over manual or less generalized rostering systems.

What Problem Does This Paper Address?

Manpower rostering, the process of scheduling employees to meet operational demands, is a critical and often complex task, especially in service industries requiring 24/7 coverage. Manually generating rosters is time-consuming, prone to errors, and often results in suboptimal schedules that dissatisfy both management and employees. Existing automated systems often focus on specific domains (e.g., nurses, bus drivers) or a limited set of constraints, lacking the generality and flexibility needed for diverse service organizations. This paper addresses the need for a comprehensive, generic toolkit that can handle a wide array of work policies and organizational structures.

Methods

The ROMAN toolkit integrates techniques from artificial intelligence, operations research, and software engineering. It supports two primary design modes:

  • Cyclic Rostering: A set of master shift patterns is rotated across employees over time. This mode is easier to manage and more stable.
  • Individualized Rostering: Each employee receives a unique shift pattern, allowing for greater adaptation to individual preferences and fluctuating demand.

The rostering process is decomposed into three core stages:

  1. Shift Allocation: Determines the required staffing levels for each shift each day based on temporal demand. This is modeled as a set covering problem, solved using a greedy heuristic.
  2. Offday Scheduling: Generates offday assignments, considering staffing demands, work/offstretch constraints, and employee preferences. This involves branch-and-bound algorithms and iterative improvement for cyclic rosters, and a two-stage approach (greedy for weekends, backtracking for weekdays) for individualized rosters.
  3. Workshift Scheduling: Assigns specific workshifts to fulfill staffing requirements, respecting shift change constraints and offday assignments. Cyclic scheduling uses a heuristic followed by a branch-and-bound algorithm, while individualized scheduling employs weighted bipartite graph matching (Hungarian method).

ROMAN also features a Work Policy Manager for defining organizational rules and constraints using an English-like specification language, and a Data Manager for handling employee and demand data.

Datasets

Not discussed in the paper. The paper focuses on the toolkit's design and implementation rather than specific empirical evaluations on public datasets.

Key Insights and Ideas

  • Generality is Key: The paper emphasizes that a truly useful automated rostering system must be generic enough to handle a wide spectrum of work policies and organizational structures, moving beyond domain-specific solutions.
  • Integration of AI and OR: ROMAN successfully combines techniques from both artificial intelligence (heuristics, search) and operations research (optimization, mathematical programming) to achieve robustness and efficiency.
  • Flexibility through Design Modes: Offering both cyclic and individualized rostering modes provides users with options to balance ease of management with employee preferences and demand responsiveness.
  • Interactive "What-If" Analysis: The toolkit's design supports interactive optimization, allowing users to explore the impact of changing policies, constraints, or demand levels, which is crucial for practical decision-making.
  • Importance of User Interface and Specification Language: A simple yet powerful specification language and an intuitive command language are vital for user adoption and integration into existing systems.

Key Results

The paper highlights the successful development and licensing of the ROMAN toolkit to major service organizations in Singapore's health care and transportation sectors. While specific quantitative results are not detailed, the toolkit is described as highly flexible, robust, and efficient, capable of generating rosters for approximately 50 employees and 10 shift types in a few seconds on a workstation. The authors claim it handles a more comprehensive set of constraints than previously reported systems.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that some subjective criteria, particularly related to employee welfare, might be difficult to fully automate and suggests that interactive computation can help bridge this gap.
  • While the toolkit is efficient, for very large problem sizes, users can trade off optimality for computational speed.
  • Future Work:
    • The authors envision extending ROMAN to encompass long-term manpower planning and daily task deployment functions, aiming for a generalized, integrated system for the entire manpower management lifecycle.
  • Further development of sophisticated user interfaces is suggested.

Summary updated

Abstract

We present ROMAN , a comprehensive, generic manpower rostering toolkit that successfully handles a wide spectrum of work policies found in service organizations. We review the use of various techniques and methodologies in the toolkit that contribute to its robustness and efficiency, and relate experience gained in addressing manpower rostering problems in industry.
BibTeX
@article{khoong1994automated,
  author = {C.M. Khoong and Hoong Chuin Lau and L.W. Chew},
  title = {{Automated Manpower Rostering: Techniques and Experience}},
  journal = {International Transactions in Operational Research},
  year = {1994},
  doi = {10.1111/1475-3995.d01-46},
}
Figure