On the Competitiveness of On-Line Scheduling of Unit-Length Packets with Hard Deadlines in Slotted Time
Bruce Hajek · 2001
Abstract — It is shown that the competitive factor for on-line scheduling of unit-length packets with hard deadlines in slotted time is in the interval [0.5, φ], where φ is the inverse of the golden ratio, φ = 5 − 1)/2 ≈ 0.618034. Moreover, any static prior-ity policy, that in each slot schedules a maximum value packet irrespective of deadlines, achieves competitive factor 0.5. I.