This paper considers a scheduling problem of routers with VOQ(Virtual Output Queue)s, where the router has an N × N port input-queued switch and each input queue is composed of N VOQs. The objective of the paper is to develope scheduling algorithms w...
This paper considers a scheduling problem of routers with VOQ(Virtual Output Queue)s, where the router has an N × N port input-queued switch and each input queue is composed of N VOQs. The objective of the paper is to develope scheduling algorithms which minimize mean tardiness under a common due date. The paper characterizes the optimal solution properties. Based upon the characterization, a integer programming is formulated for the optimal solution and two optimal solution algorithms are developed for two special cases of 2 × 2 switch and N × N switch with identical traffic.