Zurück zu den Preprints des Jahres 2009


2009-31

Parallel Machine Problems with Equal Processing Times: A Survey

by Kravchenko, S.A., Werner, F..


Series: 2009-31, Preprints

MSC:
90B35 Scheduling theory, deterministic

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