Problem 4 Job Distribution (19%) A well-known problem in optimization and combinatorics can be described as follows: Given n jobs and m machines, where n> m, and a list of how long each of the n jobs takes (positive integer), find a breakdown of these n jobs on These are the machines so that the total time (= end of the last job) is minimized. There are no addictions between the jobs so all n jobs can be performed in parallel and can be distributed freely on the machines, but if you have started a job on a particular machine, it can not be interrupted but must be completed on that machine. For example: If n = 6, m = 2 and the times are given by (4, 2, 6, 2, 4, 1) (ie job 0 takes 4 time units, job 1 takes 2 time units, ..., etc.) can we distribute the jobs on the two machines by the following distribution: Machine 0: 0, 1, 4 Machine 1: 2, 3, 5 which date4 + 2 + 4 = 10formator0 and 6 + 2 + 1 = 9formator1, ie total time10 (maximum of 10 and 9). This distribution can be represented by an array of length n, where the j-te element is k if job j is distributed to machine k. In each example this will be (0, 0, 1, 1, 0, 1). In order to find the optimal solution, you must generally use algorithms with exponential complexity. However, one can find a good approach with the following algorithm: If we still have jobs that are not distributed on a machine, find the largest of these and let that machine (or one of the machines) performing the least work until now perform this job . This can be implemented by using two heaps, a maximum (high number = high priority) for the jobs, and a minimum (low number = high priority) for the machines. 4a (4%) Suppose you have received the following 9 jobs (n = 9) with times given (1, 5, 6, 15, 5, 4, 7, 3, 1). We insert 9 pairs (time, job ID) into a priority queue based on a maximum budget. Draw the heap you get by inserting the pairs one at a time in the given order. 4b (6%) Suppose you are given m = 3 machines, all with start time 0 (no jobs distributed to any machines). We make a priority queue for the machines based on a minimum rent; The machines are sorted by the time they already use to perform the jobs they have been assigned. Show the first two rounds of the following algorithm: 1. Get the largest item from the priority queue for jobs from a shared assignment (a). 2. Get the smallest item from the priority queue for machines. 3. Distribute the job (from item 1) to the correct machine and calculate new time for this machine. 4. Put the machine back in the priority queue for machines, with new times. For each round, show how the priority queues change (you do not need to show intermediate steps).

4c (9%) Type the method in Java that implements the algorithm over. The method should include integers n and m and an array int [] t, and shall return an array of length n that shows the final distribution of the n jobs on those machines. You can assume that you have the following class available:

class Pair implements Comparable { int time; int id; Pair(int time, int id) \ this.time time; this.id - id; public int compareTo (Object o) { air) o, return this.time - a2.time; class Pair implements Comparable { int time; int id; Pair(int time, int id) \ this.time time; this.id - id; public int compareTo (Object o) { air) o, return this.time - a2.time