Given a set of jobs, with associated processing times, and a set of identical machines, each of which can process at most one job at a time, the Parallel Machine Scheduling Problem is to assign each job to exactly one machine so as to minimize the maximum completion time of a job. The problem is strongly NP-hard, and has been intensively studied since the Sixties.We present a metaheuristic and an exact algorithm, and analyze their average behavior on a large set of test instances from the literature.The metaheuristic algorithm, which is based on a scatter search paradigm, computationally proves to be highly effective, and capable of solving to optimality a very high percentage of the publicly available test instances. The exact algorithm, which is based on a specialized binary search and a branch-and-price scheme, was able to quickly solve to optimality all remaining instances.
Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem / Dell'Amico, Mauro; Iori, Manuel; S., Martello; M., Monaci. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - STAMPA. - 20(2008), pp. 333-344.
Data di pubblicazione: | 2008 |
Titolo: | Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem |
Autore/i: | Dell'Amico, Mauro; Iori, Manuel; S., Martello; M., Monaci |
Autore/i UNIMORE: | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1287/ijoc.1070.0246 |
Rivista: | |
Volume: | 20 |
Pagina iniziale: | 333 |
Pagina finale: | 344 |
Codice identificativo ISI: | WOS:000257473600001 |
Codice identificativo Scopus: | 2-s2.0-61349128377 |
Citazione: | Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem / Dell'Amico, Mauro; Iori, Manuel; S., Martello; M., Monaci. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - STAMPA. - 20(2008), pp. 333-344. |
Tipologia | Articolo su rivista |
File in questo prodotto:

I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris