Scheduling Jobs with Equal Processing Times

What is it about?

Whereas the overwhelming majority of scheduling problems appears to be NP-hard, models with equal processing time jobs form a remarkable case which is still open for most problems but it intuitively looks polynomially solvable. The basic scheduling problem we are dealing with is the following. There are n jobs, each requiring an identical execution time. There are associated a release time and a deadline with each job. All data are assumed to be integers. The aim is to construct a feasible schedule so as to minimize a given criterion. In this paper, we survey existing approaches for the problem considered, and for various machine environments.

Featured Image