# Finding a greedy ordering criteria

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?

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.
• 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.] Nov 23 '20 at 15:41