09-31
Parallel Machine Problems with Equal Processing Times: A Survey
by Kravchenko, S.A.; Werner, F.
Preprint series: 09-31, Preprints
Abstract: The basic scheduling problem we are dealing with is the following. There are n jobs, each requiring an identical execution time. All jobs have to be processed on a set of parallel machines. Preemptions can be either allowed or forbidden. The aim is to construct a feasible schedule such that a given criterion is minimized. For a couple of problems of this type, recently the complexity status has been solved and several interesting results have been presented. In this paper, we survey existing approaches for the problem class considered.
Keywords: scheduling, parallel machine problems, equal processing times, polynomial algorithms, NP-hard problem
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.