Cost analysis of alternative formulations for personnel scheduling in continuously operating organizations

Personnel-scheduling problems for continuously operating organizations have proven to be difficult to solve optimally. As a consequence, a number of alternative approaches have been devised for solving these problems. We provide computational results of a study of the staffing costs obtained using a prominent alternative formulation approach. The results demonstrate that excess staffing costs may result from the use of this approach. We subsequently develop a new local-search heuristic based on the simulated annealing algorithm to generate feasible integer personnel schedules in continuously operating organizations. The solution costs and computational effort associated with the new heuristic are shown to be generally superior to those of branch-and-bound integer programming.