Answers are grounded in this paper and cite their sources.
We study two offline job scheduling problems where tasks can be processed on a limited number of energy-efficient edge machines or offloaded to an unlimited supply of energy-inefficient cloud machines (called rejected). The objective is to minimize total energy consumption. First, we consider scheduling without deadlines, formulating it as a scheduling problem with rejection, where rejection costs are proportional to processing times. We propose a novel <tex-math notation="LaTeX">5/4(1+ε )</tex-math>-approximation algorithm, <tex-math notation="LaTeX">BEKP</tex-math>, by associating it to a Multiple Subset Sum problem, improving upon the existing <tex-math notation="LaTeX">(3/2 - 1/2m)</tex-math>-approximation for arbitrary rejection costs. Next, we address scheduling with deadlines, aiming to minimize the weighted number of rejected jobs. We position this problem within the literature and introduce a new <tex-math notation="LaTeX">(1-(m-1)ᵐmᵐ)</tex-math>-approximation algorithm, <tex-math notation="LaTeX">MDP</tex-math>, inspired by an interval selection algorithm with a <tex-math notation="LaTeX">(1-mᵐ(m+1)ᵐ)</tex-math>-approximation for arbitrary rejection costs. Experimental results demonstrate that <tex-math notation="LaTeX">BEKP</tex-math> and <tex-math notation="LaTeX">MDP</tex-math> obtain better results (lower costs or higher profits) than other state-of-the-art algorithms while maintaining a competitive or better time complexity.
No takes yet. Share an insight, caveat, or question.
Beaumont et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: