2
$\begingroup$

I'm trying to find what the family of problem is - as well as an approach - for the following:

I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri. Each task takes place during a fixed interval - ie: task 1 is from times 1-4, task 2 from 2-5, and task 3 from 9-15. This means that I would have to pick either task 1 or 2 depending on which is more valuable, and then task 3 which does not conflict with either of the previous.

I'd like for this to scale to n tasks, and also to m "CPU's" - where more than one task can be executed in parallel. This reminds me of the knapsack problem, but maybe an interval graph would provide a better approach?

Any suggestions on how to approach this problem, or any relevant references?

$\endgroup$
0
$\begingroup$

If you consider each task as a node of a graph, and each conflict as an edge, this is a weighted maximum independent set problem.

It is NP-hard, but you should get good results with a mixed integer programming solver, such as CBC.

$\endgroup$
2
  • $\begingroup$ To show the OP's problem is NP-hard, the reduction needs to go in the opposite direction. Weighted MIS cannot be directly reduced to this problem, because certain combinations of edges are impossible to represent as overlaps in an interval graph: E.g. if $a$ and $b$ both overlap $c$ and $d$, and $c$ and $d$ do not overlap each other, then $a$ must overlap $b$. $\endgroup$ – j_random_hacker Apr 3 at 7:34
  • $\begingroup$ Totally. I don't think I was referring to OP's problem, only to the independent set formulation. Note that the graph with n tasks and m cpus is not an interval graph anymore. $\endgroup$ – Gabriel Gouvine Apr 3 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.