Content area
Full Text
During the last ten years, the parallel machine scheduling problems have been intensively studied. In this paper, we present an overview of the research devoted to these problems with emphasis on the case of the optimal makespan on identical parallel machines. Scheduling problems with more than one machine involve both resource allocation and sequencing, rather than simply sequencing. The complexity, in general, grows exponentially, making the problems intractable. Since efficient exact algorithms have not been found in 50 years of researching, one is led to suspect that it will be impossible to find them, although it remains an open question. Because of the increasing appearance of these problems in Computer Science, besides their intractability, heuristic algorithms have been extensively developed to solve real world problems with very good results. However, for many cases, polynomial time approximation algorithms that guarantee near-optimal solutions are not known, so that it constitutes a true challenge. An effort has been made to review all the classical publications, from the late fifties to the most recent papers, giving attention to the results that have not been surveyed until now and suggesting directions for future research.
Keywords: Scheduling theory, optimization.
1. Introduction
In the classical Parallel Machine Scheduling (PMS) problem, there are n jobs and m machines. Each job needs to be executed on one of the machines during a fixed processing time. So the aim is to find the schedule that optimizes a certain performance measure.
The scheduling process involves two kinds of decisions, sequencing (the order in which jobs are processed), and job-machine assignment. Single machine problems ask just to find an optimal job sequencing, but in the multiple machines case it is necessary to find an optimal job-machine assignment as well. The complexity usually grows exponentially with the number m of machines, making the problem intractable. This problem, like all deterministic scheduling problems, belongs to the wide class of Combinatorial Optimization problems, many of which are known to be NP-hard (Cook, 1971; Karp, 1972; Garey and Johnson, 1979; and Papadimitriou, 1994). What this means is that it is not likely that there are efficient optimization algorithms to solve them. Consequently, the algorithms can be divided into those requiring polynomial time and those requiring exponential time to find...