Hampus Karlberg

Schemaläggning genom diskret Particle Swarm Optimisation

Sammanfattning

Optimering av arbetsfördelning i nätverk kan äka användandet av tillgängliga resurser. I instabila heterogena nätverk kan schemaläggning användas för att optimera för beräkningstid, energieffektivitet och systemstabilitet. Då nätverk består av sammankopplade resurser innebär det också att vad som är ett optimalt schema kan komma att ändras över tid. Bredden av nätverkskonfigurationer gör också att det kan vara svårt att överföra och applicera ett schema från en konfiguration till en annan. Diskret Particle Swarm Optimisation (DPSO) är en meta heuristisk metod som kan användas för att ta fram lösningar till schemaläggningsproblem. Den här uppsatsen kommer utforska hur DPSO kan användas för att optimera schemaläggning för instabila nätverk. Syftet är att hitta en lösning för nätvärk under liknande begränsningar som de som återfinns på tåg. Detta för att i sin tur facilitera planerandet av optimala banor. Genom användandet av ett artificiellt neuralt nätverk (ANN) upskattar vi schemaläggningskostnaden. Denna kostnad används sedan av DPSO heurestiken för att utforska en lösningsrymd med potentiella scheman. Våra resultat fokuserar på optimeringen av gruperingsstorleken av distribuerade problem i relation till robusthet och letens. Vi simulerar ett flertal instabila och heterogena nätverk och jämför deras prestanda. Utgångspunkten för jämförelsen är schemaläggning där uppgifter distribueras jämt i bestämda gruperingsstorlekar. Prestandan analyseras sedan i relation till användbarheten i verkliga scenarion. Våra resultat visar på en signifikant ökning i prestanda inom ett brett spann av nätverkskonfigurationer. Det här är på bekostnad av långa söktider för DPSO algoritmen. Vår slutsats är att under rätt förutsättningar kan metoden användas för att snabba upp distribuerade beräkningar förutsatt att beräkningarna för schemaläggningen görs i förväg. We rekommenderar vidare utforskande av DPSO algoritmens parametrar för att snabba upp konvergens, samt undersökande av algoritmens prestanda i verkliga miljöer.