Final answer:
The largest processing time rule computes an optimal schedule for any input where the processing requirement of each job is more than one third the optimal makespan.
Step-by-step explanation:
The question is asking us to show that for any input to the problem of minimizing the makespan on identical parallel machines, where the processing requirement of each job is more than one third the optimal makespan, the largest processing time rule computes an optimal schedule.
To prove this, we can use the concept of the largest processing time rule. This rule states that we should schedule the job with the longest processing time first. By doing this, we ensure that the job with the highest processing requirement is completed first, which leads to a more optimal schedule.
Now, let's assume that the processing requirement of each job is more than one third the optimal makespan. This means that each job is relatively large in terms of processing time.
If we apply the largest processing time rule, we will always schedule the job with the longest processing time first. Since each job has a processing requirement that is more than one third the optimal makespan, this means that the job with the longest processing time will always have a processing requirement that is more than one third the optimal makespan.
Therefore, the largest processing time rule will compute an optimal schedule for any input where the processing requirement of each job is more than one third the optimal makespan.