LPT Scheduling for Multipurpose Machines

We consider scheduling jobs on multipurpose machines where jobs can be processed by a subset of the machines operated in parallel with the objective of minimizing makespan. We apply LPT(Longest Processing Time first) algorithm and prove that its posterior worst-case performance ratio is at most log 24m/(1+λ), where λ is the number of machines eligible for processing the job with the latest completion time. In general, LPT is shown to always find a schedule with makespan at most log 24m/3 times optimum