Dynamic scheduling of queueing systems with applications to computer networks and flexible manufacturing

Efficient dynamic allocation of resources is essential to high performance design of processing systems in several technological fields, including computing/communication networks and flexible manufacturing. A unified modeling framework for studying resource allocation dynamics is that of queueing systems and networks. In this dissertation, we investigate a number of dynamic scheduling and resource allocation problems associated with basic operations in processing systems, like sequencing, parallel processing, batching and overflow control. Canonical queueing models, capturing the essential characteristics of these operations, are formulated and analyzed mathematically in order to obtain efficient operational policies that maximize performance.; Specifically, four canonical models are investigated, which axe: (1)  Parallel/Synchronized Queueing, (2)  Multiclass Batch Service, (3) Multiclass Queueing with Feedback and (4) Tandem Queueing. Although scheduling for the corresponding deterministic systems is well developed in the literature, the optimal control of the stochastic versions of such models is far less understood. The objective of our study is to present a mathematical analysis of such optimal stochastic scheduling.; The first model concerns processing systems which allow parallel execution of tasks associated with a single job. We study optimal on-line task scheduling algorithm that allocates the tasks of each job upon arrival to parallel processors to minimize the expected job execution time. The second concerns the dynamic allocation of a batch server to multiple incompatible job classes. Optimal operational policies are identified through mathematical analysis using techniques including coupling, interchange arguments, stochastic ordering/majorization and general sample-path comparison methods. Further practical design issues are explored by simulation.; We study the asymptotically optimal control of systems corresponding to the last two models, where an asymptotically optimal policy is one that its absolute difference from the optimal performance is asymptotically negligible while the optimal solution is approaching infinity. Complement to the Brownian approximation approach, where policies for the original control problem are obtained heuristically based on the Brownian limit solution, while the quality of the approximations remains unknown except for numerical verification using simulation, we present a method of measuring the tightness of approximating control policies by developing close bounds for the corresponding system performance.