I detta dokument överväger vi problemet med att schemalägga en ansökan på en parallell beräkningsplattform. Ansökan är en särskild uppgift diagram, antingen en linjär kedja av uppgifter, eller en uppsättning oberoende uppgifter. Plattformen är tillverkad av identiska processorer, vars hastighet kan ändras dynamiskt. Den är också föremål för fel: om en processor saktas ner för att minska energiförbrukningen, har den en större chans att misslyckas. Därför, schemaläggning problem kräver att åter utföra eller replikera uppgifter (dvs. utföra två gånger en samma uppgift, antingen på samma processor, eller på två olika processorer), för att öka tillförlitligheten. Det är ett tri-kriterium problem: målet är att minimera energiförbrukningen, samtidigt som en bunden på den totala verkställighetstiden (the makepan), och en begränsning på tillförlitligheten av varje uppgift. Vårt huvudsakliga bidrag är att föreslå approximationsalgoritmer för dessa särskilda klasser av uppgiftsgrafer. För linjära kedjor utformar vi ett helt polynom tid approximationsschema. Vi visar dock att det inte finns någon konstant faktor approximation algoritm för oberoende uppgifter, om inte P=NP, och vi kan i detta fall föreslå en approximation algoritm med en avslappning på makespan begränsning.
Tillnärmningsalgoritmer för vissa typer av uppgifter grafer presenterades för att effektivt lösa samma problem i REF.
Approximation algorithms for energy, reliability and makespan optimization problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}