Staff assignment with lexicographically ordered acceptance levels

Rihm, Tom; Baumann, Philipp (2018). Staff assignment with lexicographically ordered acceptance levels. Journal of scheduling, 21(2), pp. 167-189. Springer 10.1007/s10951-017-0525-1

art%3A10.1007%2Fs10951-017-0525-1 (2).pdf - Published Version
Available under License Publisher holds Copyright.

Download (827kB) | Preview

Staff assignment is a compelling exercise that affects most companies and organizations in the service industries. Here, we introduce a new real-world staff assignment problem that was reported to us by a Swiss provider of commercial employee scheduling software. The problem consists of assigning employees to work shifts subject to a large variety of critical and noncritical requests, including employees’ personal preferences. Each request has a target value, and deviations from the target value are associated with integer acceptance levels. These acceptance levels reflect the relative severity of possible deviations, e.g., for the request of an employee to have at least two weekends off, having one weekend off is preferable to having no weekend off and thus receives a higher acceptance level. The objective is to minimize the total number of deviations in lexicographical order of the acceptance levels. Staff assignment approaches from the literature are not applicable to this problem. We provide a binary linear programming formulation and propose a matheuristic for large-scale instances. The matheuristic employs effective strategies to determine the subproblems and focuses on finding good feasible solutions to the subproblems rather than proving their optimality. Our computational analysis based on real-world data shows that the matheuristic scales well and outperforms commercial employee scheduling software.

Item Type:

Journal Article (Original Article)


03 Faculty of Business, Economics and Social Sciences > Department of Business Management > Institute of Financial Management > Professorship for Quantitative Methods in Business Administration

UniBE Contributor:

Rihm, Tom and Baumann, Philipp


600 Technology > 650 Management & public relations








Juliana Kathrin Moser-Zurbrügg

Date Deposited:

12 Jul 2017 13:14

Last Modified:

12 May 2022 14:16

Publisher DOI:





Actions (login required)

Edit item Edit item
Provide Feedback