Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-25T06:06:34.080Z Has data issue: false hasContentIssue false

OPTIMAL CONTROL OF PARALLEL QUEUES WITH BATCH SERVICE

Published online by Cambridge University Press:  22 May 2002

Cathy H. Xia
Affiliation:
IBM T.J. Watson Research Center, Yorktown, NY 10598, E-mail: [email protected]
George Michailidis
Affiliation:
Department of Statistics, University of Michigan, Ann Arbor, MI, E-mail: [email protected]
Nicholas Bambos
Affiliation:
Departments of Electrical Engineering and, Management Science & Engineering, Stanford University, Stanford, CA, E-mail: [email protected]
Peter W. Glynn
Affiliation:
Department of Management Science & Engineering, Stanford University, Stanford, CA, E-mail: [email protected]

Abstract

We consider the problem of dynamic allocation of a single server with batch processing capability to a set of parallel queues. Jobs from different classes cannot be processed together in the same batch. The arrival processes are mutually independent Poisson flows with equal rates. Batches have independent and identically distributed exponentially distributed service times, independent of the batch size and the arrival processes. It is shown that for the case of infinite buffers, allocating the server to the longest queue, stochastically maximizes the aggregate throughput of the system. For the case of equal-size finite buffers the same policy stochastically minimizes the loss of jobs due to buffer overflows. Finally, for the case of unequal-size buffers, a threshold-type policy is identified through an extensive simulation study and shown to consistently outperform other conventional policies. The good performance of the proposed threshold policy is confirmed in the heavy-traffic regime using a fluid model.

Type
Research Article
Copyright
© 2002 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)