, we're makespan- 6. Recall that in the basic Load Balancing Problem from Section 11 interested in placing jobs on machines so as to minimize the the maximum load on any one machine. In a number of applications it is natural to consider cases in which you have access to different amounts of processing power, so that a given job may more quickly on one of your machines than on another. The question then becomes: How should you allocate jobs to machines in these more heterogeneous systems? machines wi th Here's a basic model that exposes these issues. Suppose you have a system that consists of m slow machines and k fast machines. The fast machines can perform twice as much work per unit time as the slow machines. Now you're given a set of n jobs; job i takes time t,to process on a slow machine and time to process on a fast machine. You want to assign each job to a machine; as before, the goal is to minimize the makespan-that is the maximum, over all machines, of the total processing time of jobs assigned to that machine. Give a polynomial-time algorithm that produces an assignment of jobs to machines with a makespan that is at most three times the opti- mum