<div dir="ltr"><div dir="ltr"><div style="font-size:12.8000001907349px;text-align:center"><font size="4"><b>Meghívó</b></font><br></div><font size="4" style="font-size:12.8000001907349px"><br></font><div style="font-size:12.8000001907349px"><div style="text-align:center">Szeretettel várunk minden kedves érdeklődőt a BME<br>Optimalizálás Szemináriumán!<br></div><br></div><div><div style="text-align:center"><span style="font-size:12.8000001907349px"><br></span></div><div style="text-align:center"><span style="font-size:12.8000001907349px">Az előadás részletei:</span></div><br></div><div style="text-align:center;font-size:12.8000001907349px"><span style="font-family:arial,helvetica,sans-serif"><i><b>április 30. (csütörtök), 14.15, H306</b></i><br></span></div><div style="text-align:center;font-size:12.8000001907349px"><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div style="text-align:center;font-size:12.8000001907349px"><span style="font-family:arial,helvetica,sans-serif"><i><b>Galambos Gábor</b></i></span><span style="font-family:arial,helvetica,sans-serif"><i><b> (SZTE):</b></i></span></div><div style="text-align:center;font-size:12.8000001907349px"><span style="font-family:arial,helvetica,sans-serif"><i><b><br></b></i></span></div><div style="text-align:center;font-size:12.8000001907349px"><span style="font-family:arial,helvetica,sans-serif;line-height:115%;font-size:small">Páros
munkák ütemezése</span></div><div style="text-align:center;font-size:12.8000001907349px"><span style="font-family:arial,helvetica,sans-serif;line-height:115%;font-size:small"><br></span></div><div style="font-size:12.8000001907349px"><span style="font-family:arial,helvetica,sans-serif"><b><span style="font-size:13px;font-weight:normal;vertical-align:baseline"><br></span></b><i><b><span style="font-size:13px;font-weight:normal;font-style:normal;vertical-align:baseline"></span></b></i></span><span style="font-family:arial,helvetica,sans-serif"><i><b><span style="font-size:13px;font-weight:normal;font-style:normal;vertical-align:baseline"><i><b>Absztrakt:</b></i></span></b></i></span><br></div>
        
        
        



        
        
        


<p lang="en-GB" class="" align="justify" style="margin-bottom:0in;line-height:100%">
<font face="arial, helvetica, sans-serif"><font><span lang="hu-HU">Az
előadásban tárgyalt probléma a következőképpen fogalmazható
meg: Adott </span></font><font><span lang="hu-HU"><i>n</i></span></font><font><span lang="hu-HU">
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 </span></font><font><span lang="hu-HU"><i>n</i></span></font><font><span lang="hu-HU">
darab munkát hajtsuk végre egy gépen úgy, hogy </span></font>
</font></p>
<ul>
        <li><p lang="en-GB" class="" style="margin-bottom:0in;line-height:100%">
         <font face="arial, helvetica, sans-serif"><span lang="hu-HU">a
        munkák között átlapolás nem lehet</span></font></p></li><li><p lang="en-GB" class="" style="margin-bottom:0in;line-height:100%"><font style="font-family:arial,helvetica,sans-serif;line-height:100%"><span lang="hu-HU">a
        teljes végrehajtási időt (</span></font><font style="font-family:arial,helvetica,sans-serif;line-height:100%"><span lang="en-US">makespan</span></font><font style="font-family:arial,helvetica,sans-serif;line-height:100%"><span lang="hu-HU">,
        </span></font><font style="font-family:arial,helvetica,sans-serif;line-height:100%"><span lang="en-US"><i>C</i></span></font><sub style="font-family:arial,helvetica,sans-serif;line-height:100%"><span lang="en-US"><i>max</i></span></sub><font style="font-family:arial,helvetica,sans-serif;line-height:100%"><span lang="en-US">)
        </span></font><font style="font-family:arial,helvetica,sans-serif;line-height:100%"><span lang="hu-HU">minimalizáljuk</span></font><font style="font-family:arial,helvetica,sans-serif;line-height:100%"><span lang="en-US">.</span></font></p></li><li><p lang="en-GB" class="" style="margin-bottom:0in;line-height:100%">
         <font face="arial, helvetica, sans-serif"><font><span lang="hu-HU">a
        munkákat nem lehet megszakítani</span></font><font><span lang="de-DE">.</span></font></font></p>
