Outline:

1. Recap: blocking under the PCP
2. Partitioning tasks as bin packing
   • overview
   • complexity
3. Hard problems
   • a brief intro to P vs NP
   • what lies beyond NP
4. Heuristics for partitioning
   • next-fit
   • first-fit
   • best-fit
   • worst-fit

Reading assignment (to be completed by the next class):

What you should understand after today (skim proofs):

• Dhall, Sudarshan K., and Chung Laung Liu. “On a real-time scheduling problem.” Operations research 26, no. 1 (1978): 127-140. (PDF on moodle)
  • carefully read: Abstract, Section 1, and Section 6
  • we focused today on Sections 4 and 5
  • skim: Section 3 (we’ll come back to this next week)

Paper to read for Friday:

• “Sensitivity Analysis for Fixed-Priority Real-Time Systems” (Bini et al.)