Approximation algorithms for scheduling with rejection in green manufacturing

Motivated by green manufacturing, this paper investigates a scheduling with rejection problem subject to an energy consumption constraint. Machines are associated with non-uniform energy consumption rates, defined as the energy consumed per unit time. Each job is either rejected with a rejection penalty or accepted and scheduled on some machine for processing, which incurs energy consumption. The problem aims to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs while the total energy consumption is bounded by a given threshold. In this paper, when the number of machines is part of the input, we develop the first $(2+ε)$-approximation algorithm for any fixed constant $ε$ and a simple QPTAS as well as a PTAS for uniform energy consumption rates. Moreover, we present an FPTAS when the number of machines is a fixed constant.