Proof of bound

• work-conserving ==> busy intervals coincide for GPS and A

• Let pkt1, pkt2, ..., pktn,... denote the pkts in alg A’s service order

  • Let ti denote pkti’s completion time in A’s schedule
  • Let ui denote pkti’s completion time in GPS’s schedule

fi,Ak ? fi,GPSk + Lmax / r

Previous slide

Next slide

Back to first slide

View graphic version