In the context of Greedy Approximation Algorithms:

Given:

  • identical machines
  • jobs, each taking time
  • is the set of jobs assigned to machine
  • Load of the machine is (I.E. The sum of the time required to complete).
  • Goal is to minimise - the makespan (total time taken to complete all jobs by the machine)
  • Optimal solution () is

The problem is NP Hard for identical machines.

Algorithm for this problem:

Steps:
  • Pick any job
  • Assign it to machine with the smallest load
  • Remove it from pile of jobs

Choosing a bounds for this problem:

Well we’ve actually got 2 bounds:

  • Assuming each job is roughly equal sized, the best case scenario is it’s the sum of jobs divided by the amount of computers (so each machine can take a roughly equal load)
  • Or: If there’s a single job that takes a disproportionately long time, an optimal solution could be however long that task is,