Many Shared Resources Scheduling Problem
Schemal?ggning med m?nga delade resurser ?r ett algoritmiskt problem d?r ett antal jobb ska
schemal?ggas p? identiska maskiner. Varje maskin kan endast bearbeta ett jobb ?t g?ngen.
Varje jobb h?r till en specifik resurs, och tv? jobb som delar samma resurs kan inte behandlas
parallellt. Att minimera makespan, vilket ?r tiden d? det sista jobbet avslutas, ?r ett NP-sv?rt
problem. Ist?llet f?r att s?ka den optimala l?sningen unders?ker vi flera approximationsalgoritmer som p? polynomisk tid hittar ett schema vars makespan h?gst ?verstiger den optimala
makespan med en viss faktor. Vi presenterar omformuleringar av 3/2- och 5/3-algoritmerna
som f?rst introducerades av Deppert et al. [1], samt en ny 4/3-algoritm som fungerar under
vissa f?renklade antaganden om upps?ttningen av jobb. Denna nya 4/3-algoritm funkar om
det inte finns vissa typer av stora jobb, och vi presenterar ?ven id?er f?r hur det skulle kunna
g? att f? algoritmen att fungera i det allm?nna fallet. Dessutom implementerar vi flera algoritmer och vissa optimeringar och heuristiker, och j?mf?r deras prestanda p? slumpm?ssigt
genererad data. Simuleringarna visar att ?ven om approximationsalgoritmerna som diskuterats i tidigare avsnitt ?r anv?ndbara f?r att bevisa vissa egenskaper hos problemet, verkar
heuristiska algoritmer vara b?ttre l?mpade f?r verkliga till?mpningar.