Article ID: | iaor200952618 |
Country: | United States |
Volume: | 20 |
Issue: | 3 |
Start Page Number: | 333 |
End Page Number: | 344 |
Publication Date: | Jun 2008 |
Journal: | INFORMS Journal On Computing |
Authors: | Martello Silvano, Dell'Amico Mauro, Monaci Michele, Iori Manuel |
Keywords: | heuristics |
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 1960s. 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.