<p>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: </p>

<ol>
<li>The time it takes to be completed ($t_i$) and,</li>
<li>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 <em>rewarded</em> $u_i$ after $t_i$).</li>
</ol>

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

<hr>

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

<hr>

<p>Two quick questions:</p>

<ol>
<li>What are the known approaches to this problem?</li>
<li>What if $u_i$ is defined as a function over time so that we are rewarded while we are completing the task?</li>
</ol>

<p>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:</p>

<p>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 <em>density function</em>: $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.</p>

<p>This would lead to the following formal definition of our problem:</p>

<hr>

<p>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:</p>

<p>$\sum\limits_{t=1}^T F_{\pi,t}$</p>

<hr>

<p>Thank you very much,</p>

CC BY-SA 3.0
2014-05-23T15:01:55.787Z
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.
Saeed
CC BY-SA 3.0
2014-05-26T07:26:33.803Z
@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.
Carlos Linares López
CC BY-SA 3.0
2014-05-26T08:54:17.510Z
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.
Saeed
CC BY-SA 3.0
2014-05-26T13:15:09.350Z
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?
Carlos Linares López
CC BY-SA 3.0
2014-05-26T13:45:36.090Z
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.
Saeed
CC BY-SA 3.0
2014-05-26T13:52:14.593Z
Well I have no idea to prove or disprove my above observation as otherwise I was going to provide an answer. But in a fractional case, we can optimize the total aggregation simply by a greedy algorithm. (if u over time is trivial function). Anyway maybe someone already considered your problem in a variation of knapsack problem.
Saeed
CC BY-SA 3.0
2014-05-27T07:51:30.710Z
Hey Saeed! You are definitely right. Sorry I was too eager to see a solution to the problem :) Actually your answer makes a lot of sense and the reason I am asking is because we are interested in related work. Strikingly, we've found none! Thanks a lot again
Carlos Linares López
<ds.algorithms><optimization><scheduling>
Are there any approaches to the following scheduling problem?
Carlos Linares López
# Are there any approaches to the following scheduling problem?

(Asked by: username_0 on 2014-05-23)

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,

**Tags:** ds.algorithms, optimization, scheduling
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_1**: Well I have no idea to prove or disprove my above observation as otherwise I was going to provide an answer. But in a fractional case, we can optimize the total aggregation simply by a greedy algorithm. (if u over time is trivial function). Anyway maybe someone already considered your problem in a variation of knapsack problem.  
> **username_0**: Hey Saeed! You are definitely right. Sorry I was too eager to see a solution to the problem :) Actually your answer makes a lot of sense and the reason I am asking is because we are interested in related work. Strikingly, we've found none! Thanks a lot again  

---

## 0 answers

