Problem: Consider the scheduling problem of n jobs on M machines where each job i have a processing time pi and gives a profit gi(t) if completed by time t. All the jobs are released at time 0. All gi(t) are non-increasing functions. For simplicity, we can assume that the machines are not preemptive.
For M=1 and linearly decreasing profit functions. this problem can be solved in O(n) using the greedy algorithm. But for general functions it is NP-complete.
I am interested in the general case. Please give me any link of papers or resource materials for the problem. I searched on the internet but didn't find anything interesting for M>1, though there is previous work on approximating the bounds for M=1.
Please note that I am not expecting you to solve this but just need previous work on the similar problems, if any. And if you have any ideas which can help please feel free to share.
I want know what bounds are know for this problem with m machines and n jobs with same release dates and general non-increasing profit functions. I found a paper towards that direction
http://arxiv.org/pdf/1008.4889v1.pdf
They gave an O(1) approximation when all jobs have identical release times. I want to find similar kind literature for the problem and what ideas they used for solving the problem.