Parallel machine scheduling problems: A survey

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.