13

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 ith job in jth 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.

v78
  • 2,803
  • 21
  • 44
  • Do jobs complete in 1 second? That is, if a job is scheduled at time j, then any dependent jobs can run at time j+1? Given that we know everything in advance it is always possible to brute force the solution, but I assume you are asking if something better exists. – dohashi Dec 09 '14 at 14:48
  • yes,any IMMEDIATE dependent job can be scheduled at time j+1 second. Naive brute force is very inefficient and exponential for this problem – v78 Dec 09 '14 at 14:58
  • 1
    Perhaps you can read the editorial when it comes out: http://www.codechef.com/DEC14/problems/RIN – David Eisenstat Dec 11 '14 at 21:06

1 Answers1

3

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/.

Community
  • 1
  • 1
btilly
  • 43,296
  • 3
  • 59
  • 88
  • 1
    No, there is error , I figured out this approach earlier . The task dependency graph is not a tree in general , it is a DAG, if a job have more than one parent then this approach gives wrong answer[it overestimate the required profit]. I can give example if not clear ?? – v78 Dec 08 '14 at 05:49
  • That's a major twist and a bad assumption on my part. Sorry. – btilly Dec 08 '14 at 17:40
  • I think DP may not be applicable in the general case . Also this problem is not in NP-complete , may be network flow can be applied. – v78 Dec 08 '14 at 18:57
  • @cc2 I have been thinking about the case where `P=4`, there is a set `S` of jobs that can happen on either second 2 or second 3, there are other jobs `T` that get a significant profit if they happen on second 2 and a subset of `S` depends on them, and still more `T'` that get a significant profit if they happen on second 3 and depend on a subset of `S`. For each element of `S` you have the boolean "this job happens on second 2." Each element of `T` and `T'` represents a boolean clause. And you've modeled a MAX-SAT problem. I don't know how to prove that... – btilly Dec 09 '14 at 15:49
  • you've modeled enough of MAX-SAT to make answering your question for this type of job actually NP-Hard, but it really has that feel. I'd suggest asking about this variation on csexchange where you'll get people more qualified than myself to analyze the question. – btilly Dec 09 '14 at 15:50
  • please can you explain your reduction to MAX-SAT with your example with VALUES . I am unable to see how this can be reduced to MAX-SAT. – v78 Dec 09 '14 at 17:58
  • @cc2 I updated the post to illustrate how I am reducing a specific type of scheduling problem that you would want to solve to a specific class of MAX-SAT problems. And clarified what more work would need to be done for this to turn into a demonstration that I am correct in suspecting that your problem is NP-Hard. – btilly Dec 09 '14 at 18:43
  • 2
    @btilly Are you sure you want your formula to be an OR of ANDs and not the AND of ORs? Satisfiability questions are normally the latter. Otherwise, all we need to do is find a satisfying assignment for one clause and we're done. – mhum Dec 10 '14 at 02:41
  • @mhum Looking more carefully, you're right. That said, the construction I have is a series of binary choices with clauses that are ands. I still would be willing to bet money that it is NP-hard, even if it isn't the problem I thought it was. – btilly Dec 10 '14 at 04:34
  • @cc2: I don't understand what you guys are saying about MAX-SAT, but I feel quite confident that each `F(i, j)` can be calculated in `O(n*p)` with dynamic programming. – Mooing Duck Dec 11 '14 at 20:10
  • @MooingDuck The problem is that jobs can have multiple dependencies, and multiple things can depend on them. `F(i, j)` as described attributes all of the possible additional profit from scheduling children earlier to the decision about when the parent job should run, and then schedules from the top on down. But if the child job depends on independent parents, when the one parent is scheduled affects what `F(i,j)` should be for the other one and vice versa. So the whole thing falls apart. – btilly Dec 11 '14 at 21:23
  • @btilly: I wrote half an explanation before I fully understood the issue. My bad, you're right. – Mooing Duck Dec 11 '14 at 22:25
  • @btilly While it is certainly possible (likely?) that you're correct, it is not necessarily a given that the widgets you've constructed will fit together in the required manner. For example, the precedence constraints are very convenient for modelling AND relations but not so great at OR; the unlimited number of identical processors makes it a little trickier to model exclusion relations; etc... Meanwhile, the SAT problem (with the clauses in CNF) where all variables in a clause are either all negated or all non-negated is known as MONOTONE SAT and I believe is known to be NP-complete. – mhum Dec 13 '14 at 01:15