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?