14
$\begingroup$

One of my friends asks me the following scheduling problem on tree. I find it is very clean and interesting. Is there any reference for it?

Problem: There is a tree $T(V,E)$, each edge has symmetric traveling cost of 1. For each vertex $v_i$, there is a task which needs to be done before its deadline $d_i$. The task is also denoted as $v_i$. Each task has the uniform value 1. The processing time is 0 for each task, i.e., visiting a task before its deadline equals finishing it. Without loss of generality, let $v_0$ denote the root and assuming there is no task located at $v_0$. There is a vehicle at $v_0$ at time 0. Besides, we assume that $d_i \ge dep_i$ for every vertex, $dep_i$ stands for the depth of $v_i$. This is self-evident, the vertex with deadline less than its depth should be taken as outlier. The problem asks to find a scheduling which finishes as many tasks as possible.

Progress:

  1. If the tree is restricted to a path, then it is in $\mathsf{P}$ via dynamic programming.
  2. If the tree is generalized to a graph, then it is in $\mathsf{NP}$-complete.
  3. I have a very simple greedy algorithm which is believed 3-factor apporoximation. I have not proved it completely. Rightnow, I am more interested about the NP-hard results. :-)

Thanks for your advice.

Improve this question
$\endgroup$
13
  • $\begingroup$ On a complete graph, the task would be easy right? Just use a simple greedy algorithm... $\endgroup$
    – Joe
    Commented Feb 13, 2012 at 0:31
  • $\begingroup$ @Joe:Yes. Because every edge needs 1 unit travelling, so there is no preference among "crossroads". Are you still interested in this problem, if yes. maybe we can talk via email. :-) $\endgroup$
    – Peng Zhang
    Commented Feb 13, 2012 at 6:18
  • $\begingroup$ What if all the deadlines are the same and/or we only ask if all the tasks can be finished? $\endgroup$
    – domotorp
    Commented Feb 13, 2012 at 8:08
  • $\begingroup$ @domotorp:If it asks to finish all the tasks with one deadline, the answer is YES if and only if the uniform deadline $d\ge |V|$. Just depth first search. As for optimal problem on the case $d< |V|$, I do not know whether it is easy. There are many variants about this problem, such as considering what if the deadlines take values from a finite set whose cardinality is a constant? Thank you very much for your comment. $\endgroup$
    – Peng Zhang
    Commented Feb 13, 2012 at 12:37
  • $\begingroup$ I would say NP-hard see the scheduling zoo, except if I misunderstood your problem. $\endgroup$
    – Gopi
    Commented Feb 13, 2012 at 15:59

3 Answers 3

Reset to default
1
$\begingroup$

Not sure this is your answer (see below) but a bit too long for the comments.

I though your problem was something like: $(P|tree;p_i=1|\Sigma T_i)$, where:

  • $P$ stands for identical homogeneous processors,
  • "tree" stands for precedence constraint the form of a tree,
  • $p_i=1$ stands for the weight of the tasks is equal to 1, and
  • $\Sigma T_i$ stands for minimizing the sum of tardiness (i.e., the number of tasks that finish after their deadline).

If this is the case, then your problem is NP-hard: you can see it as a generalization of Minimizing total tardiness on a single machine with precedence constraints. Indeed this paper states that for multiple linear chains, it is NP-hard on a single processor. The easy transformation is to take the trees of the form one root, and linear chains starting from the root.

However I am surprised because you seem to say that for the case of a single linear chain, you would use Dynamic Programming. I don't see why you would need DP, since it seems to me that when scheduling a single linear chain you do not have much choice because of the precedence constraints: only a single choice. So maybe I misunderstood your problem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ My problem seems different from yours. Mine is, "a rooted tree, travelling edge cost unit time, each vertex with a task with its deadline, task needs no time to precess. Starting from the root, how many tasks can be finished?". So there is no precedence, there is no time needed to process a task. Thank you very much. $\endgroup$
    – Peng Zhang
    Commented Feb 14, 2012 at 14:18
  • $\begingroup$ @PengZhang, If it is a rooted tree, then there are precedence? As for the cost on the edges(precedence?) or on the tasks, it seems to me to be the same thing. I really don't see the difference between both. Finally how many tasks can be finished, if you minimize the number of tasks that finish after their deadline, it is equivalent to maximizing the number of tasks that can be finished. Maybe you could draw a picture of what you are expecting? $\endgroup$
    – Gopi
    Commented Feb 14, 2012 at 18:48
  • $\begingroup$ I don't see the clear relationship between two problems. In the original problem, the cost of visiting a next node depends on which node was visited in the previous step. In precedence-constrained scheduling, the cost of a next job to process doesn't depend on which job was processed in the previous step, as long as the precedence constraint is satisfied. $\endgroup$
    – Yoshio Okamoto
    Commented Feb 15, 2012 at 5:30
  • $\begingroup$ @Gopi:the cost of edges cannot be "transferred" onto nodes, as far as I think. If the tree is restricted to a path ( maybe the chain you referred), in my problem we can dynamic programming as follows. Let vertices numbered as $1,2,\cdots, n$ from left to right. Let $f(t,l,r)$ denote the maximum tasks from position interval $[l,r]$ at time $t$ and the vehichle stands at $l$ . Let $g(t,l,r)$ denote the same thing as $f(t,l,r)$ except the vehicle stands at $r$. Then we have $f(t,l,r)$ can be derived from $\{f(\cdot,l+1,r), g(\cdot,l,r-1)$. Because $t,l,r$ are polynomial, so the dp is polynomial. $\endgroup$
    – Peng Zhang
    Commented Feb 15, 2012 at 11:54
  • $\begingroup$ @PengZhang, ok, I think I have a better understanding of what you mean. I still believe one can easily adapt the paper I gave, by considering special trees where the branches are paths (hence rooted pathes). $\endgroup$
    – Gopi
    Commented Feb 16, 2012 at 10:14
1
$\begingroup$

For this to be true, we have to make some assumptions. See comments below

For the tree case, I believe that there is a polynomial time recursive dynamic programming algorithm parameterized by the maximum deadline time. The sub-problems are: if we enter a sub-tree by time $t_a$ and exit the sub-tree by time $t_b$, what is the maximum number of tasks we can finish in the sub-tree? The base cases at the leaves are easy and we memoize from the bottom up.

If we truly parameterized by the maximum deadline time, then the algorithm would not really be polynomial in the size of the tree. However, the length of the longest path that visits every node in the tree is only polynomial in $|V|$, and we never need to check deadline times later than that.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Can you show me the recurrence? I tried the same as yours before, let $f[a, t, t']$ denote the subproblem of visiting the subtree rooted at vertex $a$. But there are two troubles. 1. How can you build your solution from the subproblems? As far as I think, enumerating the ordering of the sons is inevitable. 2. You can enter and leave a node many times. So during time slot $[t,t']$, may be you visited other vertices not in subtree rooted at $a$. Thank you very much. :-) $\endgroup$
    – Peng Zhang
    Commented Feb 8, 2012 at 7:51
  • $\begingroup$ point (1) is not as much of a problem as point (2). For my idea to work as I first envisioned it, it requires that you don't exit and re-enter a sub-tree multiple times. It's not obvious that the best solution doesn't jump all around the tree: gets a leaf, and something near the root, and walks to a leaf, and then to another leaf far away from the other 2, etc. You might be able to exploit the fact that you will get all the nodes on any path you walk though. In particular if any child has been visited, then the parent is already visited. $\endgroup$
    – Joe
    Commented Feb 8, 2012 at 9:02
  • $\begingroup$ :In my thougt, point (1) is indeed a problem. For point (2), I called the constraint "no re-entering" as "Depth First Search" constraint. The DFS constraint is commonly adopted in literatures. And under that constraint, my problem is indeed polynomial, as long as the maximum degree of the tree is a constant. So I wonder my question is NP-hard. Thank you very much. $\endgroup$
    – Peng Zhang
    Commented Feb 8, 2012 at 9:19
  • 4
    $\begingroup$ Regarding the the DFS constraint, it is easy to construct an example where the optimal sequence violates this constraint. Consider a complete, balanced binary tree with 7 nodes. Let the 2 leaves in the left subtree have deadlines 2 and 12, the 2 leaves in the right subtree have deadlines 8 and 6, and internal nodes have deadlines 100. You can visit all nodes by visiting the leaves in order 2,6,8,12; any other order violates at least one deadline. $\endgroup$
    – mhum
    Commented Feb 15, 2012 at 1:02
0
$\begingroup$

The problem of getting a constant approximation for this case or proving it NP-Hard are still open and any result would make a good publication. Some special cases have been solved. I, along with others, have some partial results that solve special cases like spiders, constant-height trees. But, the general problem for trees is unsolved.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.