Az alábbi plussz feladatokat lehet megoldani. Mindenki válasszon valamit és írja meg április 10-ig mit szeretne csinálni (legfeljebb 5 feladat prioritás szerint). Ha valakinek olyan szoftvert vagy cikket szeretne feldolgozni, ami nem szerepel a listán arra is van lehetőség ez esetben annak az adatait küldje el. Utána az esetleges egyezések feloldása után ki lesznek osztva a feladatok. Aki változtatni akar vagy késve jelentkezik, az csak a megmaradó feladatokra teheti meg.

Szoftver ismertetés

Az alábbi szoftverek valamelyikének működését kell áttekinteni, a programmról a félév utolsó előadásán, rövid kb 20 perces ismertetést kell tartani a többieknek.

• SZ1. LISA honlap
• SZ2. LEKIN honlap
• SZ3. S-graph megoldó honlap
• SZ4. TORSCHE Scheduling Toolbox for Matlab honlap

Elméleti cikk feldolgozása

Az alábbi cikkek valamelyikét kell megérteni és feldolgozni. Egy 2-3 oldalas összefoglalást kell megkapjak félév végéig, amiben a cikkben szereplő bizonyítások egyikének alapötletére is kell legyen utalás. A vizsgán a feldolgozott cikk is szóba kerül.

• C1. Adonyi, R., G. Biros, T. Holczinger, and F. Friedler, Effective scheduling of a large-scale paint production system, Journal of Cleaner Production, 16 (2), 225-232 (2008). cikk
• C2. U. Aickelin. P. White, Building Better Nurse Scheduling Algorithms, Annals of Operations Research, 128, pp 159-177, 2004. cikk
• C3. S. Albers and Tobias Jacobs. An experimental study of new and known online packet buffering algorithms. In Proc. 15th Annual European Symposium on Algorithms (ESA'07), Springer LNCS 4698, 754-765,2007. cikk
• C4. S. Albers and B. Schröder. An experimental study of online scheduling algorithms. ACM Journal of Experimental Algorithmics, 7, 2002. cikk
• C5. M. Chrobak, M. Hurand, J. Sgall: Fast algorithms for testing fault-tolerance of sequenced jobs with deadlines J. Sched.,12(5):501-515, 2009. cikk
• C6. M. Chrobak, L. Epstein, J. Noga, J. Sgall, R. van Stee, T. Tichy, N. Vakhania: Preemptive scheduling in overloaded systems J. Comput. Syst. Sci., 67(1):183-197, 2003. cikk
• C7. Gy. Dosa, L. Epstein, Online scheduling with a buffer on related machines Journal of Combinatorial Optimization, 20(2), 161-179, 2010. cikk
• C8. Gy. Dosa, L. Epstein, Preemptive scheduling on a small number of hierarchical machines, Information and Computation, 206(5), 602-619, 2008. cikk
• C9. L. Epstein, R. van Stee Maximizing the minimum load for selfish agents Proc. of the 8th LATIN, 2008, 264-275. Also in Theoretical computer Science, 411(1), 44-57, 2010. cikk
• C10. L. He , S. A. Jarvis , D. P. Spooner , X. Chen, G. R. Nudd, Dynamic Scheduling of Parallel Jobs with QoS Demands in Multiclusters and Grids, roceedings of the 5th IEEE/ACM International Workshop on Grid Computing (Grid2004), pp.402-409 cikk
• J. Hurink, B. Jurisch, M. Thole, Tabu search for the job-shop scheduling problem with multi-purpose machines, OR Spektrum, 15:205-215, 1994 cikk
• Majozi, T. and F. Friedler, Maximization of Throughput in a Multipurpose Batch Plant Under Fixed Time Horizon: S-Graph Approach, Ind. Eng. Chem. Res., 45, 6713-6720 (2006). cikk
• M. Trick, A Schedule and Break Approach to Sports Scheduling cikk
• M. Trick, Integer and Constraint Programming Approaches to Sports Scheduling cikk
• S. Yu, P. Wong, Online Scheduling of Simple Linear Deteriorating Jobs to Minimize Total General Completion Time, accepted to Theoretical Computer Science, to appear. cikk
• O. Zajicek, J. Sgall, T. Ebenlendr: Online scheduling of parallel jobs on hypercubes: Maximizing the throughput Proc. of the Parallel Processing and Applied Mathematics (PPAM'09), Part II, Lecture Notes in Comput. Sci. 6068, pages 52-61, Springer, 2010. cikk

Program írása

Egy működőképes heurisztikus (szomszédsági kereső vagy genetikus) program implementálása az alábbi problémára. Félév végéig be kell adni a forrást (kommentezve), egy futattható változatot. A vizsgán a program is szóba kerül. Szakirodalom szabadon használható, de hivatkozni kell rá.

• Visszautasításos ütemezés 3 azonos gépre. Minden munkának van egy végrehajtási ideje és egy büntetése. A munkákat vissza lehet utasítani. A cél az elfogadott munkák maximális befejezési idejének és a visszautasított munkák büntetéseinek összegének minimalizálása.
• Az input specifikációja: Az első sor a munkák m számát tartalmazza. Ezután a következő m sor mindegyike két egész számot tartalmaz, egy munkaidőt, és egy büntetést. A program feltételezheti, hogy az input korrekt.
• Az output specifikációja: Az első sor a megoldás értékét tartalmazza. A következő sor az első gépre ütemezett munkák számát, illetve a gépre ütemezett munkák össztöltését tartalmazza. Az ezutáni sor az első gépre ütemezett munkákat tartalmazza idő, büntetés párok formájában. Az egyes munkák vesszővel vannak elválasztva. A következő 4 sor ugyanezeket tartalmazza a második és harmadik gépre. Az utolsó két sor a büntetésekre vonatkozik. Annyi az eltérés, hogy nem az össztöltés, hanem az összbüntetés van kiírva. Megjegyzés: Ha valamelyik gép üres, vagy nem utasítottunk vissza munkát, akkor a kérdéses helyen a munkák felsorolása egy üres sor lesz.
• A programnak egy percen belül megoldást kell adnia.
• A határidő május 5. A május 5-ig beérkezett programok egymással teszteken össze lesznek hasonlítva és három kategóriába sorolva 30, 26 és 22 pontot szerezhetnek. A május 5 után, de még szorgalmi időszak vége előtt érkező programok minősétől függően 25 vagy 20 pontot érnek.

---