Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem
Mauro Dell'Amico, Manuel Iori, Silvano Martello, Michele Monaci
INFORMS Journal on Computing · 2008 · Volume 20 · Issue 3
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.
Keywords
scheduling, identical parallel machines, bin packing, scatter search, column generation
Enable JavaScript for citation tools and additional paper interactions.