Load Balancing
A factory has 3 identical machines for doing 6 jobs, which take and hours of time, respectively.
The factory manager wants to schedule the jobs and run the machines in parallel such that all of the jobs can be finished in as little time as possible.
Can the manager finish all the jobs in less than 10 hours?
For example, one way to schedule the jobs would be to
- let machine 1 do the first and second jobs, taking 4 hours;
- let machine 2 do the third and fourth jobs, taking 9 hours;
- let machine 3 do the fifth and sixth jobs, taking 13 hours.
Running them in parallel would require 13 hours for all the machines to finish, which exceeds the deadline he has been given.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let machine 1 do first and sixth jobs, taking 8 hours.
Let machine 2 do second and fifth jobs, taking 9 hours.
Let machine 3 do third and fourth jobs, taking 9 hours.
Running them in parallel would require only 9 hours to finish all jobs.