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

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 \(\frac{5}{4}(1+\epsilon )\) approximation algorithm \(\mathcal {BEKP} \) by associating it to a Multiple Subset Sum problem. Our algorithm is an improvement over the existing literature, which provides a ( \(\frac{3}{2} - \frac{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.