PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
As is the case with many challenge problems, this problem is NP-hard. It is often called the “Concurrent Open Job Shop” problem in research
literature. There is, however, one simplification that can be made. That is, we can restrict our attention to solutions where the cakes are scheduled
in the same order by all bakers for the following reason. Consider a solution S and say baker i works the longest overall (i.e. has the largest sum
of preparation times) and processes cake j last in S. Adjust S by moving cake j to the end of every baker’s schedule while not changing the
relative order of the remaining cakes. The completion time of every cake j’ != j is not decreased since their completion time by each individual
baker does not decrease. The completion time of cake j does not decrease since baker i worked the longest so all other bakers i’ != i still
complete cake j no later than baker i. Recursively apply these arguments to the remaining cakes j’ != j.
The problem can, however, be approximated somewhat well. The following O(n * (n+m)) algorithm finds a solution whose weighted completion
time is no more than 2 times the optimum. Denote the weight of customer j by w(j) and the processing time of cake j by baker i by p(j,i). Let I
be the baker that will work the longest (i.e. maximizes p(j _ 1, i) + p(j _ 2, i) + … + p(j _ n, i)) and let j be the cake j that minimizes w(j)/p(j,i). Add
cake j to the end of the schedule we will recursively compute on the remaining cake. For each job j’ != j, update w(j’) := w(j’) - w(j) * p(j’,i)/p(j,i).
Recursively compute a schedule on the remaining cakes j’ != j according to these new weights and add cake j to the end of this schedule.
The arguments showing why this is a 2-approximation are subtle and can be found in [1]. Assuming P != NP, one cannot approximate this problem
within any constant better than 6/5 with a polynomial-time algorithm
[1]. Finally, even approximating this problem within a constant better than 2 will refute a fundamental open conjecture known as the
“Unique Games Conjecture” (independently shown in [2] and [3]). So, while this
conjecture is still open we do not know how to guarantee a better-than-2 approximation in polynomial time.
[1] M. Mastrolilli, M. Queyranne, A. Schulz, O. Svensson, and N. Uhan, Minimizing the sum of weighted completion times in a concurrent open shop.
Operations Research Letters (2010), doi:10.1016/j.orl.2010.04.011
[2] N. Bansal and S. Khot, Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. Preprint available at Subhash’s
page Subhash Khot
[3] A. Kumar, R. Manokaran, M. Tulsiani, N. Vishnoi, On LP-based approximability for strict CSPs. Preprint available at
[0912.1776] On the Optimality of a Class of LP-based Algorithms