Algoritmy pro rozvrhování s konflikty

• Thesis title in Czech: Algoritmy pro rozvrhování s konflikty
• Thesis title in English: Algorithms for scheduling with conflicts
• Academic year of topic announcement: 2005/2006
• Thesis type: diploma thesis
• Thesis language: čeština
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: prof. RNDr. Jiří Sgall, DrSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 10.11.2005
• Date of assignment: 10.11.2005
• Date and time of defence: 11.09.2006 00:00
• Date of electronic submission: 11.09.2006
• Date of submission of printed version: 11.09.2006
• Date of proceeded defence: 11.09.2006
• Opponents: prof. RNDr. Ondřej Čepek, Ph.D.

Guidelines

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

References

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.