ABSTRACT

The majority of the basic building blocks constructed in the context of
queuing theory is such that the centralized optimal decision policy, as
computed by  means of formulating  a Markov Decision  Problem (MDP), is
non-idling when costs  incurred are  proportional to  queue length. The
consequences  of this  fact have  been significant  and profound in the
research conducted for decades in this area.

A basic queuing network will  be presented which poses some interesting
challenges.  It is a combination  of two  classic decision  problems in
networks: the scheduling problem and the routing problem. For a network
with three servers processing two  customer classes, one of the servers
has to  make scheduling  decisions  which  have a  routing  consequence
outside  of its  control. Unlike  many basic  toy problems, the distin-
guishing feature of the problem  is the fact that, for some states, the
optimal policy of this  central server involves  keeping it idle in the
presence of customers. The problem will be formulated as an MDP and its
optimal  policy will be  presented, as  it is numerically  produced for
some instances of the  problem. The consequences  and challenges  posed
by this  new  problem, as  well as  its relevance  in general  queueing
networks, will be discussed.