Weighted Scheduling with one overlap

[nik88]

I am trying to figure out an algorithm for finding the maximum weight of a schedule in which one overlap is allowed.

I can solve this with no overlaps using a fairly simple dynamic programming algorithm, however when one overlap is allowed I am not sure how figure the max weight out.

Is it possible to solve this using dynamic programming?

What about extending it to n overlaps?

any ideas?

[D_Drmmr]

I am trying to figure out an algorithm for finding the maximum weight of a schedule in which one overlap is allowed.

You'll have to be way more specific than that.

[nik88]

yeah you are right ... ok, so here it goes:

say I have a schedule with 6 tasks. Each task has a start time, end time and weight.

A: 0 - 2, w = 3
B: 0 - 10, w = 7
C: 1 - 5, w = 4
D: 4 - 11, w = 6
E: 5 - 15, w = 10
F: 2 - 5, w = 6

if I am trying to formulate a schedule with no overlaps, (no task can start before one is finished) the algorithm would output tasks, C and E which has the maximum weight 14 and no overlaps.

I can do this with a dynamic programming algorithm.

I want to be able to allow for one overlap (two tasks can be happening at once, ie. A and B is allowed but A, B and C is not) . Here the algorithm should output tasks, C, B and E with the total weight being 21.

Any ideas?

[nik88]

The reason I post this is because I am working on a project that is meant to allocate vehicles to people in a household.

Basically, I need to figure out, given a group of peoples schedule, who should get the car at what times?

more specifically, if there are 4 people in a household each with a set of trips which trips should get the car (all trips start from home and end at home) ... I could go into further detail, but I translated the problem to an activity scheduling problem described in my above post.

This is not a homework assignment!

I am not looking for a solution, just an idea if dynamic programming can work somewhat efficiently (polynomial time) for this problem. And if it can't, any suggestions on what kind of problem this resembles?

If more detail is needed on the specifics of Vehicle allocation for household activities ... I can do this ...

Thanks in advance.