This thesis presents results of our research in the area of optimization problems with incomplete information-our research is focused on the online scheduling problems. Our research is based on the worst-case analysis of studied problems and algorithms; thus we use methods of the competitive analysis during our research.

Althrough there are many "real-world" industrial and theoretical applications of the online scheduling problems there are still so many open problems with so simple description. Therefore it is important, interesting and also challenging to study the online scheduling problems and their simplified variants as well.

In this thesis we have shown the following our results of our research on the online scheduling problems:

• A 1.58-competitive online algorithm for the problem of randomized scheduling of unit jobs on a single processor, where the jobs are arriving over time and the total weight of processed jobs is maximized.
• A lower bound 1.172 on the competitive ratio for the problem of randomized scheduling of 2-uniform unit jobs on a single processor, where the jobs are arriving over time and the total weight of processed jobs is maximized.
• A lower bound 1.25 on the competitive ratio for the problem of randomized scheduling of s-uniform unit jobs on a single processor where s is tending to infinity, the jobs are arriving over time and the total weight of processed jobs is maximized.
• A 1.5-competitive online algorithm for the problem of deterministic scheduling of equal-length jobs on a single processor, where restarts of jobs are allowed, the jobs are arriving over time and the total weight of processed jobs is maximized.
• There is no online 1-competitive algorithm with speed-up s <; 2 for the problem of deterministic scheduling of tight jobs on a single processor, where the preemptions of jobs are allowed, the jobs are arriving over time and the total weight of processed jobs is maximized.
• There is no 1-competitive k-relaxed online algorithm for any k for the problem of deterministic scheduling of jobs arriving over time with maximizing total weight of processed jobs.
• A lower bound 1.05099 on the competitive ratio for the problem of 1-relaxed deterministic scheduling of jobs arriving over time with maximizing total weight of processed jobs. We have shown a generalized lower bound for k-relaxed algorithms.

We present also some other results related to studied problems that are products of a joint work with other researchers.

Práce prezentuje výsledky našeho výzkumu v oblasti optimalizačních problémů s neúplnou informací-náš výzkum je zaměřený na online rozvrhovací problémy. Náš výzkum je založený na principu analýzy nejhorších případů ve studovaných problémech a algoritmech, tedy v našem výzkumu používáme metody kompetitivní analýzy.

Mnoho online rozvrhovacích problémů, které mají "realné" průmyslové či teoretické aplikace, jsou stále nevyřešené ačkoliv mají tak jednoduchý popis problému. Proto je tak důležité, zajímavé a vyzývavé studium online rozvrhovacích problémů a zrovna tak jejich zjednodušených variant.

V disertační práci jsme dokázali následující výsledky našeho výzkumu online rozvrhovacích problémů:

• 1.58-kompetitivní online algoritmus pro problém randomizovaného rozvrhování jednotkových úkolů na jednom procesoru, kde úkoly přicházejí v čase a cílem je maximalizovat celkovou váhu zpracovaných úkolů.
• Dolní odhad 1.172 kompetitivního poměru pro problém randomizovaného rozvrhování 2-uniformních jednotkových úkolů na jednom procesoru, kde úkoly přicházejí v čase a cílem je maximalizovat celkovou váhu zpracovaných úkolů.
• Dolní odhad 1.25 na kompetitivní poměr pro problém randomizovaného rozvrhování s-uniformních jednotkových úkolů na jednom procesoru, kde s jde do nekonečna. Úkoly přicházejí v čase a cílem je maximalizovat celkovou váhu všech zpracovaných úkolů.
• 1.5-kompetitivní online algoritmus pro problém deterministického rozvrhování stejně dlouhých úkolů na jednom procesoru. Zpracování úkolů je povoleno přerušit a restartovat. Úkoly přicházejí v čase a cílem je maximalizovat celkovou váhu zpracovaných úkolů.
• Neexistuje žádný 1-kompetitivní online algoritmus se s-násobným zrychlením pro s < 2 pro problém deterministického rozvrhování těsných úkolů na jednom procesoru. Přerušení zpracování úkolů je povoleno. Úkoly přicházejí v čase a cílem je maximalizovat celkovou váhu zpracovaných úkolů.
• Neexistuje žádný 1-kompetitivní k-relaxed online algoritmus for libovolné k pro problém deterministického rozvrhování úkolů přicházejících v čase s cílem maximalizovat celkovou váhu zpracovaných úkolů.
• Dolní odhad 1.05099 na kompetitivní poměr problému 1-relaxed deterministického rozvrhování úkolů přicházejících v čase s cílem maximalizovat celkovou váhu zpracovaných úkolů. Toto je zároveň dolní odhad pro obecný k-relaxed algoritmy.

V práci prezentujeme i několik dalších výsledků výzkumu studovaných problémů, které jsou výsledkem společného výzkumu s kolegy.