EnglishGiven 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.
| 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): | 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:
http://hdl.handle.net/11380/619417
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
Copyright © 2019