Algoritmy pro rozvrhování s konflikty

• Název práce v češtině: Algoritmy pro rozvrhování s konflikty
• Název v anglickém jazyce: Algorithms for scheduling with conflicts
• Akademický rok vypsání: 2005/2006
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. RNDr. Jiří Sgall, DrSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 10.11.2005
• Datum zadání: 10.11.2005
• Datum a čas obhajoby: 11.09.2006 00:00
• Datum odevzdání elektronické podoby: 11.09.2006
• Datum odevzdání tištěné podoby: 11.09.2006
• Datum proběhlé obhajoby: 11.09.2006
• Oponenti: prof. RNDr. Ondřej Čepek, Ph.D.

Zásady pro vypracování

Práce se bude zabývat problémy rozvrhování na více počítačích s konflikty.

Zaměří se zejména na model rozvrhování bufferů popsaný v práci Chrobak et al. V této variantě on-line rozvrhování je dán graf, který udává konflikty procesorů, tj. množina procesorů pracujících současně musí být nezávislá v tomto grafu. Předpokládá se, že úlohy přicházející na jednotlivé počítače mohou být uloženy v lokální frontě, a cílem je navrhnout takové on-line algoritmy, které nepotřebují o mnoho delší frontu než optimální řešení.

Cílem práce je navrhnout a analzyovat algoritmy pro konkrétní grafy konfliktů, jako jsou například cesty, případně další třídy grafů.

Seznam odborné literatury

M. Chrobak, J. Csirik, C. Imreh, J. Noga, J. Sgall, G. J. Woeginger
The buffer minimization problem for multiprocessor scheduling with conflicts
In Proc. of the 28th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Comput. Sci. 2076, pages 862-874, Springer, 2001.

A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998.

A. Fiat, G. Woeginger: Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998.