An MILP-based heuristic for staff scheduling problems with acceptance levels

Rihm, Tom (September 2015). An MILP-based heuristic for staff scheduling problems with acceptance levels (Unpublished). In: International Conference on Operations Research. Vienna. 01.-04.09.2015.

We present a real-world staff-assignment problem that was reported to us by a provider of an online workforce scheduling software. The problem consists of assigning employees to work shifts subject to a large variety of requirements related to work laws, work shift compatibility, workload balancing, and personal preferences of employees. A target value is given for each requirement, and all possible deviations from these values are associated with acceptance levels. The objective is to minimize the total number of deviations in ascending order of the acceptance levels.

We present an exact lexicographic goal programming MILP formulation and an MILP-based heuristic. The heuristic consists of two phases: in the first phase a feasible schedule is built and in the second phase parts of the schedule are iteratively re-optimized by applying an exact MILP model. A major advantage of such MILP-based approaches is the flexibility to account for additional constraints or modified planning objectives, which is important as the requirements may vary depending on the company or planning period.

The applicability of the heuristic is demonstrated for a test set derived from real-world data. Our computational results indicate that the heuristic is able to devise optimal solutions to non-trivial problem instances, and outperforms the exact lexicographic goal programming formulation on medium- and large-sized problem instances.

Item Type:

Conference or Workshop Item (Speech)


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


600 Technology > 650 Management & public relations




Juliana Kathrin Moser-Zurbrügg

Date Deposited:

22 Feb 2016 15:22

Last Modified:

28 Jan 2020 13:48


Actions (login required)

Edit item Edit item
Provide Feedback