(1) Mathematical Institute, Leiden University, P.O. Box 9512, 2300RA Leiden, The Netherlands;(2) Mathematical Institute, Leiden University, P.O. Box 9512, 2300RA Leiden, The Netherlands
Abstract:
In this companion paper of [10] we introduce the combinatorial notion of unbalance for a routing pattern. Using this unbalance we derive an upper bound for the total average expected waiting time of jobs which are routed to parallel queues according to a periodic routing rule. A billiard sequence is obtained with unbalance smaller than or equal to –1, where N is the number of different symbols in the sequence which corresponds to the number of parallel queues in the routing problem.
–1, where N is the number of different symbols in the sequence which corresponds to the number of parallel queues in the routing problem.