Scheduling jobs on a single machine with periodic release date/deadline intervals

The problem of scheduling jobs on a single machine with a given set of release date/deadline intervals, in which release dates are integer multiples of a certain constant and each interval has the same length, is considered. The problem is to find an one-to-one mapping from the set of jobs into the set of release dates minimizing an index of the release data assigned to the last scheduled job and assuring that each job is executed entirely in the time interval assigned to it. It is shown that the problem is strongly NP-hard. Two approximation algorithms are proposed and the results of the worst-case analysis are presented.