EJP Reading Tools

Dynamic Scheduling of a Parallel Server System in Heavy Traffic with Complete Resource Pooling: Asymptotic Optimality of a Threshold Policy

Dublin Core		PKP Metadata Items	Metadata for this Document
1.	Title	Title of document	Dynamic Scheduling of a Parallel Server System in Heavy Traffic with Complete Resource Pooling: Asymptotic Optimality of a Threshold Policy
2.	Creator	Author's name, affiliation, country	Steven L. Bell; University of California, San Diego
2.	Creator	Author's name, affiliation, country	Ruth J. Williams; University of California, San Diego
3.	Subject	Discipline(s)
3.	Subject	Keyword(s)
4.	Description	Abstract	We consider a parallel server queueing system consisting of a bank of buffers for holding incoming jobs and a bank of flexible servers for processing these jobs. Incoming jobs are classified into one of several different classes (or buffers). Jobs within a class are processed on a first-in-first-out basis, where the processing of a given job may be performed by any server from a given (class-dependent) subset of the bank of servers. The random service time of a job may depend on both its class and the server providing the service. Each job departs the system after receiving service from one server. The system manager seeks to minimize holding costs by dynamically scheduling waiting jobs to available servers. We consider a parameter regime in which the system satisfies both a heavy traffic and a complete resource pooling condition. Our cost function is an expected cumulative discounted cost of holding jobs in the system, where the (undiscounted) cost per unit time is a linear function of normalized (with heavy traffic scaling) queue length. In a prior work, the second author proposed a continuous review threshold control policy for use in such a parallel server system. This policy was advanced as an "interpretation" of the analytic solution to an associated Brownian control problem (formal heavy traffic diffusion approximation). In this paper we show that the policy proposed previously is asymptotically optimal in the heavy traffic limit and that the limiting cost is the same as the optimal cost in the Brownian control problem.
5.	Publisher	Organizing agency, location
6.	Contributor	Sponsor(s)
7.	Date	(YYYY-MM-DD)	2005-09-07
8.	Type	Status & genre	Peer-reviewed Article
8.	Type	Type
9.	Format	File format	PDF
10.	Identifier	Uniform Resource Identifier	http://ejp.ejpecp.org/article/view/281
10.	Identifier	Digital Object Identifier	10.1214/EJP.v10-281
11.	Source	Journal/conference title; vol., no. (year)	Electronic Journal of Probability; Vol 10
12.	Language	English=en
14.	Coverage	Geo-spatial location, chronological period, research sample (gender, age, etc.)
15.	Rights	Copyright and permissions	The Electronic Journal of Probability applies the Creative Commons Attribution License (CCAL) to all articles we publish in this journal. Under the CCAL, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles published in EJP, so long as the original authors and source are credited. This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available. Summary of the Creative Commons Attribution License You are free to copy, distribute, display, and perform the work to make derivative works to make commercial use of the work under the following condition of Attribution: others must attribute the work if displayed on the web or stored in any electronic archive by making a link back to the website of EJP via its Digital Object Identifier (DOI), or if published in other media by acknowledging prior publication in this Journal with a precise citation including the DOI. For any further reuse or distribution, the same terms apply. Any of these conditions can be waived by permission of the Corresponding Author.