Answers are grounded in this paper and cite their sources.
We study a problem arising in the administration of staff positions in organizations with a fixed set of given positions, e.g., public institutions. When a new employee is hired, one or more of the available positions need to be (partially) assigned to her while respecting that they are already (partially) assigned to other staff members, possibly only during certain time intervals. Some positions are better suited for the new hire due to their associated pay grades or other administrative reasons. Furthermore, one seeks an assignment to only few positions and with only few changes over time. This yields a multi-objective optimization problem with a lexicographic objective function that models the mentioned considerations. Our problem can be seen as a scheduling problem with non-availability periods for the machines, where one of the objectives is to minimize the number of job preemptions. We derive structural insights into this problem and present three MIP-formulations based on them. Their solutions are optimal with respect to the three most important sub-objectives and optimal or near-optimal with respect to the least important sub-objective, respectively. We show that, using our formulations, we can find provably optimal solutions considerably faster than with a straightforward approach and near-optimal solutions even faster. In addition, we present a combinatorial algorithm for an important special case of the problem with even better running times. Our results form the backbone of an optimization tool we developed in collaboration with the administration of the Technical University of Munich where it is now used regularly whenever a new employee is hired.
No takes yet. Share an insight, caveat, or question.
Jendraszewski et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: