Optimal stochastic scheduling and routing in queueing networks.

Abstract

Queueing networks are extensively used in the study of systems such as communication, computer, and manufacturing networks. Presently there exists some conceptual understanding of many underlying issues of network performance; yet, there remain fundamental issues that are not well understood and need to be investigated. Such issues are related to efficient network resource utilization and routing under imperfect information. In this dissertation we investigate stochastic scheduling, resource allocation and dynamic routing problems arising in queueing networks. We determine optimal policies or derive qualitative properties of optimal policies for the problems described below. We study the problem of optimally scheduling time-critical tasks in multi-class queueing systems. Two different versions of the problem are considered: (i) If the service of a task does not begin by a certain deadline, the task is lost and a fixed cost is incurred; and (ii) if the service of a task is completed at a time other than a certain due date, a penalty proportional to the earliness or tardiness is incurred. We determine properties of dynamic nonidling strategies that minimize infinite horizon expected costs. Next we consider the problem of optimally scheduling tasks in a multi-server system consisting of two interconnected queues. Tasks incur an instantaneous holding cost during the time they remain in the system. We establish sufficient conditions on the service times, the holding costs, and the interconnection process under which it is possible to explicitly determine the strategy that minimizes the total expected discounted cost. Finally we investigate the following decentralized routing problem. We consider a queueing system consisting of two service stations and two controllers, one in front of each station. Customers arriving at a controller's site are to be routed to one of the two stations. Each controller has perfect knowledge of the queue length in its own station and receives information about the other station's queue length with delay of one time unit. We explicitly determine the controllers' routing strategies that minimize the customers' total flowtime.