Online scheduling of multiprocessor jobs with preemption

• Thesis title in Czech: Online rozvrhování víceprocesorových úloh s preempcí
• Thesis title in English: Online scheduling of multiprocessor jobs with preemption
• Key words: rozvrhování, online algoritmy, preempce, paralelní úlohy
• English key words: scheduling, online algorithms, preemption, multiprocessor jobs
• Academic year of topic announcement: 2017/2018
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: prof. RNDr. Jiří Sgall, DrSc.
• Author: Mgr. Štěpán Šimsa - assigned and confirmed by the Study Dept.
• Date of registration: 30.05.2018
• Date of assignment: 30.05.2018
• Confirmed by Study dept. on: 20.07.2018
• Date and time of defence: 18.09.2018 00:00
• Date of electronic submission: 20.07.2018
• Date of submission of printed version: 20.07.2018
• Date of proceeded defence: 18.09.2018
• Opponents: doc. Mgr. Petr Kolman, Ph.D.

Guidelines

Práce podá ucelený přehled výsledků pro rozvrhování paralelních úloh, který byl řešen v uvedených článcích. Pokusí se získat nové dolní a horní odhady kompetitivního poměru v některých konkrétních případech, např. pro 4 paralelní počítače.

References

Aktuální články, včetně

J. Sgall, G. J. Woeginger: Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms
In Proc. of the 12th Workshop on Approximation and Online Algorithms (WAOA 2014), Lecture Notes in Comput. Sci. 8952, pages 236-247, Springer, 2015.

K.S. Hong and J.Y.-T. Leung. On-line scheduling of real-time tasks. IEEE Transactions on Computers 41, 1326-1331, 1992.

B. Johannes. Scheduling parallel jobs to minimize the makespan. Journal of Scheduling 9, 433-452, 2006.