Efficient scheduling jobs with declining profits on multiple machines

Question

Problem: Consider the scheduling problem of n jobs on M machines where each job i have a processing time p_i and gives a profit g_i(t) if completed by time t. All the jobs are released at time 0. All g_i(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.

Answer 1

You can start with a "greedy solution" by using a dispatch rule that e.g. minimizes

g_i(t₀+p_i)/p_i

on the first empty machine (i runs over all not yet scheduled jobs, t₀ is the time, where the first machine is empty).

Then this solution can be improved using Meta-Heuristics like Simulated Annealing. A solution can be represented as a tuple of job sequences (one job sequence for each machine). A crucial point is, what "moves" are allowed to change a solution. Maybe for this problem one can find already good solutions with the two basic moves:

• Take one job from one machine and find a new place to insert it.
• Exchange two jobs in the machines' job sequences.