Vi anser att problemet med hastighetsskalning infördes i Yao et al:s seminalpapper. [25]................................................................. I detta problem, ett antal jobb, var och en med sin egen bearbetning volym, release tid, och deadline måste utföras på en hastighetsskalbar processor. Strömförbrukningen hos denna processor är P (s) = s α, där s är processhastigheten, och α > 1 är en konstant. Den totala energiförbrukningen är energiintegrerad över tid och målet är att bearbeta alla jobb samtidigt som energiförbrukningen minimeras. Den förebyggande versionen av problemet, tillsammans med dess många varianter, har studerats ingående under årens lopp. Dock är lite känt om den icke förebyggande versionen av problemet, förutom att det är starkt NP-hård och tillåter en konstant faktor approximation [6]. Hittills har problemets (allmänna) komplexitet varit okänd. I detta dokument studerar vi ett viktigt specialfall av problemet, där arbetsintervallen bildar en laminär familj, och presenterar ett kvasipolynom-tids approximationssystem för det, vilket visar att (åtminstone) detta specialfall inte är APX-hård, om inte NP  och DTIME(2 poly(log n) ). Det andra bidraget från detta arbete är en polynom-tidsalgoritm för specialfallet av lika volymjobb, där tidigare endast en 2 α approximation var känd [8]. Dessutom visar vi att två andra specialfall av detta problem tillåter helt polynom-tids approximationssystem (FPTAS).
Lägg märke till det oberoende, Huang et al. I REF föreslogs en polynom-tidsalgoritm för det enskilda maskinfallet.
New Results for Non-Preemptive Speed Scaling
{'venue': 'MFCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}