Humán erőforrás optimális felhasználása

A téma kiírójának neve és tanszéke: 
Illés Tibor, Differenciálegyenletek Tanszék
A téma kiírójának e-mail címe: 
illes@math.bme.hu
Típus: 
PhD téma

Napjaink igen fontos problémája a rendelkezésre álló erőforrások ésszerű (optimális) felhasználása. Az erőforrások egyik legértékesebbje a humán erőforrás. Országok folytatnak folyamatos küzdelmet jól képzett munkaerő megszerzéséért, így nem meglepő, hogy a magasan képzett, hiány szakmákban dolgozó munkaerő optimális felhasználása a feladatok elvégzésére egyre inkább a modern gazdaság egyik kulcskérdésévé válik. A munkaerő optimális felhasználásának szép példáit adják a pilóták, stewardessek és repülőgépek járatokhoz rendelése; bolti eladók és pénztárosok műszakokhoz rendelése; orvosok, nővérek heti vagy havi beosztásának elkészítése, ügyeleteik kiosztása, vagy a mozdonyok, vonatok, és a buszok és vezetőinek járatokhoz rendelése. Az a közös az imént felsorolt feladatokban, hogy meghatározott képesítést igényelő munkákhoz kell optimálisan rendelni a rendelkezésre álló munkatársakat, kielégítve törvényi és egyéb humánpolitikai szabályokat. A példaként felsorolt esetekben közös az, hogy az elvégzendő feladatokhoz kell hozzárendelni a rendelkezésre álló erőforrásokat (legyen az ember, eszköz, vagy mindkettő). A gyakorlatban ez általában bonyolultabb az egészértékű programozásból ismert hozzárendelési alapfeladatnál, mert a párosítási feltételeken túl, törvényi szabályozást leíró feltételeket is be kell építeni az optimalizálási modellbe.

A tárgyalásra kerülő ütemezési illetve hozzárendelési feladatok nagy többsége, az egészértékű változókkal való leírás miatt – komplexitás elméleti szempontból – NP-teljes optimalizálási feladatra vezet. Természetesen a feladat nehézsége csupán annyit jelent, hogy a konkrét, valós feladatok esetén optimális megoldás előállítása elméletileg – általában – nem garantálható. Operációkutatási szempontból, ezért (is) válik érdekessé a feladat, hiszen tág teret nyit a modell variánsok megfogalmazására, közelítő eljárások kidolgozására, poliéderes kombinatorikai megközelítés alkalmazására, gyakorlatban hatékony számítógépes implementáció elkészítésére.

Az 1940-es évek óta komoly szakirodalma alakult ki a témakörnek. Jelenleg a gyakorlatban is alkalmazható (és alkalmazott) megoldási módszere a humán erőforrás ütemezési és (vagy) hozzárendelési feladatnak az úgynevezett generálás és kiválasztás (GAS) módszere. Ennek lényege, hogy nagyon sok ún. megengedett műszakot generálunk, majd ezek közül egy halmazfedési probléma (közel optimális) megoldásával kiválasztunk annyi dolgozót és a hozzá tartozó műszakot, amennyi az összes elvégzendő feladathoz minimálisan kell. Nyilvánvaló, hogy egyszerre két optimalizálási feladatot kell elvégeznünk: meg kell határoznunk a szükséges munkaerő számát és azok megengedett műszakát.

Szinte minden humán erőforrás ütemezési és (vagy) hozzárendelési feladat esetén a megengedett műszakok száma a változók darabszámának exponenciális függvénye. Ebből világosan következik, hogy a módszer a valódi feladatnak csak egy a megengedett megoldások részhalmazán keresztül történő közelítése lehet. A GAS módszer e hátránya miatt, feladat specifikus megengedett műszak generálási heurisztikák terjedtek el. A GAS módszer hátrányai miatt: lehetséges műszakok generálása (a feladat megengedett megoldásának belső approximációja) és a halmaz fedési egészértékű programozási feladat NP-teljessége miatt, nyilvánvaló, hogy az optimumtól való eltérésnek két komoly hibaforrása is van.

A GAS kialakulásának és elterjedésének az oka az volt, hogy évtizedeken keresztül (nagyméretű) gyakorlati feladatot csak ezzel a módszerrel lehetett megoldani a számítógépes kapacitás korlátok és a számítási sebesség (lassúság) miatt. Ma már ezek a korlátozó feltételek nem állnak fenn, így elérkezett az idő, hogy a humán erőforrás ütemezési és (vagy) hozzárendelési problémára új modell osztályt dolgozzunk ki, amelyik a probléma operációkutatási szempontból teljes leírását adja meg és az új modellhez fejleszt ki megoldási eljárásokat.

A BME Optimalizálási Kutatócsoportban a humán erőforrás ütemezési és (vagy) hozzárendelési probléma, buszvezető hozzárendelési feladatára egy lehetséges új modell került megfogalmazásra.

A doktori kutatási projekt keretében a jelölt feladata a humán erőforrás ütemezési és (vagy) hozzárendelési probléma új modelljének részletes kidolgozása mellett, olyan új, hatékony algoritmusok megfogalmazása lenne, amelyek nagyméretű gyakorlati feladatok hatékony megoldását tenné lehetővé. Komoly előrelépés lenne, ha az új modell és a kidolgozandó algoritmusok segítségével, egy-egy speciális feladatosztályára (pl. buszvezetők hozzárendelése), a gyakorlatban a GAS módszernél hatékonyabb számítási eljérás készülne.