Title: LP-based working subsets for personnel scheduling: evaluation and augmentation

Authors: Michael J. Brusco; Tony R. Johns; Ray R. Venkataraman

Addresses: Department of Business Analytics, Information Systems and Supply Chain, College of Business, Florida State University, 821 Academic Way, Tallahassee, FL 32306-1110, USA ' Department of Management and Marketing, College of Business Administration and Information Sciences, Clarion University, 335 Still Hall, Clarion, PA 16214, USA ' Project and Supply Chain Management Department, Sam and Irene Black School of Business, Penn State Erie, 255, Burke Center, Jirdan Road, Erie, PA 16563, USA

Abstract: 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. [Received 24 April 2017; Revised 25 August 2017; Revised 17 September 2017; Accepted 6 December 2017]

Keywords: personnel scheduling; integer programming; linear programming.

DOI: 10.1504/EJIE.2018.090614

European Journal of Industrial Engineering, 2018 Vol.12 No.2, pp.175 - 198

Published online: 23 Mar 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article