Leírás
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 erőforrásokat a munkák az ütemezésük pillanatában felhasználják. A kezdeti erőforráskészleteinkhez ismert időben és mennyiségben utánpótlások érkeznek. A feladat már nagyon speciális esetben is NP-nehéz, így általában a célunk az lesz, hogy minél jobb approximációs algoritmust találjunk az egyes esetekre.
Az előadás során röviden áttekintem az eddig elért eredményeket, majd néhány konkrét feladatról beszélek részletesebben is. Szó lesz a makespan (az utoljára elvégzett munka befejezési ideje) minimalizálásáról párhuzamos gépek esetén, illetve a súlyozott befejezési idők összegének minimalizálásáról egy gép esetén. Az eredmények Kis Tamással közösek.