Two-phase scheduling with unknown speeds

• Thesis title in Czech: Dvoufázové rozvrhování s neznámými rychlostmi
• Thesis title in English: Two-phase scheduling with unknown speeds
• Key words: rozvrhování|aproximační algoritmy|délka rozvrhu|uniformní rychlosti
• English key words: scheduling|approximation algorithms|makespan|uniform speeds
• Academic year of topic announcement: 2023/2024
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: prof. RNDr. Jiří Sgall, DrSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 30.10.2023
• Date of assignment: 30.10.2023
• Confirmed by Study dept. on: 04.11.2023
• Date and time of defence: 16.02.2024 09:00
• Date of electronic submission: 10.01.2024
• Date of submission of printed version: 10.01.2024
• Date of proceeded defence: 16.02.2024
• Opponents: Franziska Eberle

Guidelines

Práce podá přehled výsledků pro dvoufázové rozvrhování úloh na strojích s neznámými rychlostmi, který byl řešen v uvedených článcích. Pokusí se získat nové odhady aproximačního poměru zejména v případech, kdy počet "balíčků" v první fázi je různý od počtu strojů.

References

Aktuální a přehledové články včetně:

Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, Bertrand Simon:
Speed-robust scheduling: sand, bricks, and rocks. Math. Program. 197(2): 1009-1048 (2023)

Clifford Stein, Mingxian Zhong:
Scheduling When You Do Not Know the Number of Machines. ACM Trans. Algorithms 16(1): 9:1-9:20 (2020)

Kirk Pruhs, Jiří Sgall, Eric Torng:
Online Scheduling. Handbook of Scheduling 2004