</li></ul>
<p lang="en-GB" class="" align="justify" style="margin-bottom:0.14in;line-height:100%">
<font face="arial, helvetica, sans-serif"><font><span lang="hu-HU">Az
</span></font><font><span lang="hu-HU"><i>i.</i></span></font><font><span lang="hu-HU">
munkát egy </span></font><font><span lang="hu-HU"><i>(a</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>,L</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>,b</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>)</i></span></font><font><span lang="hu-HU">
rendezett hármassal lehet leírni, ahol </span></font><font><span lang="hu-HU"><i>a</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU">
= az első művelet elvégzéséhez szükséges időtartam, </span></font><font><span lang="hu-HU"><i>
L</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU">
= a két művelet közötti előírt követési idő,  </span></font><font><span lang="hu-HU"><i>
b</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU">
= a második művelet elvégzéséhez szükséges időtartam.
</span></font><font><span lang="hu-HU"><i>a</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>,L</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>,b</i></span></font>_{<font><span lang="hu-HU"><i>i
</i></span></font>}<font><span lang="hu-HU">értékeitől
függően különböző bonyolultságú feladatok vizsgálhatók,
azonban ezek legtöbbje NP-teljes. </span></font>
</font></p>
<p lang="en-GB" class="" style="margin-bottom:0.14in;line-height:100%">
<font face="arial, helvetica, sans-serif"><span lang="hu-HU">Az
előadásban három speciális esetet vizsgálunk:</span></font></p>
<ul>
        <li><p lang="en-GB" align="justify" style="margin-bottom:0.14in;line-height:100%">
        <font face="arial, helvetica, sans-serif"><font><span lang="hu-HU">Az
        </span></font><font><span lang="hu-HU"><i>a</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>
        =a,  b</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>
        = b, L</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>=
        L</i></span></font><font><span lang="hu-HU">
        un. Identical Coupled of Task esetre egzakt algoritmust adunk egy
        gráfelméleti modell segítségével.</span></font></font></p>
        </li><li><p lang="en-GB" align="justify" style="margin-bottom:0.14in;line-height:100%">
        <font face="arial, helvetica, sans-serif"><font><span lang="hu-HU">Az
        Az </span></font><font><span lang="hu-HU"><i>a</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>
        = b</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>
        = 1, L</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU">
        problémára egy algoritmust publikált Ageev és Baburin (2007),
        amelynek aszimptotikus viselkedésére egy javítást mutatunk meg.</span></font></font></p>
        </li><li><p lang="en-GB" align="justify" style="margin-bottom:0.14in;line-height:100%">
        <font face="arial, helvetica, sans-serif"><font><span lang="hu-HU">Az
        általános esetet is vizsgáljuk. Az </span></font><font><span lang="hu-HU"><i>(a</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>,L</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>,b</i></span></font>_{<font><span lang="hu-HU"><i>i</i></span></font>}<font><span lang="hu-HU"><i>)
        </i></span></font><font><span lang="hu-HU">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.</span></font></font></p>
</li></ul>
<p lang="en-GB" class="" align="justify" style="margin-bottom:0in;line-height:150%"><font face="arial, helvetica, sans-serif"><span style="line-height:100%">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).</span><span style="line-height:normal"> </span></font><br></p><span style="text-align:justify"><font face="arial, helvetica, sans-serif"><br><br></font></span></div><div style="font-size:12.8000001907349px"><span style="text-align:justify"><font face="arial, helvetica, sans-serif"><br>A félév további programját </font></span><span style="text-align:justify"><font face="arial, helvetica, sans-serif"><font face="arial, helvetica, sans-serif"><a href="http://www.math.bme.hu/diffe/szeminarium/opt.shtml" target="_blank">itt</a></font> tekinthetik meg.<br></font></span></div><div dir="ltr" style="font-size:12.8000001907349px"><span style="text-align:justify"><font face="arial, helvetica, sans-serif"><br><br>Üdvözlettel,<br><br>Majoros Csilla</font></span></div></div>