[Mat09] BME Optimalizálás Szeminárium

[Csilla Majoros]

*Meghívó*

Szeretettel várunk minden kedves érdeklődőt a BME
Optimalizálás Szemináriumán!


Az előadás részletei:

*április 30. (csütörtök), 14.15, H306*

*Galambos Gábor** (SZTE):*

Páros munkák ütemezése


*Absztrakt:*

Az előadásban tárgyalt probléma a következőképpen fogalmazható meg: Adott
*n* munka (job). Minden munka két különálló műveletből (task) áll össze, és
a műveletek sorrendje kötött. A két művelet között meghatározott hosszúságú
időnek (delay-time) kell eltelni. A feladat az, hogy az *n* darab munkát
hajtsuk végre egy gépen úgy, hogy

   -

   a munkák között átlapolás nem lehet
   -

   a teljes végrehajtási időt (makespan, *C**max*) minimalizáljuk.
   -

   a munkákat nem lehet megszakítani.

 Az *i.* munkát egy *(a**i**,L**i**,b**i**)* rendezett hármassal lehet
leírni, ahol *a**i* = az első művelet elvégzéséhez szükséges időtartam, * L*
*i* = a két művelet közötti előírt követési idő, * b**i* = a második
művelet elvégzéséhez szükséges időtartam. *a**i**,L**i**,b**i *értékeitől
függően különböző bonyolultságú feladatok vizsgálhatók, azonban ezek
legtöbbje NP-teljes.

Az előadásban három speciális esetet vizsgálunk:

   -

   Az *a**i** =a, b**i** = b, L**i**= L* un. Identical Coupled of Task
   esetre egzakt algoritmust adunk egy gráfelméleti modell segítségével.
   -

   Az Az *a**i** = b**i** = 1, L**i* problémára egy algoritmust publikált
   Ageev és Baburin (2007), amelynek aszimptotikus viselkedésére egy javítást
   mutatunk meg.
   -

   Az általános esetet is vizsgáljuk. Az *(a**i**,L**i**,b**i**) *esetre
   megmutatjuk az ismertebb LP, IP algoritmusokat, és az általunk konstruált,
   tisztán kombinatórikus közelítésre alapozott Branch and Bound algoritmus
   ismertetése után összehasonlítjuk ezen algoritmusok hatékonyságát.

Az előadás eredményeiben a társszerzők: Békési József (SZTE JGYPK), Dino
Ahr, Michael Jung , Marcus Oswald, Gerhard Reinelt (Uni. Heidelberg).



A félév további programját itt
<http://www.math.bme.hu/diffe/szeminarium/opt.shtml> tekinthetik meg.


Üdvözlettel,

Majoros Csilla
--------- következő rész ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: <http://lists.math.bme.hu/pipermail/mat09/attachments/20150428/08214925/attachment.html>