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