Problem 1. Suppose you're consulting for a biotech company that runs experiments on two identical testing machines, 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 t; > 0. They need to split the jobs into two groups where one group is assigned to M1 and the other to M2. Let T be the total time to do all jobs assigned to M1, and let T2 be the total time to do all jobs assigned to M2. The problem is to have the two machines work roughly for the same amounts of time, that is, to minimize the objective function |T1 - T2]. a) You decide to first implement the brute-force approach. Describe the search space and give its size in terms of the total number of jobs n. b) After some brainstorming, you propose an alternative approach as follows. Start by assigning jobs to the two machines arbitrarily (say jobs 1, ..., n/2 to M1, the rest to M2). You loop through all jobs 1...n and move the job to the other machine if the move decreases the absolute difference in the processing times. You repeat this loop as many times as necessary, until there is no move that makes the absolute difference decrease any further. Let tmin be the processing time of the smallest job on the machine with the higher load. Explain how you know that at termination, the difference in processing times is at most tmin. In other words, argue why T1 - T2 0. They need to split the jobs into two groups where one group is assigned to M1 and the other to M2. Let T be the total time to do all jobs assigned to M1, and let T2 be the total time to do all jobs assigned to M2. The problem is to have the two machines work roughly for the same amounts of time, that is, to minimize the objective function |T1 - T2]. a) You decide to first implement the brute-force approach. Describe the search space and give its size in terms of the total number of jobs n. b) After some brainstorming, you propose an alternative approach as follows. Start by assigning jobs to the two machines arbitrarily (say jobs 1, ..., n/2 to M1, the rest to M2). You loop through all jobs 1...n and move the job to the other machine if the move decreases the absolute difference in the processing times. You repeat this loop as many times as necessary, until there is no move that makes the absolute difference decrease any further. Let tmin be the processing time of the smallest job on the machine with the higher load. Explain how you know that at termination, the difference in processing times is at most tmin. In other words, argue why T1 - T2