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?


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.