Scheduling and control of stochastic processing networks

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.