Consider a time-slotted queuing system which has two servers and two users. At each time slot, a packet for user $1$ arrives with probability $\lambda _1$, while a packet arrives for user $2$ with probability $\lambda _2$. All the arrivals are independent of one another. The servers can serve at most $1$ packet in each time slot. If user $1$'s packet goes to server $1$ then the probability of service in a slot is $p_1$ while the same for server $2$ is $q_1$. For, user $2$'s packets the corresponding service rates are $p_2$ and $q_2$, respectively. At each time slot a scheduling policy assigns one packet to each server. What is the optimal policy that minimizes the maximum of the average queue length of the two queues? The objective function to minimize is, $\mathrm{max} (\mathbb{E}[Q_1(t)] , \mathbb{E}[Q_2(t)] ) $.

Assume that $p_1 >\lambda _1 > q_1$ and $p_2 >\lambda _2 > q_2$ . I am aware that the max-weight policy would be throughput-optimal. But I am not sure what is the optimal policy for the above objective function.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.