Effective job planning with reduced profits on multiple machines

Question

Problem: Consider the problem of scheduling n tasks on machines M, where each task has processing time p _i and gives profit g _i (t) if it is completed by time t. All tasks will be released at time 0. All g _i (t) are not increasing functions. For simplicity, we can assume that machines are not proactive.

With M = 1 and linearly decreasing profit functions. this problem can be solved in O (n) using a greedy algorithm. But for common functions, it is NP-complete.

I am interested in the general case. Please give me a link to documents or materials to solve the problem. I searched on the Internet, but did not find anything interesting for M> 1, although there is previous work on approximating estimates for M = 1.

Please note that I do not expect you to solve this, but you just need to do previous work on similar problems, if any. And if you have any ideas that might help, please feel free to share them.

I want to know what boundaries are known for this problem with m machines and n jobs with the same release dates and generally not increasing profit functions. I found paper in that direction

http://arxiv.org/pdf/1008.4889v1.pdf

They gave an approximation of O (1), when all tasks have the same release time. I want to find similar literature for the problem and what ideas they used to solve the problem.

Answer 1

You can start with a "greedy solution" using a sending rule, for example, minimizes

g <sub> Isub> (t <sub> 0sub> + p <sub> Isub>) / p <sub> yasub>

on the first empty machine (i runs through the still not scheduled tasks, t ₀ is the time when the first machine is empty).

Then this solution can be improved using metaheuristics, for example, Simulated annealing . A solution can be represented as a set of task sequences (one task sequence for each machine). The decisive point is that the "moving" is allowed to change the decision. Perhaps for this problem you can already find good solutions with two main moves:

• Take one task from one computer and find a new place to insert it.
• Exchange of two tasks in the sequence of tasks of machines.