Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem

Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem

0.00 Avg rating0 Votes
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: , , ,
Keywords: heuristics
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 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.

Reviews

Required fields are marked *. Your email address will not be published.