TY - JOUR
T1 - LP-based working subsets for personnel scheduling
T2 - Evaluation and augmentation
AU - Brusco, Michael J.
AU - Johns, Tony R.
AU - Venkataraman, Ray R.
N1 - Publisher Copyright:
© 2018 Inderscience Enterprises Ltd.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85044772615&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85044772615&partnerID=8YFLogxK
U2 - 10.1504/EJIE.2018.090614
DO - 10.1504/EJIE.2018.090614
M3 - Article
AN - SCOPUS:85044772615
SN - 1751-5254
VL - 12
SP - 175
EP - 198
JO - European Journal of Industrial Engineering
JF - European Journal of Industrial Engineering
IS - 2
ER -