Many Shared Resources Scheduling Problem

Publicerad

Typ

Examensarbete för kandidatexamen
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.

Beskrivning

Ämne/nyckelord

Citation

Arkitekt (konstruktör)

Geografisk plats

Byggnad (typ)

Byggår

Modelltyp

Skala

Teknik / material

Index

item.page.endorsement

item.page.review

item.page.supplemented

item.page.referenced