Two-phase scheduling with unknown speeds

• Název práce v češtině: Dvoufázové rozvrhování s neznámými rychlostmi
• Název v anglickém jazyce: Two-phase scheduling with unknown speeds
• Klíčová slova: rozvrhování|aproximační algoritmy|délka rozvrhu|uniformní rychlosti
• Klíčová slova anglicky: scheduling|approximation algorithms|makespan|uniform speeds
• Akademický rok vypsání: 2023/2024
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: prof. RNDr. Jiří Sgall, DrSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 30.10.2023
• Datum zadání: 30.10.2023
• Datum potvrzení stud. oddělením: 04.11.2023
• Datum a čas obhajoby: 16.02.2024 09:00
• Datum odevzdání elektronické podoby: 10.01.2024
• Datum odevzdání tištěné podoby: 10.01.2024
• Datum proběhlé obhajoby: 16.02.2024
• Oponenti: Franziska Eberle

Zásady pro vypracování

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ů.

Seznam odborné literatury

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