The Simple and Multiple Job Assignment Problems

Abstract : This paper addresses two real-life assignment problems. In both cases, the number of employees to whom tasks should be assigned is significantly greater than the number of tasks. In the simple job assignment problem, at most one task (job) should be assigned to each employee; this constraint is relaxed in the multiple job assignment problem. In both cases, the goal is to minimize the time the last task is completed; these problems are known as Bottleneck Assignment Problems (BAPs for short). We show that the simple job assignment problem can be solved optimally using an iterative approach based on dichotomy. At each iteration, a linear programming problem is solved: in this case the solution is integer. We propose a fast heuristic to solve the multiple job assignment problem, as well as a Branch-and-Bound approach which leads to an optimal solution. Numerical examples are presented. They show that the heuristic is satisfactory for the application at hand.
Type de document :
Rapport
[Research Report] RR-3744, INRIA. 1999, pp.15
Liste complète des métadonnées

https://hal.inria.fr/inria-00072918
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:16:43
Dernière modification le : samedi 17 septembre 2016 - 01:06:49
Document(s) archivé(s) le : jeudi 24 mars 2011 - 12:20:42

Fichiers

Identifiants

  • HAL Id : inria-00072918, version 1

Collections

Citation

Fabrice Chauvet, Jean-Marie Proth, A. Soumare. The Simple and Multiple Job Assignment Problems. [Research Report] RR-3744, INRIA. 1999, pp.15. 〈inria-00072918〉

Partager

Métriques

Consultations de la notice

385

Téléchargements de fichiers

159