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,