Równoległe algorytmy genetyczne do rozwiązywania NRP

Planowanie obsady pielęgniarskiej jest złożonym problemem który pojawia się w codziennej działalności i systemie opieki zdrowotnej w nowoczesnych szpitalach. Nurse Rostering Problem jest podklasą problemów planowania personelu a większość jego instancji jest NP-trudna. Pomimo tego że rozwiązanie problemu obsady pielęgniarskiej jest przedmiotem badań od wielu lat nadal obsada pielęgniarska jest wykonywana ręcznie. Udowodniono że metaheurystyki GA są bardzo skuteczne w uzyskiwaniu niemal optymalnych rozwiązań dla różnych trudnych problemów kombinatorycznych w tym NP-trudnego. Algorytmy heurystyczne wykazały się doskonałymi zdolnościami wyszukiwania ale często tracą swoją skuteczność gdy są stosowane do dużych i złożonych problemów. Wiele metod optymalizacji cierpi z powodu przekleństwa wymiarowości które pokazuje że ich wydajność szybko się pogarsza wraz ze wzrostem wymiarowości przestrzeni wyszukiwania. Konieczność zapewnienia pewnego stopnia równoległości w tradycyjnym podejściu. Obecnie procesory graficzne GPGPU są w stanie zapewnić niezbędne zasoby obliczeniowe do rozwiązywania wysokowymiarowych problemów przy zachowaniu ograniczonego czasu wykonania i wysokiej przenośności.