Optimal Selection of Non-Overlapping Jobs 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 &quot;CPU's&quot; - 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?
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.