BSc Matematika Alapszak
Tantárgyleírás
2013.
Borromeo gyűrűk
Ü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
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.
↻