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. [10.1287/ijoc.1070.0246]

Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem

DELL'AMICO, Mauro;IORI, MANUEL;
2008

Abstract

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.
20
333
344
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. [10.1287/ijoc.1070.0246]
Dell'Amico, Mauro; Iori, Manuel; S., Martello; M., Monaci
File in questo prodotto:
File Dimensione Formato  
ijoc.1070.0246.pdf

non disponibili

Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 212 kB
Formato Adobe PDF
212 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/619417
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 41
  • ???jsp.display-item.citation.isi??? 35
social impact