A nettó jelenérték maximalizálása erőforrás-korlátos projektekben - egy új harmóniakereső metaheurisztika (A harmony search metaheuristic for the resourceconstrainedproject scheduling problem with discountedcash flows)

摘要

Ebben a tanulmányban a szerző egy új harmóniakereső metaheurisztikát mutat be, amely a minimális időtartamúerőforrás-korlátos ütemezések halmazán a projekt nettó jelenértékét maximalizálja. Az optimális ütemezés elméletileg két egész értékű (nulla-egy típusú) programozási feladat megoldását jelenti, ahol azelső lépésben meghatározzuk a minimális időtartamú erőforrás-korlátos ütemezések időtartamát, majda második lépésben az optimális időtartamot feltételként kezelve megoldjuk a nettó jelenérték maximalizálásiproblémát minimális időtartamú erőforrás-korlátos ütemezések halmazán. A probléma NP-hardjellege miatt az egzakt megoldás elfogadható idő alatt csak kisméretű projektek esetében képzelhető el.A bemutatandó metaheurisztika a Csébfalvi (2007) által a minimális időtartamú erőforrás-korlátos ütemezésekidőtartamának meghatározására és a tevékenységek ennek megfelelő ütemezésére kifejlesztett harmóniakeresőmetaheurisztika továbbfejlesztése, amely az erőforrás-felhasználási konfliktusokat elsőbbségikapcsolatok beépítésével oldja fel. Az ajánlott metaheurisztika hatékonyságának és életképességének szemléltetésére számítási eredményeket adunk a jól ismert és népszerű PSPLIB tesztkönyvtár J30 részhalmazánfuttatva. Az egzakt megoldás generálásához egy korszerű MILP-szoftvert (CPLEX) alkalmaztunk. _______________ This paper presents a harmony search metaheuristicfor the resource-constrained project scheduling problem with discounted cash flows. In the proposed approach, a resource-constrained project is characterized by its „best” schedule, where bestmeans a makespan minimal resource constrainedschedule for which the net present value (NPV)measure is maximal. Theoretically the optimal schedule searching process is formulated as a twophasemixed integer linear programming (MILP)problem, which can be solved for small-scale projectsin reasonable time. The applied metaheuristic is basedon the "conflict repairing" version of the "Sounds ofSilence" harmony search metaheuristic developed byCsébfalvi (2007) for the resource-constrained projectscheduling problem (RCPSP). In order to illustratethe essence and viability of the proposed harmonysearch metaheuristic, we present computational results for a J30 subset from the well-known and popular PSPLIB. To generate the exact solutions a state-of-the-art MILP solver (CPLEX) was used.