-2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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.] $\endgroup$
    – Neal Young
    Nov 23 '20 at 15:41
  • $\begingroup$ 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. $\endgroup$
    – Chip Bell
    Nov 23 '20 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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