ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Eliminating migration in multi-processor scheduling
Full text PdfPdf (921 KB)
Source Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents
Baltimore, Maryland, United States
Pages: 499 - 506  
Year of Publication: 1999
ISBN:0-89871-434-6
Authors
Bala Kalyanasundaram  Dept. of Computer Science, University of Pittsburgh
Kirk R. Pruhs  Dept. of Computer Science, University of Pittsburgh
Sponsors
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics
Publisher
Society for Industrial and Applied Mathematics  Philadelphia, PA, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 15,   Citation Count: 3
Additional Information:

references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Review this Article  

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
S. Baruah, J. Harita, and iN. Sharma, "On-line scheduling to maximize task completions", IEEE Real-time Systems Symposium, 1994.
 
2
S. Baruah , G. Koren , D. Mao , B. Mishra , A. Raghunathan , L. Rosier , D. Shasha , F. Wang, On the competitiveness of on-line real-time task scheduling, Real-Time Systems, v.4 n.2, p.125-144, May 1992  [doi>10.1007/BF00365406]
 
3
Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
 
4
Peter Brucker, Scheduling Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 1995
 
5
P. Brucker, J. Hurink, S. Knust, "Complexity results of scheduling problems", http://www.mathematik.uniosnabrueck.de/research/OR/class.
 
6
K. Christian and K. Pruhs, private communication.
 
7
M. L. Dertouzos , A. K. Mok, Multiprocessor Online Scheduling of Hard-Real-Time Tasks, IEEE Transactions on Software Engineering, v.15 n.12, p.1497-1506, December 1989  [doi>10.1109/32.58762]
 
8
B. Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance [scheduling problems], Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.214, October 23-25, 1995
 
9
B. Kalyanasundaram and K. Pruhs "Randomized algorithms for real-time scheduling with fault-tolerance", Technical report, Computer Science Department, University of Pittsburgh, 1994.
 
10
Bala Kalyanasundaram , Kirk Pruhs, Maximizing Job Completions Online, Proceedings of the 6th Annual European Symposium on Algorithms, p.235-246, August 24-26, 1998
 
11
Gilad Koren , Amihood Amir , Emanuel Dar, The power of migration in multi-processor scheduling of real-time systems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.226-235, January 25-27, 1998, San Francisco, California, United States
 
12
Gilad Koren , Dennis Shasha, MOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling, Theoretical Computer Science, v.128 n.1-2, p.75-97, June 6, 1994  [doi>10.1016/0304-3975(94)90165-1]
 
13
E. L. Lawler, A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs, Annals of Operations Research, v.26 n.1-4, p.125-133, Dec. 1990  [doi>10.1007/BF02248588]
14
Cynthia A. Phillips , Cliff Stein , Eric Torng , Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1997, El Paso, Texas, United States  [doi>10.1145/258533.258570]
 
15
Gerhard J. Woeginger, On-line scheduling of jobs with fixed start and end times, Theoretical Computer Science, v.130 n.1, p.5-16, Aug. 1, 1994  [doi>10.1016/0304-3975(94)90150-3]

CITED BY  3
Chiu-Yuen Koo , Tak-Wah Lam , Tsuen-Wan Ngan , Kar-Keung To, Extra processors versus future information in optimal deadline scheduling, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
Stefano Leonardi , Alberto Marchetti-Spaccamela , Friedhelm Meyer auf der Heide, Scheduling against an adversarial network, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
 
Luca Becchetti , Stefano Leonardi , S. Muthukrishnan, Scheduling to minimize average stretch without migration, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.548-557, January 09-11, 2000, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling


General Terms:
Algorithms, Design, Performance, Theory, Verification

Collaborative Colleagues:
Bala Kalyanasundaram: colleagues
Kirk R. Pruhs: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player