Denna artikel initierar en teoretisk undersökning av online schemaläggning problem med hastighetsskalning där de tillåtna hastigheterna kan vara diskret, och effektfunktionen kan vara godtycklig, och utvecklar algoritmiska analystekniker för denna inställning. Vi visar att en naturlig algoritm, som använder kortast återstående processtid för schemaläggning och sätter makten att vara en mer än antalet oavslutade jobb, är 3-konkurrenskraftiga för målet med total flödestid plus energi. Vi visar också att en annan naturlig algoritm, som använder den högsta densiteten först för schemaläggning och sätter kraften att vara den fraktionerade vikten av de oavslutade jobben, är en 2-konkurrenskraftig algoritm för målet med fraktionerad viktad flödestid plus energi.
Bansal m.fl. REF introducerade begreppet godtycklig effektfunktion och visade att en online-clairvoyant algoritm (OCA) är (2 + )-kompetitiv med ett mål att minimera den fraktionerade viktade flödestiden plus energi.
Speed Scaling with an Arbitrary Power Function
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science']}