A Combinatorial 2-Approximation Algorithm for the Parallel-Machine Scheduling with Release Times and Submodular Penalties.

In this paper, we consider parallel-machine scheduling with release times and submodular penalties ( P | r j , r e j e c t | C max + π (R) ), in which each job can be accepted and processed on one of m identical parallel machines or rejected, but a penalty must paid if a job is rejected. Each job has a release time and a processing time, and the job can not be processed before its release time. The objective of P | r j , r e j e c t | C max + π (R) is to minimize the makespan of the accepted jobs plus the penalty of the rejected jobs, where the penalty is determined by a submodular function. This problem generalizes a multiprocessor scheduling problem with rejection, the parallel-machine scheduling with submodular penalties, and the single machine scheduling problem with release dates and submodular rejection penalties. In this paper, inspired by the primal-dual method, we present a combinatorial 2-approximation algorithm to P | r j , r e j e c t | C max + π (R) . This ratio coincides with the best known ratio for the parallel-machine scheduling with submodular penalties and the single machine scheduling problem with release dates and submodular rejection penalties. [ABSTRACT FROM AUTHOR]