Sammanfattning Detta dokument undersöker problemet med schemaläggning jobb på flera hastighetsskalade processorer, dvs. vi har konstant α > 1 så att köra en processor i hastighet s resulterar i energiförbrukning s α per tidsenhet. Vi betraktar det allmänna fallet där varje arbete har en monotont ökande kostnadsfunktion som straffar förseningar. Detta inbegriper de hittills behandlade fallen av tidsfrister, flödestid och viktad flödestid. För alla typer av delay cost-funktioner får vi följande resultat: Varje β-approximationsalgoritm för en enda processor ger en randomiserad βB α - approximationsalgoritm för flera processorer, där B α är α: e Bell-numret, det vill säga antalet partitioner av en uppsättning storlek α. Det genererade schemat är utan migration, men vi jämför det med ett optimalt schema med migration. Detta resultat gäller därför migrationsströmmar och icke-migrerande scheman. Analogt visar vi att varje β-konkurrenskraftig online-algoritm för en enda processor ger en βB α-konkurrenskraftig online-algoritm för flera processorer. Slutligen visar vi att varje β-tillnärmningsalgoritm för flera processorer med migrering ger en deterministisk βB α-tillnärmningsalgoritm för flera processorer utan migrering. Dessa fakta förbättrar flera approximativa nyckeltal och leder till nya resultat. Till exempel får vi den första konstanta faktorn online och offline approximation algoritm för flera processorer utan migration för godtyckliga releasetider, deadlines och jobbstorlekar.
Greiner m.fl. I REF föreslogs en B α - approximationsalgoritm för allmänna instanser, där B α är det α-te Bell-numret.
The Bell Is Ringing in Speed-Scaled Multiprocessor Scheduling
{'venue': 'Theory of Computing Systems', 'journal': 'Theory of Computing Systems', 'mag_field_of_study': ['Computer Science']}