Many Shared Resources Scheduling Problem

Abstract

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.