Pré-affectation des tâches aux employés effectuant des tâches non-interruptibles et des activités interruptibles

In this thesis, we consider the problem of assigning tasks and activities to employees, which represents the last stage in the personnel scheduling process. We assume in the thesis that tasks are non-interruptible and activities are interruptible. The signification of “non-interruptible” and “interruptible” is that each task should be finished continuously by the same employee(s) without any preemption; however, activities can be interrupted. That is, an employee can be replaced by another one during an activity. The duration of a task is much shorter than that of an activity. Furthermore, the demand of a task is a constant of required employees; whereas the demand of an activity is expressed as a curve which varies with time periods. This curve represents the number of required employees in each of certain discrete time slices in a given period. We proposed a two-phases method to solve this problem. In the first phase, work shifts are covered by tasks and activities while relaxing certain constraints of the activities. For the next phase, we consider the assignment of activities to employees with the tasks fixed. Three basic models are proposed for the problem of phase 1. The objective of the first model is to distribute the over-covering of activities among time periods and activities. Some new variables are added in the second model for the inactive employees (who are not assigned any work). The objective is to maximize their qualifications (to have more flexibility for activities in phase-2). The qualifications of inactive employees are distributed into three linear segments in the third model. Several extensions are presented to improve the performance of the models. For example, the situations of multiple employees demand for each task, the precedence constraints of tasks, and the pre-treatment of tasks to avoid bad assignments are also discussed in the thesis.

Résumé

Ce mémoire est consacré au problème d'affectation des tâches et des activités aux employés. Dans le mémoire, nous supposons que les tâches sont non-interruptibles et les activités sont interruptibles, c'est-à-dire que chaque tâche doit être exécutée continuellement par le même employé, mais les activités peuvent être interrompues. Donc, on peut remplacer un employé par un autre durant l'activité. La durée d'une tâche est beaucoup plus courte que celle d'une activité. Par ailleurs, la demande d'une tâche est un nombre fixé d'employés requis. La demande d'une activité est une courbe variant avec le temps. Cette courbe indique le nombre d'employés requis dans chaque tranche de temps d'une certaine discrétisation de la période considérée. Ce problème constitue le dernier niveau de décision dans le procesus d'horaires du personnel. Nous proposons une nouvelle stratégie en deux phases pour résoudre ce problème. Dans la première phase, nous remplissons les quarts de travail par des tâches et des activités en relaxant certaines des contraintes sur les activités. Ensuite, nous considérons l'affectation des activités aux employés avec les tâches fixées. Trois modèles de base sont proposés pour le problème de la phase 1. L'objectif du premier modèle est de répartir les sur-couvertures d'activités entre les périodes et les activités. Les nouvelles variables pour les employés inactifs sont ajoutées dans le deuxième modèle, et les qualifications des employés inactifs sont maximisées pour avoir plus de flexibilité pour les activités dans la phase 2. Ces qualifications sont réparties en trois morceaux dans le troisième modèle. Certaines extensions sont présentées pour améliorer les modèles de base. Nous discutons le cas où la demande de chaque tâche est d'un ou plusieurs employés, les contraintes de précédence des tâches et le pré-traitement des tâches afin d'éviter les mauvaises affectations.