<p>As I think about this, I'm thinking this may be far easier than I think. However, I don't think I could prove this rigorously.</p>
<p>My intuition tells me that the task with the longest inactive time should go first, since it'll take longer to finish. While that first inactive task is running, you could perform more active tasks and therefore increase concurrency. So, my guess is that <em>sorting by <span class="math-container">$b_k$</span> descending</em> is the correct ordering.</p>
<p>Again, I have no proof so I don't consider this a &quot;full&quot; answer.</p>

CC BY-SA 4.0
2020-11-23T15:41:21.603Z
Suppose you have a solution that is not sorted by decreasing $b_k$.  Then there are two consecutive jobs, say, $(a'_1, b'_1)$ followed by $(a'_2, b'_2)$, where $b'_1 < b'_2$.  Consider swapping these two jobs.  Can this make the solution worse?  Note that the finishing times of other jobs are unaffected by the swap.  [Note: this is not really a research-level question in TCS, so should probably be migrated to cs.stackexchange.com.]
Neal Young
CC BY-SA 4.0
2020-11-23T23:50:43.637Z
Awesome, thank you! And you're right I realized _after_ posting that I should have posted in Computer Science instead. I've actually [posted my full problem there](https://cs.stackexchange.com/questions/132565/modified-topological-sort).
Chip Bell
CC BY-SA 4.0
2020-11-23T14:17:52.393Z
2020-11-23T14:17:52.393Z
Chip Bell
<p>I've been thinking through a problem, and I won't go into all the details here but I'm stumped on a particular subproblem:</p>
<p>Consider this following definition of a task: <span class="math-container">$T_k = (a_k, b_k)$</span>. <span class="math-container">$a_k$</span> is the amount of time I would spend actively working on that task. <span class="math-container">$b_k$</span> is the amount of time that the task would run idly <em>after I finish the active portion</em>. A good example is washing clothes: it might take <span class="math-container">$a_k = 5$</span> minutes for me to load the washing machine, and then <span class="math-container">$b_k = 40$</span> minutes for the cycle to complete. During this &quot;inactive time&quot; I could go do something else.</p>
<p>So, imagine I have a set of tasks <span class="math-container">$S = \{ T_1, T_2, ... \}$</span>. One question might be &quot;in what order should I perform those tasks such that the time to completion is minimized?&quot;</p>
<p>Here's a trivial example: <span class="math-container">$S = \{ (1, 2), (2, 1) \}$</span>. Doing task 1 first would take <span class="math-container">$1 + 2 + 1 = 4$</span> minutes since the first task's &quot;inactive time&quot; of 2 minutes will occur while I'm doing task 2. If I did the task 2 first, it would take <span class="math-container">$2 + 1 + 2 = 5$</span> minutes and the second task's inactive time would finish while I'm doing the first task. So, clearly order matters.</p>
<p>What I'm stumped on is, given that I want to find an ordering that minimizes the time to completion, is there a way that I can figure out that ordering without considering every possible ordering? My gut says there's some greedy criteria for sorting <span class="math-container">$S$</span>, but I cannot seem to find it. Does it exist? Is there a way to prove it doesn't?</p>

<partial-order><greedy-algorithms>
Finding a greedy ordering criteria
Chip Bell
# Finding a greedy ordering criteria

(Asked by: username_0 on 2020-11-23)

I've been thinking through a problem, and I won't go into all the details here but I'm stumped on a particular subproblem:

Consider this following definition of a task: $T\_k = (a\_k, b\_k)$. $a\_k$ is the amount of time I would spend actively working on that task. $b\_k$ is the amount of time that the task would run idly *after I finish the active portion*. A good example is washing clothes: it might take $a\_k = 5$ minutes for me to load the washing machine, and then $b\_k = 40$ minutes for the cycle to complete. During this "inactive time" I could go do something else.

So, imagine I have a set of tasks $S = \{ T\_1, T\_2, ... \}$. One question might be "in what order should I perform those tasks such that the time to completion is minimized?"

Here's a trivial example: $S = \{ (1, 2), (2, 1) \}$. Doing task 1 first would take $1 + 2 + 1 = 4$ minutes since the first task's "inactive time" of 2 minutes will occur while I'm doing task 2. If I did the task 2 first, it would take $2 + 1 + 2 = 5$ minutes and the second task's inactive time would finish while I'm doing the first task. So, clearly order matters.

What I'm stumped on is, given that I want to find an ordering that minimizes the time to completion, is there a way that I can figure out that ordering without considering every possible ordering? My gut says there's some greedy criteria for sorting $S$, but I cannot seem to find it. Does it exist? Is there a way to prove it doesn't?

**Tags:** partial-order, greedy-algorithms

---

## 1 answers

### Answer by username_0 on 2020-11-23. Score: 0

As I think about this, I'm thinking this may be far easier than I think. However, I don't think I could prove this rigorously.

My intuition tells me that the task with the longest inactive time should go first, since it'll take longer to finish. While that first inactive task is running, you could perform more active tasks and therefore increase concurrency. So, my guess is that *sorting by $b\_k$ descending* is the correct ordering.

Again, I have no proof so I don't consider this a "full" answer.

> **Comments:**
> **username_1**: Suppose you have a solution that is not sorted by decreasing $b_k$.  Then there are two consecutive jobs, say, $(a'_1, b'_1)$ followed by $(a'_2, b'_2)$, where $b'_1 < b'_2$.  Consider swapping these two jobs.  Can this make the solution worse?  Note that the finishing times of other jobs are unaffected by the swap.  [Note: this is not really a research-level question in TCS, so should probably be migrated to cs.stackexchange.com.]  
> **username_0**: Awesome, thank you! And you're right I realized _after_ posting that I should have posted in Computer Science instead. I've actually [posted my full problem there](https://cs.stackexchange.com/questions/132565/modified-topological-sort).  

---

