04/11/2005, 15:00 — 16:00 — Room P4.35, Mathematics Building
Carlos Bispo, ISR/IST
Optimality of Idling Policies: The Entangled Scheduling and Routing Problem ou Como problemas simples podem contribuir para “desaprender”
The Theory of Queuing Networks (TQN), like many other areas, is built from knowledge and intuition gained with simple models. The M/M/1 queue is the first basic block. Many others were developed and studied over the years, namely the Scheduling Problem, defined for two classes of customers and one single server, and the Routing Problem, defined for one class of customers and two parallel servers.
The majority, if not all, of the basic building blocks defined for the TQN is such that the optimal decision policy is /Non-Idling/. That is, servers only stop when there are no clients waiting for processing. The consequences of this fact are significant and profound in the research conducted for decades in this area. However, as it is the thesis of this presentation, they are misleading and harmful.
A basic building block will be presented, for which the optimal policy will be *shown* to be /Idling/. That is, there are states for which a given server remains idle in the presence of customers waiting for its service. This block, entitled as the Entangled Scheduling and Routing Problem, may become a fundamental tool in the analysis of networks of queues.
In the talk, the problem will be formulated as a Markov Decision Problem and its optimal policy will be presented, as it is numerically produced for some instances of the problem.
It is now necessary to formally characterize the optimal policy as well as *to prove* its idling characteristic. The talk aims at motivating the participants into engaging such formal characterization exercise. Clues and intuition derived from the numerical results will be provided as guides for potential solution paths.
