Energy efficient scheduling of parallelizable jobs

این مقاله برنامه ریزی شغل های موازی را در تنظیم مقیاس سرعت غیر دائمی برای به حداقل رساندن اهداف زمان جریان وزنی به همراه انرژی می دهد. پیش از این، مرزهای پایینی قوی بر روی این مدل در تنظیمات بدون وزن نشان داده شد، حتی زمانی که الگوریتم یک مقدار ثابت از افزایش منابع را بیش از راه حل بهینه ارائه شده است. با این حال، این مرزهای پایین تر فقط برای خانواده های خاصی از الگوریتم ها ارائه می شود که به طور همزمان کارهای زنده را تشخیص نمی دهند. در این کار، ما محدودیت های قبلی پایین تر را نشان می دهیم و یک الگوریتم مقیاس پذیر را طبق فرض طبیعی می پذیریم که الگوریتم می تواند به طور همزمان پردازش شغلی را بداند. وقتی یک تابع قدرت عمومی در نظر گرفته می شود، این اولین الگوریتمی است که دارای نسبت رقابتی ثابت برای مشکل با استفاده از هر مقدار افزایش منابع است.