0
$\begingroup$

Consider the following problem: we are given $K$ tasks $\langle n_1, n_2, ..., n_K \rangle$. Every task $n_i$ is qualified with two parameters:

  1. The time it takes to be completed ($t_i$) and,
  2. The utility of completing it, $u_i$. Let us assume that $u_i$ is a scalar value which represents a revenue that is obtained after completing task $n_i$ (so that we are rewarded $u_i$ after $t_i$).

All tasks are affordable and there are no constraints among them. Once one is started it has to be completed before permuting to a different one. It is clear that the total revenue is constant and it is equal to $U=\sum\limits_{i=1}^K u_i$. It is also obvious that this reward will be obtained in a total time equal to $T=\sum\limits_{i=1}^K t_i$.

We are interested, however, in computing the best arrangement (or permutation) of the $K$ tasks that anticipates the rewards as much as possible

Two quick questions:

  1. What are the known approaches to this problem?
  2. What if $u_i$ is defined as a function over time so that we are rewarded while we are completing the task?

What follows is a particular attempt to put the problem on a formal basis so that comments to this part would be also very welcome. Answers are not expected to necessarily go along the same lines:

For a particular arrangement $\pi:\langle n_1, n_2, ..., n_K \rangle$ let us $X$ denote the random variable that represents the utility over the interval $(0,T]$. Thus, let $f_{\pi, t} = p(X=x,t)$ denote the probability that the random variable $X$ is exactly equal to $x$ in the instant $t\leq T$. This reasoning suggests that the optimization metric should be the area inscribed by the density function: $F_{\pi, t}=p(X\leq x, t)$. Both $f$ and $F$ are subscripted with $\pi$ and $t$ because every problem defines different curves and different values of $t$ yield different results.

This would lead to the following formal definition of our problem:

Given $K$ tasks $\langle n_1, n_2, ..., n_K \rangle$ each qualified with the utility $u_i$ of completing it and the time required to complete it, $t_i$ find the optimal permutation $\pi^*$ among the $K!$ plausible permutations $\pi$ such that the following is maximized:

$\sum\limits_{t=1}^T F_{\pi,t}$

Thank you very much,

Improve this question
$\endgroup$
7
  • $\begingroup$ Consider this variation: Given a time T, we want to maximize benefit at this time, then the problem is same as 0-1 knapsak problem, time here is weight and T is the basket size and utility is value. The problem is weakly NP-complete because we can simply use same dynamic programming approach as knapsak for this version. I think for your general case this also works. And if $u_i$ is defined over a time, then simple greedy algorithm works. $\endgroup$
    – Saeed
    Commented May 23, 2014 at 15:01
  • $\begingroup$ @Saeed: Thanks for the reply! Please note that all tasks are performed. There is no knapsack problem. We know for sure that we will get an overall utility U after total time T. The problem here is to maximize the utility as a function defined over time. If you prefer it, I can try out a couple of examples where different permutations yield the same overall U and T but with different profiles over time. Each has its own area and we are trying to find out a way to compute the one that yields the largest area. $\endgroup$
    – Carlos Linares López
    Commented May 26, 2014 at 7:26
  • $\begingroup$ I already considered this and by noticing this I wrote previous comment. Please reread my comment, without thinking that it's not related to knapsak (without your own bias), if still you think my comment is not valid, then I'll provide an example. Just notice that the T that I mentioned is not total time is some time between zero and total time (Suppose total time is S then $0\le T\le S$). It's exactly knapsack, in knapsack we know the total weight and total value but for a particular weight we don't know best value. $\endgroup$
    – Saeed
    Commented May 26, 2014 at 8:54
  • $\begingroup$ Hi there Saeed! Thanks again for helping. What I actually understood is that you propose to compute the temporal variant of the knapsack problem for every $T$, $0\leq T\leq S$ an this would actually provide optimal solutions for a specific $T$. What I do not see is what does it tell us about the optimal solution at time $S$ where all items fit the knapsack. Recall that we are interested in the best order of tasks such that the area representing the benefit is maximized. I do not see any information about order in the solution of a knapsack problem. What am I missing? $\endgroup$
    – Carlos Linares López
    Commented May 26, 2014 at 13:15
  • $\begingroup$ Carlos, you are right, and if you see my first comment I said this is a variation (and second comment was explanation of first not your question), my intention was to say that even for a particular time it's NP-complete, that motivates perhaps total aggregation is even harder. So I didn't provide it as answer because it is not really the original one, and I just tried to mention the problem is almost NP-hard and just in a case that you looking for a polynomial algorithm I think there is no polynomial one, but may be for your general case similar dynamic programming as knapsack works. $\endgroup$
    – Saeed
    Commented May 26, 2014 at 13:45

0

Reset to default

Your Answer

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