Tárgyfelelős: Dósa György, MTA doktora (dosa.gyorgy@mik.uni-pannon.hu)
Tematika:
Ütemezési feladatok
- Ütemezési modellek, approximációs algoritmusok, hatékonyságbecslés
- Approximációs sémák
- Online ütemezés. Alsó korlát konstrukciók, kompetitív algoritmusok, versenyképességi arány
- Félig online ütemezés, jelentősebb modellek, eredmények
Ládapakolási feladatok
- A klasszikus ládapakolási feladat
- “Fit” algoritmusok: Next Fit, First Fit, Best Fit, Worst Fit, Any Fit, Almos Any Fit
- Súlyfüggvény technika
- Approximációs sémák
- Online ládapakolás, alsó és felső korlátok (Harmonic-Fit típusú algoritmusok)
- Téglalap-pakolás, vektorpakolás, egyéb modellek
Irodalom:
Dósa Gy., Imreh Cs. Online algoritmusok, Elektronikus jegyzet, Typotex Kiadó, 2011, ISBN 9789632795089
Chen B., Potts C. N., Woeginger G. A review of machine scheduling: Complexity, algorithms and approximability. In Du D.-Z. and Pardalos P. M. (eds.), Handbook of Combinatorial Optimization, Kluwer Academic Publishers, 1998.
Sgall, J. On-line scheduling, in: On-line Algorithms: The State of Art, Lecture Notes in Computer Science 1442, Springer-Verlag, 196–231, 1998.
Tan Zhiyi, Zhang An, Online and Semi-online Scheduling, In: Pardalos Panos M, Du Ding-Zhu, Graham Ronald L (szerk.) : Handbook of Combinatorial Optimization. Springer New York, 2013. (ISBN 978-1-4419-7996-4) pp. 2191-2252.
Coffman E. G. Jr., Garey M. R., Johnson D. S. Approximation algorithms for bin packing: a survey, in: Hochbaum D. (ed.), Approximation algorithms. PWS Publ. Co., 1997.
Coffman E. G Jr., Csirik J., Galambos G., Martello S., Vigo D., Bin Packing Approximation Algorithms: Survey and Classification. In: Handbook of Combinatorial Optimization. Springer New York, 2013. (ISBN 978-1-4419-7996-4) pp. 455-531.