## Scheduling and control of stochastic processing networks

##### Abstract

In this dissertation the following two control problems of different queueing
systems are addressed.
Service rate and Admission Control: We consider a single server system
with constant Poisson arrivals subjected to both service rate and admission
controls. The controller can admit or reject a customer on arrival and choose
the service rate, from a fixed subset, when an arrival or departure occurs.
With each control decision is associated a one time rejection cost and a cost
for service. A holding cost and cost for service are continuously incurred.
The holding cost is non-decreasing in the number of customers in the system
and the cost for service is non-decreasing in the service rate. The objective
is to minimize the long run average cost per unit time. We restrict to
(state-dependent) stationary deterministic controls and derive the optimality
equations. We use standard average cost dynamic programming techniques
to obtain the optimality equations in terms of minimum achievable average
cost. The stationary controls correspond to a threshold system state (finite
or infinite) and service rates for each of the states. Customer are rejected
service once the number of customers in the system is greater than or equal
to the threshold. We suggest a fast scheme, based on considering incremental
values of the system threshold for computing the optimal average cost and
the associated optimal service rates. This is similar to initially fixing a system
threshold, and choosing the optimal service rates thereafter. We establish
the monotonicity of optimal service rates in terms of the queue lengths, for
the original system as well as the intermediate systems. Finally, we prove
that the constructed stationary optimal policy is optimal across all possible
non-anticipative controls.
Stochastic Scheduling under Parameter Uncertainty: We suggest a new
approach to model randomness in the context of job shop scheduling. In
addition to inherent randomness such as variable processing times for a job
class, certain parameters, e.g. like the initial number of jobs might not be
known with certainty. We consider scheduling of such a system: a stochastic
job shop with parameter uncertainty.
We model a situation in which the initial number of jobs and the mean
processing times of jobs are uncertain. We assume that the controller has a
limited ability to make certain control decisions before the initial number of
jobs and processing times are revealed. Thus these decisions must be made
a priori. For each server, the scheduler must choose a cycle length and the
fraction of time devoted to processing each job class during a cycle. Under
these assumptions the resulting optimization problem for minimizing expected
makespan is a stochastic integer program. We obtain a continuous job shop
model, a relaxation of the original model, by relaxing the integrality requirements.
When we restrict allowable policies to satisfy certain time allocation
constraints, we obtain a further relaxation called the fluid model. The optimal
solution for the fluid model is shown to be optimal for the continuous job
shop. The optimization problem for the fluid model is a stochastic non-linear
program, which is easier to solve. Based on the optimal solution to the fluid
model, we propose a scheduling heuristic. We show the asymptotic optimality
of the heuristic. The optimality results is in terms the expected makespan.
We also extend the asymptotic optimality results to the case when processing
times are random, i.e., when the job completion process is doubly stochastic.
We obtain tight bounds for makespan which hold with high probability. We
also discuss an assignment problem for the single station case and suggest
asymptotically optimal heuristics, which are constructed from the associated
fluid model.

##### Description

text