### A new average case analysis for completion time schedulingA new average case analysis for completion time scheduling

Access Restriction
Subscribed

 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

Source: ACM Digital Library