Dynamic and Stochastic Scheduling of Multi-product Queues with
Setups: A Diffusion Approach
Ph D Dissertation

K. Ravikumar


The class of scheduling problems investigated in this dissertation is motivated by stochastic scheduling of multi-product manufacturing systems with switchover costs and/or switchover times. The dynamic scheduling methodology originated in the dissertation is applicable in general to many discrete activity scheduling problems arising in manufacturing, computer, and communication systems. The scheduling problem is formulated in the modeling framework of multi-class queues in heavy traffic. The solution methodology is based on Brownian approximations and uses an extended version of the multi-armed bandit problem with diffusion dynamics.

Specifically, consider a flexible machine center which caters to multiple classes of products with significant setup times and/or setup costs involved in switching from one class of products to another. A holding cost is incurred for making a customer wait for service. The processing times and inter-arrival times are allowed to have arbitrary distributions. Our objective is to evolve a scheduling policy that would minimize the infinite horizon discounted cost. This scheduling problem, especially in the presence of setup costs and/or setup times, has defied analytical tractability and has remained an open problem except in very special cases. In this work, we originate a solution methodology for this problem in a general setting by invoking an approach based on diffusion approximations for multiclass queues in heavy traffic. The use of diffusion approximations creates a tractable control and optimization framework, with just the knowledge of only the first two moments of arrival and service processes. In this setting, the scheduling problem is transformed into a stochastic control problem in a multi-dimensional framework, with an interesting variant of the multi-armed bandit problem embedded within it. The methodology leads to an elegant and computationally efficient index strategy for dynamic scheduling, which at any decision epoch assigns an index to each product class as a function of the current state of the system.

A brief outline

We present a detailed insightful formulation of the main scheduling problem of interest in a multi-parameter framework, by defining the allocation policy as a vector valued stochastic process . We assume that once a queue is selected it will be served until exhaustion and at such exhaustion epochs the decision as to which queue to be selected next is made. So, we concentrate on a subset of allocation policies, called switching strategies, which ensure that no two queues are attended to simultaneously. These switching strategies exert control over diffusion processes obtained as heavy traffic limits of queueing models with server vacations. Thus, the original scheduling problem becomes a stochastic control problem of a system driven by diffusion dynamics.

The solution methodology rests on a variant of the multi-armed bandit problem in continuous time. By embedding an optimal stopping problem, parameterized by the stopping cost, we derive an interesting index strategy which associates an index to every component diffusion process depending on its current state at a decision epoch and the strategy is to choose the component having the least index value (at a decision epoch) and activate it without interrupting until it hits zero. Simulation studies performed show the superiority of the index strategy over many known heuristic policies.

We also address the setup time problem, with deterministic setup times. Since the setup time problem entails difficult analytical treatment, we reformulate this as a setup cost problem with zero setup times and use the above results to evolve an index based scheduling policy. We again provide numerical results.