Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum lateness

The paper is concerned with the problem of scheduling on parallel identical machines partially ordered tasks that can be preempted at integer points in time. The objective function is the maximum lateness. The well-known algorithms for scheduling unit execution time tasks and for scheduling with arbitrary preemptions are not directly applicable to the considered problem. The paper presents a new method for scheduling with integer preemptions and the worst-case analysis for several polynomial-time algorithms which have this method as a core scheduling routine.