Suppose there are $n$ jobs $J_1, \ldots, J_n$ that need to be completed using $m$ machines $M_1, \ldots, M_m$. Each job $J_i$ consists of a set $S\left(J_i\right)$ of $k_i$ sub-chores $s_1, \ldots, s_{k_i}$. Let $S(J)=\bigcup_{i=1}^n S\left(J_i\right)$ denote the overall collection of all the sub-chores. Each sub-chore $s \in S(J)$ needs to be scheduled on a given machine $ M(s) \in { M_1, \ldots, M_m } $ and has a certain processing time $p(s)$, all of which is known to you. The condition we insist upon is that for any $i \in[n]$, no two sub-chores from $S\left(J_i\right)$ can be processed such that they overlap, i.e., each sub-chore from $S\left(J_i\right)$ has to end before another one from $S\left(J_i\right)$ can begin. The sub-chores themselves can be processed in any order. The goal is to schedule the given sub-chores such that the time at which all sub-chores have been completed is minimized.


I need to come up with an efficient algorithm for solving this problem that will lead to a 2 approximation to the optimal solution and prove that the algorithm is capable of achieving a 2-approximation to the optimal solution.

Resources I looked at

From what I understand this is a spin-off of the regular load balancing question which is similar to this question, but uses jobs instead of subjobs and doesn't restrict some jobs to run sequentially.

In Klienberg and Tardos (pg.600) they lay out an approach for the regular load balancing question where you use a greedy solution which minimizes the current load on any machine, and this approach yields a 2 approximation.

Their approach makes use of the fact that $T^* \ge \frac{1}{m} \sum _ j t_j$ and $T^* \ge \max_j (t_j)$ which states that the optimal makespan is greater (or equal to) the average of all possible durations of each job and that it is greater than the longest job.

They then consider the final job added to the machines and because it was added in a greedily manner we can deduce another inequality which finally arrives at the 2-approximation.

What I tried

I believe we should take a greedy approach, where we just consider all subjobs and put them at the earliest point such that they satisfy the sequential constraints. (Also let $T^*$ be the optimal solution)

I also tried to get some similar constraints with respect to the book. So the time at which all sub-chores are completed is at least the sum of the "job collection" $S(J_k)$ whose total duration (sum of all it's sub jobs) is maximal. Which could be written as

$$ T^* \ge \max _ {i \in 1, ..., n} (\sum _ {s_j \in S(J_i) } s_j) $$

This is because within each job collection none of the sub jobs can be parallelized, and thus all must be run sequentially. (Let $J(S_o)$ be this maximal job collection)

Also we have a similar averaging constraint over the sub jobs but with respect to $J(S_o)$:

$$ T^* \ge \frac{1}{m} \sum _ {s _ j \in J(S_o) } s_j $$

because if this is not true, then there would not be enough time "scheduled" to support the sub jobs from the maximum job collection.

I believe that next we would take a similar approach to Klienberg and Tardos on page 603 where we consider the last sub job added to the machines to then deduce a new inequality which helps us get to the 2-approximation.

But I'm stuck here because of the complexity that comes with adding the jobs in a way so that they don't overlap with jobs from the same job collection. Can anyone provide some insight on how to get un-stuck and complete the problem?



Your Answer

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