LP-based working subsets for personnel scheduling: Evaluation and augmentation

Michael J. Brusco, Tony R. Johns, Ray R. Venkataraman

Research output: Contribution to journalArticlepeer-review


This paper evaluates the efficacy of LP-based working subsets for generalised set-covering formulations of personnel scheduling problems and presents a nearest-neighbour augmentation procedure for improving performance. Three experimental studies were completed in the evaluation process. In the first study, the LP-based working subset was sufficient to yield an optimal shift scheduling solution for 85% of the 24,300 test problems and the nearest-neighbour augmentation improved the percentage of optimal solutions to over 98%. The second study focused on more complex cyclic shift scheduling environments that permitted shift length, meal break and relief break flexibility. The adequacy of LP-based working subsets was supported by the provision of optimal shift scheduling solutions for 185 of 189 (98%) of the test problems. The third study examined a challenging tour scheduling environment for which globally-optimal benchmarks are not available. The superiority of the augmented LP-based working subset procedure was nevertheless evident, as it yielded better results than the (non-augmented) LP-based working subset for 92% of the test problems despite being constrained to only 40% of the allowed computation time for the non-augmented subsets.

Original languageEnglish (US)
Pages (from-to)175-198
Number of pages24
JournalEuropean Journal of Industrial Engineering
Issue number2
StatePublished - 2018

All Science Journal Classification (ASJC) codes

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'LP-based working subsets for personnel scheduling: Evaluation and augmentation'. Together they form a unique fingerprint.

Cite this