Optimal assignment of high multiplicity flight plans to dispatchers

This paper addresses the problem of finding a feasible schedule of n jobs on m parallel machines, where each job has a deadline and some jobs are preassigned to some machine. This problem arises in the daily assignment of workload to a set of flight dispatchers, and it is strongly characterized by the fact that the job lengths may assume one out of k different values, for small k. We prove the problem to be NP-complete for k = 2 and propose an effective implicit enumeration algorithm which allows efficiently the solution of a set of real-life instances.