Keyun Cheng

Reading Notes: JACM’1977 Scheduling

Title: Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors

Conference (): Link

Journal (Journal of the ACM’1977): Link

Summary

This paper analyzes the theoretical performances (complexity, worst-case bounds) for 5 heuristics for the scheduling unrelated machines problem. Then it provides a heuristic to 2 non-identical processor’s scheduling, and a heuristic to m identical processors.

Main Contributions

Details

• Heuristics to Scheudling Unrelated Machines
  • A: greedily finds the schedule
  • B: sorting by minimum processing time
  • C: sorting by maximum processing time
  • D: Find the most appropriate job among all jobs
  • E: Also traverses the remaining jobs in each round. Very close to D

Strength

Weakness