Performance guarantees for a scheduling problem with common stepwise job payoffs

We consider a single machine scheduling problem with unequal release dates and a common stepwise payoff function for the jobs. The goal is to maximize the sum of the jobs payoffs, which are defined with regard to some common delivery dates. The problem is strongly NP-hard. In this paper, we propose a polynomial time approximation algorithm with both absolute and relative performance guarantees. The time complexity of the approximation algorithm is O(KNlog⁡N)O(KNlog⁡N), N being the number of jobs and K the number of delivery dates.