Load Balancing

A factory has 3 identical machines for doing 6 jobs, which take \(1, 3, 4, 5, 6,\) and \(7\) 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.