On the average sojourn time under M/M/1/SRPT

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the average sojourn time under M/M/1/SRPT

Full text

Pdf (152 KB)

Source

ACM SIGMETRICS Performance Evaluation Review archive
Volume 31 , Issue 2 (September 2003) table of contents
Special issue on the fifth workshop on MAthematical performance Modeling and Analysis (MAMA 2003)

Pages: 34 - 35

Year of Publication: 2003

ISSN:0163-5999

Author

Nikhil Bansal

Carnegie Mellon University, Pittsburgh, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 12, Citation Count: 0

Additional Information:

abstract references collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/959143.959164 What is a DOI?

ABSTRACT

We consider an M/M/1 queueing system under the Shortest Remaining Processing Time (SRPT) policy. We show that there are constants c_l and c₂ such the average sojourn time under SRPT lies between c_l (μ(1 - ρ) log 1/(1 - ρ))^-1 and c₂ (μ(l - ρ) log 1/(1 - ρ))^-1, where μ denotes the service rate and ρ denotes the load. Comparing this with the classic result that any scheduling policy that does not use the knowledge of job sizes has average sojourn time (μ(1-ρ))^-1, implies that SRPT offers a non-constant improvement over such policies.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. W. Conway, W. L. Maxwell, and L. W. Miller. Theory of Scheduling. Addison-Wesley Publishing Company, 1967.
	2	L. E. Schrage. A proof of the optimality of the shortest processing remaining time discipline. Operations Research, 16:678--690, 1968.
	3	L. E. Schrage and L. W. Miller. The queue M/G/1 with the shortest processing remaining time discipline. Operations Research, 14:670--684, 1966.

Collaborative Colleagues:

Nikhil Bansal: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player