Suppose you're consulting for a biotech company that runs experiments on two expensive...

Suppose you're consulting for a biotech company that runs experiments on two expensive high-throughput assay machines, each identical, which we'll label M1 and M2. Each day they have a number of jobs that they need to do, and each job has to be assigned to one of the two machines. The problem they need help on is how to assign the jobs to machines to keep the loads balanced each day. The problem is stated as follows. There are n jobs, and each job j has a required processing time tj. They need to partition the jobs into two groups A and B, where set A is assigned to M1 and set B to M2. The time needed to process all of the jobs on the two machines is  The problem is to have the two machines work roughly for the same amounts of time—that is, to minimize |T1 – T2|.

A previous consultant showed that the problem is NP-hard (by a reduction from Subset Sum). Now they are looking for a good local search algorithm. They propose the following. Start by assigning jobs to the two machines arbitrarily (say jobs 1, …, n/2 to M1, the rest to M2). The local moves are to move a single job from one machine to the other, and we only move jobs if the move decreases the absolute difference in the processing times. You are hired to answer some basic questions about the performance of this algorithm.

(a) The first question is: How good is the solution obtained? Assume that there is no single job that dominates all the processing time— that is, that  for all jobs j. Prove that for every locally optimal solution, the times the two machines operate are roughly balanced: .

(b) Next you worry about the running time of the algorithm: How often will jobs be moved back and forth between the two machines? You propose the following small modification in the algorithm. If, in a local move, many different jobs can move from one machine to the other, then the algorithm should always move the job j with maximum tj. Prove that, under this variant, each job will move at most once. (Hence the local search terminates in at most n moves.)

(c) Finally, they wonder if they should work on better algorithms. Give an example in which the local search algorithm above will not lead to an optimal solution.