This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Caron, G. Articles by Jaumard, B. Search for Related Content

The Assignment Problem with Seniority and Job Priority Constraints

Ecole Polytechnique de Montréal, Montréal, Québec, Canada
Ecole des Hautes Études Commerciales, Montréal, Québec, Canada
Ecole Polytechnique de Montréal, Montréal, Québec, Canada

Consider an assignment problem in which persons are qualified for some but usually not all of the jobs. Moreover, assume persons belong to given seniority classes and jobs have given priority levels. Seniority constraints impose that the solution be such that no unassigned person can be given a job unless an assigned person with the same or higher seniority becomes unassigned. Priority constraints specify that the solution must be such that no unassigned job can become assigned without a job with the same or higher priority becoming unassigned. It is shown that: (i) adding such constraints does not reduce and may even increase the number of assigned persons in the optimal solution; (ii) using a greedy heuristic for constrained assignment (as often done in practice) may reduce the number of assigned persons by half, and (iii) an optimal solution to the assignment problem with both types of constraints can be obtained by solving a classical assignment problem with adequately modified coefficients.

Subject classifications: health care; hospitals; network/graphs; theory; applications.