Utilisation de langages formels pour la modelisation et la resolution de problemes de planification de quarts de travail
Bibliographic record
Abstract
In this thesis, we address different versions of the shift scheduling problem. The shift scheduling problem is to select a set of shifts to cover a planning horizon, typically from 1 to 7 days, divided into periods of equal length for which the required numbers of employees are given. We divide the shift scheduling problems into four main classes. First, we distinguish the problems where the employees are considered to be identical from the problems where each employee has individual characteristics that must be taken into account when assigning them to shifts. We call the first class the anonymous problems and the second one, the personalized problems. Then, we differentiate two other classes of problems, the mono-activity and the multi-activity shift scheduling problems. In this thesis, we study each of these classes of shift scheduling problems with different approaches where constraints on shift construction are formulated with tools based on formal languages. In fact, using automata and grammars, we define languages composed of words that represent allowed shifts for our problem. More precisely, our first contribution presents how, from a finite automata or a context-free grammar defining the rules constraining the construction of shifts for a given problem, one can automatically generate an integer programming model based on binary assignment variables in a graph structure embedding every allowed shift for this problem. The transformation of an automaton or a grammar into a mathematical programming model is inspired by structures from constraint programming. Experiments on a multi-activity shift scheduling problem show that formal language based modeling is very powerful and allows us to address complex rules in the construction of multi-activity shifts. However, while the relevance of our modeling approach is clear, the experimental results reveal some limitations on the scalability of the formulation based on binary assignment variables and decomposed on employees. In fact, when the number of employees and the number of work-activities grow, the model is hard to solve directly. To address both the growing size of the models and the symmetry issues arising from a context where employees are identical, our second contribution is an implicit model based on grammars allowing us to model and solve anonymous multi-activity shift scheduling problems efficiently. From a grammar encoding every restriction in the composition of shifts, we use the graph structure presented in the first article. Instead of using binary variables associated with allowed shifts for each employee, we use nonnegative integer variables to implicitly represent, in a single graph structure, every allowed shift for the problem. The optimal solution to the corresponding integer programming model gives the required number of shifts to cover the demands of the problem and the number of shifts assigned to each work-activity at each period. From these informations, a procedure extracts the optimal explicit solution from the implicit one. Experimental results show that this modeling approach gives easy-to-solve models and can address a wide variety of rules over shifts. We also prove that the models obtained with our technique yield the same integrality gap as well known models in the literature. To our knowledge, this is the first implicit method that can address the multi-activity shift scheduling cases. Our last contribution is a column generation approach also based on grammars that allows us to successfully solve personalized multi-activity shift scheduling problems. The method uses a set covering formulation to model the problem and solves the linear relaxation with a column generation method based on a pricing subproblem using the graph generated from a grammar. A subproblem is defined for each available employee and represents the set of shifts that the given employee is allowed to perform given his individual characteristics. The subproblems are solved with a dynamic programming algorithm. An adapted branching procedure is proposed to find integer solutions and solve the problem exactly. Our method uses a new column generation subproblem and a new branching strategy for this class of problems. The modeling approach is very flexible and contrary to the few other approaches proposed in the literature, it can solve exactly different versions of the personalized multi-activity shift scheduling problem. (Abstract shortened by UMI.)
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.007 | 0.021 |
| Meta-epidemiology (narrow) | 0.003 | 0.002 |
| Meta-epidemiology (broad) | 0.002 | 0.007 |
| Bibliometrics | 0.002 | 0.002 |
| Science and technology studies | 0.002 | 0.006 |
| Scholarly communication | 0.006 | 0.007 |
| Open science | 0.003 | 0.004 |
| Research integrity | 0.003 | 0.007 |
| Insufficient payload (model declined to judge) | 0.006 | 0.002 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".