Optimal stochastic scheduling of queueing networks: Switching costs and partial information.

Abstract

This dissertation addresses two fundamental resource allocation issues encountered in a variety of network systems: scheduling subject to (1) penalties for changes of server allocation (switching penalties) and (2) partial information. We focus on the characterization of optimal dynamic control policies, thereby reducing the search and/or computation required to determine an optimal control strategy. Our treatment of the first issue, switching penalties, begins with complete information. Consider a system of parallel queues without arrivals for which service periods in a particular node are i.i.d. In addition to holding costs in each node, a set-up switching cost (or set-up time) is incurred at each instant the server processes a job in a queue different than the previous one. We prove that an index rule is optimal and derive the closed form indices associated with each queue. The analysis of parallel queues is used to address problems with connected queues and switching penalties. In this case, a queue may send jobs to another queue, thus forming a forest network. We determine conditions on the holding costs and service distributions for which exhaustive service is optimal. That is, the server never leaves a queue while jobs remain in it. We treat both switching costs and partial information in the context of scheduling a passenger shuttle or, more abstractly, a batch server. We analyze two problems. In the first, we consider dispatching a single finite capacity shuttle between two terminals. The controller observes perfectly the terminal at which it waits, but obtains only delayed observations of the other. In the second problem, we consider the dispatching of an infinite capacity shuttle on a fixed ring of N terminals. Customers boarding at one terminal depart at the next terminal. The controller observes the present terminal, but has no recent observations of the other terminals since its last visit to them. For both of these shuttle scheduling problems, we prove optimality and monotonicity of threshold policies.