Example 5.5.1 (Minimizing Maximum Lateness with Preemptions) Consider the following instance of P2 prmp Lmax with 4 jobs. The processing times and due dates are given in the table below. Preemptions are allowed at integer points in time. 138 5 Parallel Machine Models (Deterministic) First, it has to be checked whether there exists a feasible solution with Lmax=0. The data of the instance created through time reversal are determined as follows. The release dates are obtained by determining the maximum due date in the original problem which is 9 and corresponds to job 4 ; the release date of job 4 in the new problem is then set equal to 0 . The release dates of the remaining jobs are obtained by subtracting the original due dates from 9. The question now is: in this new instance can a schedule be created with a makespan less than 9? Applying LRPT immediately yields a feasible schedule