Dynamic Resource Allocation in Stochastic Processing Networks

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Complex systems like semiconductor wafer fabrication facilities (fabs), networks of data switches, and large scale call centers all demand efficient resource allocation. Deterministic models like linear programs (LP) have been used for capacity planning at both the design and expansion stages of such a system. LP-based planning is critical in setting a medium range or long term goal for many systems. But it does not translate into a day-to-day operational policy that must deal with discreteness of jobs and the randomness of the processing environment. This research project will investigate a general class of stochastic processing networks. A processing network is a system that takes inputs of materials of various kinds and uses various processing resources to produce outputs of materials of various kinds. These processing networks provide high-fidelity stochastic models in diverse economic sectors including manufacturing, service and information technology. The key goal of this research is to devise dynamic, operational policies that can achieve long term objectives for networks. These objectives include (i) achieving maximum throughput predicted by LPs, and furthermore, (ii) minimizing work-in-process or delays in networks. The research team will make fundamental understanding of these stochastic processing networks by building mathematical frameworks at all three time and space scales. More importantly, the team will use the frameworks to (i) devise operational policies that require minimal state information; (ii) prove that these policies are throughput optimal; (iii) identify and prove that policies are asymptotically optimal in terms of some second order performance measures when the system has a unique pooled bottleneck station; (iv) adapt the theoretically proven policies so that they can be readily implemented in a number of application areas. The project attempts to solve dynamic resource allocation problems that are challenging in different economic sectors including manufacturing, service and information technology. The results discovered from this research can directly be applied to wafer fab scheduling, input-queued data switch design and control, Internet Border Gateway routing, congestion based road traffic pricing/control, and call center scheduling. These applications intersect with many disciplines including electrical engineering, computer science, civil engineering, industrial engineering, and management. The Ph.D. students who conduct research on the project will have excellent interdisciplinary training. These interdisciplinary skills are essential for future academic leaders. Building on proven track record, the PI will turn cutting edge research results into course materials to be used for both graduate and undergraduate students at Georgia Tech and elsewhere.