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 solution a set of real-life instances.
Agnetis, A., Smriglio, S. (2000). Optimal Assignment of High Multiplicity Flight Plans to Dispatchers. NAVAL RESEARCH LOGISTICS, 47(5), 359-376 [10.1002/1520-6750(200008)47:5<359::AID-NAV1>3.0.CO;2-J].
Optimal Assignment of High Multiplicity Flight Plans to Dispatchers
Agnetis, Alessandro;
2000-01-01
Abstract
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 solution a set of real-life instances.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/17602
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo