Maximize profit in scheduling unit tasks with dependencies

Question

Problem I have n jobs to schedule in P seconds on unlimited number of machines with dependencies between the jobs i.e . for every job there is a set of jobs which are to be scheduled only after this job is finished. The profit for scheduling the i^th job in j^th second on any machine is f(i,j), which is positive.
And my target is to maximize the total profit by scheduling each job exactly once in at most P seconds.

We can assume that all the jobs can be scheduled in P seconds always.

Everything is known in advance i.e. offline problem.

Also 0 <= f(i,j) <= B . for all i, j .

and number of dependencies is of O(n).

Is this problem easy ? [may be due to finite constraints ]

My approach
For simplicity , first assume that for a job its profit is time independent.
That is f(i,j) is independent of j for all i and is dependent on only i.
Then any topological ordering which fits in P seconds will work.
If there is no dependency, then also we choose the highest profit giving time for each job and this is easy also.

But problem is when profit for a jobs varies with time with dependencies, in this case, I am unable think any general algorithm.

I am having trouble dealing with the dependencies between the jobs , Are there any resources for dependent unit tasks scheduling algorithms online ?

Please share any idea which can help ...

Update : I have added the bounds for various parameters as they may be required for analysis of the problem.

Answer 1

This is a dynamic programming problem. Let's assume for simplicity that all profits are non-negative.

Define F(i, j) to be the maximum profit to be made from scheduling the i'th job and all of the things that depend on it (recursively downwards) at or later than the j'th second, or -1 if that is impossible.

Then F(i, j) is -1 if F(i_1, j+1) is -1 for any dependency i_1 of i. Otherwise it is the larger of (f(i, j) plus the sum of F(i_1, j+1)) or F(i, j+1).

And then your answer is the sum of F(i, 0) for all jobs i with no dependencies.

(Without unlimited machines this problem would become np-hard...)

---

Here is an example of how to use your problem to model MAX-SAT equations where each clause has all terms not negated or all terms negated.

Suppose we have 4 boolean variables A, B, C, and D. As an example suppose that we want to do maximum satisfiability for the equation (A && B) || (!A && !C) || (!B && !C && !D) || (C && D). (Where ! means not, && means and, and || means or.)

Let's use the notation J1 > J2 for jobs where J1 has to run before J2. And distribute over parentheses so that J1 > (J2, J3) means that J1) is a dependency for bothJ2andJ3`.

Now to model the booleans let's set up 12 jobs. A1 > A2 > A3, B1 > B2 > B3, C1 > C2 > C3, and D1 > D2 > D3. Then the jobs A2, B2, C2, D2 must occur at time 2 or 3, and the boolean A is the truth of the statement "A2 happens at time 2". And likewise for the other booleans.

All of these jobs are given a profit of 1 no matter what time they run at. We introduced 3x as many jobs as booleans, but so far this is straightforward.

Now let's add jobs for the clauses. Each of these jobs will have a profit of 11 if it runs in seconds 2 or 3, and 1 otherwise. Your maximum profit will therefore be reached when you find settings for your booleans that maximize the number of clauses that are true.

(A2, B2) > J1 models the truth of (A && B).

J2 > (A2, C2)) models the truth of (!A && !C).

J3 > (B2, C2, D2) models the truth of (!B && !C && !D).

(C2, D2) > J4 models the truth of (C && D).

This is again a straightforward transformation, with the number of jobs added equal to the number of clauses.

So we're modeling MAX-SAT problems with scheduling. But we can't model all of them. In particular we have no way to model clauses with mixed negation like (A && !B). So even though MAX-SAT is NP-hard, it is possible that this restricted version is not. However other restricted versions of MAX-SAT, for instance MAX-2SAT, tend to be NP-hard, and it is my intuition that this one will be as well.

But for a proof or disproof of that intuition, you should ask on a more appropriate forum. Like https://cs.stackexchange.com/.