English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider fundamental scheduling problems motivated by energy issues. Inthis framework, we are given a set of jobs, each with a release time, deadlineand required processing length. The jobs need to be scheduled on a machine sothat at most g jobs are active at any given time. The duration for which amachine is active (i.e., "on") is referred to as its active time. The goal isto find a feasible schedule for all jobs, minimizing the total active time.When preemption is allowed at integer time points, we show that a minimalfeasible schedule already yields a 3-approximation (and this bound is tight)and we further improve this to a 2-approximation via LP rounding techniques.Our second contribution is for the non-preemptive version of this problem.However, since even asking if a feasible schedule on one machine exists isNP-hard, we allow for an unbounded number of virtual machines, each havingcapacity of g. This problem is known as the busy time problem in the literatureand a 4-approximation is known for this problem. We develop a new combinatorialalgorithm that gives a 3-approximation. Furthermore, we consider the preemptivebusy time problem, giving a simple and exact greedy algorithm when unboundedparallelism is allowed, i.e., g is unbounded. For arbitrary g, this yields analgorithm that is 2-approximate.

LP Rounding and Combinatorial Algorithms for Minimizing Active and Busy Time