Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436149 | Theoretical Computer Science | 2015 | 18 Pages |
Abstract
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(KNlogN)O(KNlogN), N being the number of jobs and K the number of delivery dates.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yasmina Seddik, Christophe Gonzales, Safia Kedad-Sidhoum,