An Example of Scheduling When Precedence Constraints Exist

Tony D’Amato runs a local body shop that does automotive painting and repairs. On a particular Monday morning he has six cars waiting for repair. Three(1,2, and 3) are from a car rental company and he has agreed to finish these cars in the order of the dates that they were promised. Cars 4, 5, and 6 are from a retail dealer who has requested that car 4 be completed first because a customer is waiting for it. The resulting precedence constraints can be represented as two disconnected networks, as pictured in following figure.


The times required to repair each of the cars(in days) and the associated promised completion dates are
Job 1 2 3 4 5 6
Processing time 2 3 4 3 2 1
Due date 3 6 9 7 11 7
　Determine how the repair of the cars should be scheduled through the shop in order to minimize the maximum tardiness.
Solution
1, First we find the job scheduled last(sixth). Among the candidates for the last position are those jobs that are not predecessors of other jobs. These are 3,5, and 6. The total processing time of all jobs is 2+3+4+3+2+1=15.(This is the current value of t). As the objective is to minimize the maximum tardiness, we compare the tardiness of these three jobs and pick the one with smallest value. We obtain min{15-9, 15-11, 15-7}=min{6, 4, 8}=4, corresponding to job 5. Hence job 5 is scheduled last(position 6).
2, Next we find the job scheduled fifth. The candidates are jobs 3 and 6 only. At this point the value of t is 15-2=13. Hence, we find min{13-9, 13-7}=min{4,6}=4, which corresponds to job 3. Hence, job 3 is scheduled in the fifth position.
3, Find the job scheduled fourth. Because job 3 is no longer on the list, job 2 now becomes a candidate. The current value of t=13-4=9. Hence, we compare min{9-6,9-7}=min{3,2}=2, which corresponds to job 6. Schedule job 6 in the fourth position.
4, Find the job scheduled third. Job 6 has been scheduled, so job 4 now becomes a candidate along with job 2, and t=9-1=8. Hence, we look for min{8-6, 8-7}=min{2, 1}=1, which occurs at job 4.
5, At this point we would find the job scheduled second. However, we are left with only job 1 and 2, which because of the precedence constraints, must be scheduled in the order 1-2.
Summarizing the results above, the optimal sequence to repair the cars is 1-2-4-6-3-5.
In order to determine the value of the objective function, the maximum tardiness, we compute the flow time for each job and compare it to the due date. We have
Job Processing Time Flow Time Due Date Tardiness
1 2 2 3 0
2 3 5 6 0
4 3 8 7 1
6 1 9 7 2
3 4 13 9 4
5 2 15 11 4
Hence, the maximum tardiness is four days.