A note on the assignment problem with seniority and job priority constraints

Consider an assignment problem in which persons are qualified for a subset of the jobs; assume the persons to belong to given seniority classes. Seniority constraints impose that the solution is such that no free person can be given a job unless an assigned person with the same or higher seniority becomes free. Similarly, jobs can belong to priority classes for which priority constraints must hold. It is shown that the assignment problem with both types of constraints can be solved by successively reoptimizing a (rectangular) linear assignment problem of increasing size. The related complexity is lower than for a known coefficient scaling approach. A further advantage of this approach is that it is easy to modify to solve the problem under the bottleneck criterion