Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T11:57:13.272Z Has data issue: false hasContentIssue false

A conservation law for single-server queues and its applications

Published online by Cambridge University Press:  14 July 2016

Genji Yamazaki*
Affiliation:
Tokyo Metropolitan Institute of Technology
Hirotaka Sakasegawa*
Affiliation:
University of Tsukuba
J. George Shanthikumar*
Affiliation:
University of California, Berkeley
*
∗ Postal address: Department of Engineering Management, Tokyo Metropolitan Institute of Technology, Hino-city, Tokyo 191, Japan.
∗∗ Postal address: Institute of Socio-Economic Planning, University of Tsukuba, Tsukuba City, Ibaraki 305, Japan.
∗∗∗ Postal address: School of Business Administration, University of California, Berkeley, CA 94720, USA.

Abstract

We establish a conservation law for G/G/1 queues with any work-conserving service discipline using the equilibrium equations, also called the basic equations. We use this conservation law to prove an extremal property of the first-come firstserved (FCFS) service discipline: among all service disciplines that are work-conserving and independent of remaining service requirements for individual customers, the FCFS service discipline minimizes [maximizes] the mean sojourn time in a G/G/1 queue with independent (but not necessarily identical) service times with a common mean and new better [worse] than used (NBUE[NWUE]) distributions. This extends recent results of Halfin and Whitt (1990), Righter et al. (1990) and Yamazaki and Sakasegawa (1987a,b). In addition we use the conservation law to obtain an approximation for the mean queue length in a GI/GI/1 queue under the processor-sharing service discipline with finite degree of multiplicity, called LiPS discipline. Several numerical examples are presented which support the practical usefulness of the proposed approximation.

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 1991 

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.)

Article purchase

Temporarily unavailable