Galambos Gábor (SZTE): Páros munkák ütemezése

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, Cmax) minimalizáljuk.
• a munkákat nem lehet megszakítani.

Az i. munkát egy (ai,Li,bi) rendezett hármassal lehet leírni, ahol ai = az első művelet elvégzéséhez szükséges időtartam, Li = a két művelet közötti előírt követési idő, bi = a második művelet elvégzéséhez szükséges időtartam. ai,Li,bi é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 ai =a, bi = b, Li= L un. Identical Coupled of Task esetre egzakt algoritmust adunk egy gráfelméleti modell segítségével.
• Az Az ai = bi = 1, Li 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 (ai,Li,bi) 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 tekinthetik meg.