Access Restriction

Author Scharbrodt, Mark ♦ Schickinger, Thomas ♦ Steger, Angelika
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2006
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Scheduling theory ♦ Average case analysis
Abstract We present a new average case analysis for the problem of scheduling $\textit{n}$ jobs on $\textit{m}$ machines so that the sum of job completion times is minimized. Our goal is to use the concept of competitive ratio---which is a typical worst case notion---also within an average case analysis. We show that the classic SEPT scheduling strategy with $Ω(\textit{n})$ worst-case competitive ratio achieves an average of O(1) under several natural distributions, among them the exponential distribution. Our analysis technique allows to also roughly estimate the probability distribution of the competitive ratio. Thus, our result bridges the gap between worst case and average case performance guarantee.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2006-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 53
Issue Number 1
Page Count 26
Starting Page 121
Ending Page 146

Open content in new tab

   Open content in new tab
Source: ACM Digital Library