Borromeo gyűrűk
BSc Matematika Alapszak
Tantárgyleírás
2020.

Ütemezéselmélet

  • Óraszám (ea+gy): 2 + 0
  • Specializáció: alk. mat.
  • Kredit (ea+gy): 3 + 0
  • Számonkérés: kollokvium
  • Tárgykód (ea, gy): utemez1e0_m17ea
  • Ajánlott félév: 5
  • Státusz: köt. vál.
  • Specializáció: elemző
  • Kredit (ea+gy): 3 + 0
  • Számonkérés: kollokvium
  • Tárgykód (ea, gy): utemez1e0_m17ea
  • Ajánlott félév: 5
  • Státusz: köt. vál.
Óraszám
ea(+k) + gy(+k)
Kredit
ea + gy
Számonkérés Specializáció Tárgykód
ea/gy
Ajánlott
félév
Státusz
2 + 0 3 + 0 kollokvium alk. mat. utemez1e0_m17ea 5 köt. vál.
3 + 0 kollokvium elemző utemez1e0_m17ea 5 köt. vál.
Erős Gyenge előfeltételek
Előadás
Erős:
Matematika kritériumtárgyG (bevmat1x0_m17ga)

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.