A 1.25(1+ε)-Approximation Algorithm for Scheduling with Rejection Costs Proportional to Processing Times

EasyChair Preprint 13471

Abstract

We address an offline job scheduling problem where jobs can either be processed on a limited supply of energy-efficient machines, or offloaded to energy-inefficient machines (with an unlimited supply), and the goal is to minimize the total energy consumed in processing all tasks. This scheduling problem can be formulated as a problem of scheduling with rejection, where rejecting a job corresponds to process it on an energy-inefficient machine and has a cost directly proportional to the processing time of the job. To solve this scheduling problem, we introduce a novel 1.25(1+ε) approximation algorithm BEKP by associating it to a Multiple Subset Sum problem. Our algorithm is an improvement over the existing literature, which provides a (1.5 - 1/2m) approximation for scheduling with arbitrary rejection costs. We evaluate and discuss the effectiveness of our approach through a series of experiments, comparing it to existing algorithms.

Keyphrases: approximation algorithm, energy minimization, scheduling with rejection

@booklet{EasyChair:13471,
  author    = {Olivier Beaumont and Rémi Bouzel and Lionel Eyraud-Dubois and Esragul Korkmaz and Laercio Pilla and Alexandre Van Kempen},
  title     = {A 1.25(1+ε)-Approximation Algorithm for Scheduling with Rejection Costs Proportional to Processing Times},
  howpublished = {EasyChair Preprint 13471},
  year      = {EasyChair, 2024}}