I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists.
In my case, I am allowed to shift the start time of activities in some extend while duration remains same. This will give me some flexibility and I might increase my utilization.
Example scenario is something like the following where all activities are supposed to be in 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 shifting flexibility, I would choose (a1, a3, a6) and thats it. On the other hand I have shifting flexibility to the left/right by at most t units for any task where t is given. In that case I might come up with 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 more than enough room for each activity in the time domain. There are clusters of activities which overlaps and very big empty space where no activities and there comes another cluster of overlapping activities i.e a1, a2, a3 and a4 are let say cluster1 and a5 and a6 is cluster2. Each cluster can be expanded in time by shifting some of them to left and right. By doing that, I can select more activities than the original activity selection problem. However, I do not know how to decide which tasks to be shifted to left or right.
Are there any feasible solution to this problem?