MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling. We study competitive on-line scheduling in multiprocessor real-time environments. In our model, every task has a deadline and a value that it obtains only if it completes by its deadline. A task can be assigned to any processor, all of which are equally powerful. The problem is to design an on-line scheduling algorithm (i.e. one in which the scheduler has no knowledge of a task unit it is released) with worst-case guarantees as to the total value obtained by the system. We study systems with two or more processors. We present an inherent limit on the best competitive guarantee that any on-line parallel real-time scheduler can give. Then we present a competitive algorithm that achieves a worst-case guarantee which is within a small factor from the best possible guarantee in many cases. These are the most general results yet known for competitive scheduling of multiprocessor real-time systems. (Source:

References in zbMATH (referenced in 17 articles , 1 standard article )

Showing results 1 to 17 of 17.
Sorted by year (citations)

  1. Devadas, Vinay; Li, Fei; Aydin, Hakan: Competitive analysis of online real-time scheduling algorithms under hard energy constraint (2010)
  2. Fung, Stanley P.Y.; Poon, Chung Keung; Zheng, Feifeng: Online interval scheduling: Randomized and multiprocessor cases (2008)
  3. Lam, Tak-Wah; Lee, Lap-Kei; To, Isaac K.K.; Wong, Prudence W.H.: Energy efficient deadline scheduling in two processor systems (2007)
  4. Koo, Chiu-Yuen; Lam, Tak-Wah; Ngan, Tsuen-Wan Johnny; To, Kar-Keung: Extra processors versus future information in optimal deadline scheduling (2004)
  5. Lam, Tak-Wah; Ngan, Tsuen-Wan Johnny; To, Kar-Keung: Performance guarantee for EDF under overload (2004)
  6. Lam, Tak Wah; Ngan, Tsuen-Wan; To, Kar-Keung; Wong, Prudence W.H.: Aggressive online deadline scheduling. (2004)
  7. Leung, Joseph Y.-T.: Improved competitive algorithms for two-processor real-time systems (2004)
  8. Miyazawa, Hiroyuki; Erlebach, Thomas: An improved randomized on-line algorithm for a weighted interval selection problem (2004)
  9. Koo, Chiu-Yuen; Lam, Tak-Wah; Ngan, Tsuen-Wan; To, Kar-Keung: Competitive deadline scheduling via additional or faster processors (2003)
  10. Phillips, C.A.; Stein, C.; Torng, E.; Wein, J.: Optimal time-critical scheduling via resource augmentation (2002)
  11. Lam, Tak-Wah; To, Kar-Keung: Performance guarantee for online deadline scheduling in the presence of overload (2001)
  12. Becchetti, Luca; Leonardi, Stefano; Muthukrishnan, S.: Scheduling to minimize average stretch without migration (2000)
  13. Koren, Gilad; Dar, Emanuel; Amir, Amihood: The power of migration in multiprocessor scheduling of real-time systems (2000)
  14. Kwon, Oh-Heum; Chwa, Kyung-Yong: Scheduling parallel tasks with individual deadlines (1999)
  15. Lam, Tak Wah; To, Kar Keung: Trade-offs between speed and processor in hard-deadline scheduling (1999)
  16. Canetti, Ran; Irani, Sandy: Bounding the power of preemption in randomized scheduling (1998)
  17. Koren, Gilad; Shasha, Dennis: MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling (1994)