In a Jackson network, organized as a tree rooted at queue r, several customers are queued at time 0 and there is no new customer arrival. The service time of each customer in queue i is geometrically distributed with rate $p_i$. Service times are independent and service can be preempted. Each customer arrives at parent queue after it is served in queue i. The objective is to find a scheduling policy that maximizes the expected number of customers in queue r at time T. Note queue r is never active and once a customer arrives at r, it stays.

The problem falls in the arena of stochastic scheduling in Markov Decision Process. However, there are two constraints in my problem: no two queues sharing a parent can be active at the same time; plus, a queue and its parent queue cannot be active together. Can anyone please give some hint (reference books, papers, etc.) on how this or similar problem is approached in the literature? Is there some optimal result, like $\mu c$-rule, for this problem? Thanks in advance.

  • $\begingroup$ In MDPs you have quite some flexibility with constraints, and often in the end you just have to formulate the dynamic programming equations to solve the problem. Unfortunately, I am not familiar with queuing problems, and hence do not see precisely how your setting can be reformulated as an MDP. Have you thought of that? $\endgroup$ – Ilya Nov 19 '14 at 8:49
  • $\begingroup$ It has been formulated in an MDP with states being the number of customers at each queue. It yields an optimal solution, but it suffers from the curse of dimensionality and becomes computationally intractable as network grows large. Thus, I propose an efficient greedy scheduling policy. But I'm having difficulty proving its optimality and thus want to see if there is any literature in closely-related stochastic scheduling that can give me some hint on the proof. $\endgroup$ – sinoTrinity Nov 19 '14 at 15:06

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.