I have some activities with weights and I would like to select activities that do not overlap by maximizing the total weight. This is a known problem and the solution exists.
In my case, I am allowed to shift the start time of activities while the duration remains the same. This will give me some flexibility and I could increase my use.
Scenario example is something like the following where all activities are supposed to be in the interval (0-200):
(start, end, profit)
a1: 10 12 120
a2: 10 13 100
a3: 14 18 150
a4: 14 20 100
a5: 120 130 100
a6: 126 132 150
Without changing flexibility, I would choose (a1, a3, a6) and that's all. By cons I have changing flexibility left / right by at most t units for any task where t is given. In this case, I could suggest this schedule and all tasks can be selected.
t: 5
a1: 8 10 120 (shifted -2 to left)
a2: 10 13 100
a3: 14 18 150
a4: 18 23 100 (shifted +4 to right)
a5: 115 125 100 (shifted -5 to left)
a6: 126 132 150
In my problem, I have enough room for each activity in the time domain. There are overlapping groups of activities and a very large empty space where there are no activities and there is another group of overlapping activities, that is, a1, a2, a3 and a4 are cluster1 and a5 and a6 are cluster2. Each group can be expanded in time by moving some of them to the left and the right. By doing this, I can select more activities than the original activity selection problem. However, I do not know how to decide which tasks to move left or right.
Is there a workable solution to this problem?
