This Article Full Text (PDF) e-companion References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ye, H.-Q. Articles by Yao, D. D. Search for Related Content

Heavy-Traffic Optimality of a Stochastic Network Under Utility-Maximizing Resource Allocation

Department of Logistics, Faculty of Business, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, and School of Business, National University of Singapore, Singapore
Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
lgtyehq{at}inet.polyu.edu.hk
yao{at}ieor.columbia.edu

We study a stochastic network that consists of a set of servers processing multiple classes of jobs. Each class of jobs requires a concurrent occupancy of several servers while being processed, and each server is shared among the job classes in a head-of-the-line processor-sharing mechanism. The allocation of the service capacities is a real-time control mechanism: in each network state, the resource allocation is the solution to an optimization problem that maximizes a general utility function. Whereas this resource allocation optimizes in a "greedy" fashion with respect to each state, we establish its asymptotic optimality in terms of (a) deriving the fluid and diffusion limits of the network under this allocation scheme, and (b) identifying a cost function that is minimized in the diffusion limit, along with a characterization of the so-called fixed-point state of the network.

Subject classifications: stochastic processing network; concurrent resource occupancy; utility-maximizing resource allocation; fluid limit; diffusion limit; resource pooling; heavy-traffic optimality; Lyapunov function.
History: Received January 2006; revision received November 2006; accepted April 2007.