Keyun Cheng

Reading Notes: Polynomial complete scheduling problems

Title: Polynomial complete scheduling problems

Conference (SOSP’1973): Link

Journal (): Link

Summary

This paper presents theoretical proofs for scheduling unrelated parallel machines.

Main Contributions

• Builds theoretical foundations of scheduling problem

Details

• Definition of NP, NP-Complete problems

• Theoretical proofs of the NP-completeness scheduling problem, by reducing to a 3-satisfiability problem

Strength

Weakness