Sammanfattning Vi anser orelaterade maskin schemaläggning problem med målet att minimera schema makespan. Utöver sitt maskinberoende är handläggningstiden för alla arbeten också beroende av användningen av en knapp förnybar resurs. En mängd k-enheter av den resursen, t.ex. Arbetstagare, kan fördelas över de arbetstillfällen som pågår, och ju mer av denna resurs tilldelas ett arbete, desto mindre är handläggningstiden. Modellen generaliserar den klassiska orelaterade maskin schemaläggning problem, lägga till en resurs-tid kompromiss. Det är också en naturlig variant av ett generaliserat uppdragsproblem som tidigare studerats av Shmoys och Tardos, skillnaden ligger i det faktum att resursen är förnybar och inte en total budgetbegränsning. Vi använder en tvåfasig LP-avrundningsteknik för att tilldela resurser till jobb och jobb till maskiner. I kombination med Grahams lista schemaläggning, bevisar vi således förekomsten av en (4 + 2 ⁄ 2)-tillnärmning algoritm. Vi visar hur vårt tillvägagångssätt kan anpassas till schemaläggningsproblem även med dedikerade maskiner, med en förbättring av prestandan som är begränsad till (3 + 2 ε 2). Dessutom härleder vi en lägre gräns på 2 för den använda LP-baserade analysen, och vi bevisar ett 1,5-in approximability resultat.
Om man antar att bearbetningstiderna är monotona i resurserna (och inte nödvändigtvis linjära), bevisas förekomsten av en (4 + 2 ε 2)-tillnärmningsalgoritm i REF.
Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times
{'venue': 'IPCO', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics', 'Psychology']}