Leírás
Az előadáson bemutatok több, a doktorimhoz kapcsolódó eredményt. Olyan ütemezési feladatokat fogunk vizsgálni, ahol a munkák elvégzése ismert mennyiségű nem megújuló erőforrások meglétéhez kötött. Ezeket az eroforrásokat a munkák az ütemezésük pillanatában felhasználják. A kezdeti erőforrás készleteinkhez ismert időben és mennyiségben utánpótlások érkeznek.
Először bemutatom, hogy az egygépes, két utánpótlásos feladatnak a legkésőbbi befejezési idő (makespan) minimalizálása esetén milyen kapcsolata van a hátizsákfeladattal, továbbá milyen eredményekhez juthatunk ebből a kapcsolatból. Egygépes feladatok esetén szó lesz még néhány approximációs sémáról a makespan minimalizálása esetén, továbbá egy 2-approximációról, amennyiben a befejezési idők súlyozott összegét szeretnénk minimalizálni egy speciális esetben. Az egygépes eredményeket egy korlátozás és vágás alapú egzakt algoritmussal zárjuk. Az előadás utolsó részében megnézzük, hogy az elért approximációs eredmények milyen esetekben terjeszthetőek ki párhuzamos gépek esetére.
Az elért eredmények nagyrésze Kis Tamással közös.