Lex-optimal online multiclass scheduling with hard deadlines

Bruce Hajek, Pierre Seri

Research output: Contribution to journalArticlepeer-review


Online scheduling of unit-length packets with hard deadlines by a single server in slotted time is considered. First, the throughput optimal scheduling policies are characterized. Then multiclass packets are considered in which each packet has an M-bit class identifier, and a new optimality property called lex-optimality (short for lexicographic optimality) is defined for online scheduling policies. Lex-optimality is a hierarchical sequence of M throughput optimality properties. The lex-optimal policies that do not drop packets early are characterized. Both characterizations involve identification of a "no-regret subset" of the set of packets available for scheduling in a given slot. A lex-optimal scheduling algorithm is presented with complexity per packet O(MB), where M is the log of the number of priority classes and B is the maximum buffer size. The algorithm requires no more packets to be buffered than any online, throughput optimal scheduling policy. Simulation results are presented that illustrate that lex-optimality combines elements of pure priority and nested priority scheduling.

Original languageEnglish (US)
Pages (from-to)562-596
Number of pages35
JournalMathematics of Operations Research
Issue number3
StatePublished - Aug 2005


  • Competitive optimality
  • Deadlines
  • Multiclass queues
  • Online scheduling
  • Priority

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Lex-optimal online multiclass scheduling with hard deadlines'. Together they form a unique fingerprint.

Cite this