Algorithm to solve allocation conflicts

Please help solve or point me to the appropriate existing algorithm in theory for this problem. No, it is not a coding contest, it comes from a real life issue! Here it is :

We have a list of tasks to do. Every task has a start day, end day, and a profit. Some tasks collide (their days within start end end dates intersect), therefore one can only do one at a time, so a choice has to be made. How can one select tasks to optimize profit?

I googled but could not find the related problem. Sure it exists. Thanks for help!

CodePudding user response：

This is polynomially solvable since this can be solved as a linear program. From your OP, it appears that each task covers consecutive days of work, and each day, only one task can be worked on. Given this, index your tasks by i = 1,...,I. Let profit be p_i. Let j = 1,...,J index the total number of days.

Then, you have the following problem to solve (specialized for 3 tasks and 4 days each task taking 2 consecutive days)

Max p_1 x_1   p_2 x_2   p_3 x_3
s.t.
    x_1                        <= 1 // day 1 task 1 
    x_1    x_2                 <= 1 //day 2 task 1 or 2
           x_2     x_3         <= 1 //day 3 task 2 or 3
                   x_3         <= 1 //day 4 task 3
x_1, x_2, x_3 >= 0

Next, convert each inequality to an equality by adding a slack variable.

Max p_1 x_1   p_2 x_2   p_3 x_3
s.t.
    x_1                  s_1               = 1 
    x_1    x_2                s_2          = 1 
           x_2     x_3             s_3     = 1
                   x_3                 s_4 = 1
                                         0 = 0
x_1, x_2, x_3, s_1, s_2, s_3, s_4 >= 0

Now, this is the same as:

Max p_1 x_1   p_2 x_2   p_3 x_3
s.t.
    x_1                  s_1                    = 1 
        x_2            - s_1   s_2              = 0 
   -x_1       x_3            - s_2   s_3        = 0
       -x_2                        - s_3   s_4  = 0
            - x_3                        - s_4  = -1
x_1, x_2, x_3, s_1, s_2, s_3, s_4 >= 0

where we have kept the first equation as is, and then sequentially subtracted the previous equation from the current one iteratively. If you observe the constraint matrix, you will observe that each column has exactly one 1 and exactly one -1 entry as the non-zero entries (this is a totally unimodular matrix). As a result, this becomes a trivial linear program, a network flow problem, that can be very efficiently solved by the network simplex method.

Note: On some thought it should be clear that even if different tasks span different number of days, performing the operation as indicated above will always lead to a totally unimodular constraint matrix.

CodePudding user response：

There's a pretty easy O(N²) dynamic programming solution.

Let BEST(d,w) be the maximum profit that you can attain using jobs with start days <=d, and end days < d w.

Assuming that all start days are >=0, then BEST(0,w) = 0 for all w.

For all the other days, BEST(d,w) for any d and all w can be easily calculated from the values for BEST(d-1,w 1) and the list of tasks that start on day d.

When d is high enough that all jobs have been considered, then the max BEST(d,w) is your answer.

With a little extra effort, you can limit your calculations to days on which tasks start, and lengths (w values) that are different from the next shorter length. That limits the range of both values to the number of jobs.