Many Shared Resources Scheduling Problem
Publicerad
Författare
Typ
Examensarbete för kandidatexamen
Bachelor Thesis
Bachelor Thesis
Program
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.