BSc Matematika Alapszak
Tantárgyleírás
2013.
Tantárgyleírás
2013.
Ütemezéselmélet
Óraszám ea/gy |
Kredit ea/gy |
Számonkérés | Szakirány | Tárgykód ea/gy |
Ajánlott félév |
Státusz |
---|---|---|---|---|---|---|
2 + 0 | 2 + 0 | kollokvium | elemző | mm1c1ue5e | 5 | köt. vál |
Tantárgyfelelős
Erős | Gyenge | előfeltételek | |
---|---|---|---|
Előadás | |||
Erős:
Matematika kritériumtárgyG
(mm1c2bm1)
|
Megjegyzések
- A Véges matematika1,2 és az Operációkutatás előzetes hallgatása ajánlott.
A tematikát kidolgozta:
Szükséges előismeretek
Lineáris programozás és a gráfelmélet alapfogalmai.
A tantárgy célkitűzése
Ütemezési feladatok matematikai modelljeinek kidolgozása és az alapvető megoldási módszerek áttekintése.
Irodalom
- Jordán Tibor: Ütemezés. Jegyzet.
- Vizvári Béla: Bevezetés a termelésirányítás matematikai elméletébe. ELTE jegyzet, 1994.
Tematika
- Az ütemezés alapfogalmai, probléma típusok, jelölések, Gantt diagram. Egygépes ütemezési feladatok: SPT és EDD sorrend, Hodgson algoritmusa, LCL szabály, dinamikus programozás, LP relaxáció, közelítő algoritmusok.
- Ütemezés párhuzamos gépeken: listás ütemezés, LPT sorrend, Hu algoritmusa. Megszakítható eset, McNaughton algoritmusa, megoldás hálózati folyamokkal. Egységnyi munkák két gépen megelőzési feltételekkel. Többgépes ütemezés, optimális megoldás a megszakítható esetekre, közelítő algoritmus SCT sorrenddel és LP relaxációval. Minimális súlyú párosítás feladat.
- Shop modellek: Johnson algoritmusa, órarendkészítés, páros gráfok élszínezése. Branch and bound heurisztika flow shop és open shop feladatokra. Optimális megoldás a job shop feladatra két munka vagy két gép esetén. A ládapakolási feladat.