Scheduling problem solution formulations

  1. Sort by some quantity
  2. Schedule accordingly
  3. Prove correctness by these strategies

Event Scheduling

Q. Interval Scheduling (Greedy Algorithm)

alg. Interval Scheduling with rooms

Q. Multiple Room Interval Scheduling

Q. Interval Coloring

Q. Interval Cover Problem

Job Scheduling

Q. Minimize Makespan (=maximum time on any machine) of machines

alg. Approximate Greedy Makespan: Always choose the least loaded machine

  • Is a 2-level approximation alg. Better Approximate Greedy Makespan: Assign from longest to shortest job, to least loaded machine every time.

alg. Minimize lateness of jobs

  • Interval Scheduling

    • schedule jobs
      • no dependencies
    • => how many jobs can you complete? (total time doesn’t matter!)
    • conflict when:
      • Start[i] <
    • Dynamic Programming solution is easy
      1. OPT = max(1+OPT(jobs that don’t conflict with job 1) vs OPT(2..n))
    • => but or even with improvement !
  • Greedy solution:

    • job that finishes first = job that leaves the most amount of remaining time
    • implementation
      1. Sort by finish time
      2. choose earlyest finish time
      3. choose next earliest finish time that doesn’t conflict with most recently finished job
      4. Done!
    • => time (because sorting)!
    • Proof by induction: Exchange Argument
      • base: optimal solution has
        • if you have that finish time earlier than
        • removing and adding is also optimal solution
  • Try: dp solution

  • variation: make span algorithm (greedy is close to optimal, but not optimal)

  • interval scheduling, but with meeting rooms

    • greedy still words!
  • minimum total completion time.

  • minimize lateness

    • sort by ascending lateness<<