In this problem. I have a set of "activities" which can happen. Each "activity" is associated with several values:

  • Duration: The length of time the activity takes
  • Earliest time to start: The earilest time at which the activity can begin
  • Latest time to start: The latest time at which the activity can begin
  • Weight/Value: The "value"/"benefit" gained if the activity happens.

I have a set of activities $A = \left\{ a_{1},a_{2},\dots,a_{n}\right\} $. I want to find a subset of activities $\alpha \subset A$ which maximises the total value, subject to the constraint that two activities cannot overlap in time (so the subset of activities should be such that we can schedule these activities without any overlap, and such that each activity starts within its earliest and latest start times). Activities must be performed contiguously. i.e we can't just break apart an activity in two and do half of it now and half of it later.

If activities all had a fixed starting time, this would be equivalent to the "Maximum Weight Independent Set of Intervals" problem, but in this case an activitiy does not have a fixed starting time and it can move around.

If activities could be positioned anywhere, this would be equivalent to a knapsack problem.

I will use this with a time span of one day and activities will usually last between 1 and 4 hours.

I had one idea which I write below but thought maybe someone would have a better idea. Heuristics and approximations would be helpful as well.

I need something that will run in less than a second with ~$1000$ activities.

So far what I thought of doing is duplicating activities that can move around. So if I have an activity $a$ which can start between 14:00 and 16:00, then to create three activities: at 14:00, at 15:00 and at 16:00. That way I don't need to worry anymore about activities moving around and I have a "Maximum Weight Independent Set of Intervals" problem which seems researched at least. Also "Maximum Weight Independent Set" problems are quite researched.

Thank you!


Your Answer

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

Browse other questions tagged or ask your own question.