We investigate the best possible average sojourn time achievable under policies that do not make use of job sizes n their scheduling decisions (blind scheduling policies). Our main result is that for a single server GI/GI/1 queueing system, the average sojourn tome under the best blind policy is at most log e/(1-p) time worse (upto constant factors) than the best average sojourn time possible under any arbitrary policy. Here p is the system load. Thus in a sense, the lack of knowledge of actual job sizes while making the scheduling decisions does not pose a serious problem if the blind policy is chosen carefully.
Our result makes us of previous results in the area of competitive analysis of online scheduling algorithms. Our main contribution is to show how these results can be used together with a game theoretic result known as Yao's Minimax Theorem to obtain almost tight results about queueing systems in fairly general setting such as a GI/GI/1 system.
By: Nikhil Bansal
Published in: RC23296 in 2004
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .