Many Shared Resources Scheduling Problem

dc.contributor.authorBjörkenbacke, Olle
dc.contributor.authorKihl, Hampus
dc.contributor.authorLapidus, Olle
dc.contributor.departmentChalmers tekniska högskola / Institutionen för matematiska vetenskapersv
dc.contributor.departmentChalmers University of Technology / Department of Mathematical Sciencesen
dc.contributor.examinerEriksson, Dennis
dc.contributor.supervisorRau, Malin
dc.date.accessioned2025-06-30T11:42:28Z
dc.date.issued2025
dc.date.submitted
dc.description.abstractSchemalä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.
dc.identifier.coursecodeMVEX11
dc.identifier.urihttp://hdl.handle.net/20.500.12380/309778
dc.language.isoswe
dc.setspec.uppsokPhysicsChemistryMaths
dc.titleMany Shared Resources Scheduling Problem
dc.type.degreeExamensarbete för kandidatexamensv
dc.type.degreeBachelor Thesisen
dc.type.uppsokM2

Ladda ner

Original bundle

Visar 1 - 1 av 1
Hämtar...
Bild (thumbnail)
Namn:
MVEX11_Olle_Olle_Hampus_Rapport08_2506.pdf
Storlek:
1.64 MB
Format:
Adobe Portable Document Format

License bundle

Visar 1 - 1 av 1
Hämtar...
Bild (thumbnail)
Namn:
license.txt
Storlek:
2.35 KB
Format:
Item-specific license agreed upon to submission
Beskrivning: