Improved algorithms for stretch scheduling

ABSTRACT

We study the basic problem of preemptive scheduling of an online stream of jobs on a single processor. The ith job arrives at time r(i) and has processing time p(i) that is known at the time of its arrival. If C(i) is the completion time of job i, then the flow time is C(i) - r(i) and stretch of a job is the ratio of its flow time to its processing time; that is, C(i)-r(i)/p(i). Flow time considers the time a job is in the system regardless of the service it requested; the stretch measure relies on the intuition that a job that requested long service must be prepared to wait longer than the small jobs.In this paper, we present improved algorithmic results in stretch scheduling. We first show that a simple online algorithm that takes amortized O(1) time per job arrival is O(Δ^1/2)-competitive with respect to maximum stretch, where Δ is the ratio of the largest processing time to the smallest processing time. This is significantly more efficient than the best known online algorithm for this problem which takes ω(n²) per scheduling step (n is the number of jobs seen thus far). We next present a polynomial time approximation scheme for average stretch scheduling. The previous best polynomial-time algorithm is the shortest remaining processing time algorithm, which achieves a 2-approximation. Finally, we consider the impact of incomplete knowledge of job sizes on the average stretch performance of scheduling algorithms. We show that a constant-factor competitive ratio for average stretch is achievable even if the processing times (or remaining processing times) of jobs are known only to within a constant factor of accuracy.

REFERENCES

• 1: Swarup Acharya , S. Muthukrishnan, Scheduling on-demand broadcasts: new metrics and algorithms, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.43-54, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288248]
• 2: Foto Afrati , Evripidis Bampis , Chandra Chekuri , David Karger , Claire Kenyon , Sanjeev Khanna , Ioannis Milis , Maurice Queyranne , Martin Skutella , Cliff Stein , Maxim Sviridenko, Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.32, October 17-18, 1999
• 3: Hannah Bast, Dynamic scheduling with incomplete information, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.182-191, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277684]
• 4: H. Bast. On scheduling parallel tasks at twilight. Theory of Computing Systems, 33(5/6):489-563, 2000.
• 5: Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
• 6: M. Bender, S. Muthukrishnan, and R. Rajaraman. Improved algorithms for stretch scheduling. Technical report NU-CCS-01-07, Northeastern University, October 2001.
• 7: Chandra Chekuri , Sanjeev Khanna , An Zhu, Algorithms for minimizing weighted flow time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.84-93, July 2001, Hersonissos, Greece [doi>10.1145/380752.380778]
• 8: C. Chekuri and S. Khanna. Approximation schemes for preemptive weighted flow time. Manuscript, April 2001.
• 9: M. Crovella, R. Frangioso, and M. Harchol-Balter. Connection scheduling in web servers. Proceedings of the USENIX Symposium on Internet Technologies and Systems, 1999.
• 10: Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
• 11: Ashish Goel , Monika R. Henzinger , Serge Plotkin , Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.189-197, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301300]
• 12: Mor Harchol-Balter , Mark E. Crovella , Cristina D. Murta, On choosing a task assignment policy for a distributed server system, Journal of Parallel and Distributed Computing, v.59 n.2, p.204-228, Nov. 1999 [doi>10.1006/jpdc.1999.1577]
• 13: Niranjan Joshi , Srinivas R. Kadaba , Sarvar Patel , Ganapathy S. Sundaram, Downlink scheduling in CDMA data networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.179-190, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345941]
• 14: B. Kalyanasundaram , K. R. Pruhs, Minimizing flow time nonclairvoyantly, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.345, October 19-22, 1997
• 15: Bala Kalyanasundaram , Kirk Pruhs , Mahendran Velauthapillai, Scheduling Broadcasts in Wireless Networks, Proceedings of the 8th Annual European Symposium on Algorithms, p.290-301, September 05-08, 2000
• 16: Stefano Leonardi , Danny Raz, Approximating total flow time on parallel machines, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.110-119, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258562]
• 17: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1]
• 18: S. Muthukrishnan , Rajmohan Rajaraman , Anthony Shaheen , Johannes E. Gehrke, Online Scheduling to Minimize Average Stretch, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.433, October 17-18, 1999
• 19: Mikkel Thorup, On RAM priority queues, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.59-67, January 28-30, 1996, Atlanta, Georgia, United States