5-4. An Assignment Problem: In a job shop operations, four jobs may be performed on any of four machines. The hours required for each job on each machine are presented in the following table. The plant supervisor would like to assign jobs so that total time is minimized. MACHINE Job 10 14 13 M 16 15 12 B 12 13 12 9 12 16 11 16 D 14 18 (a). Formulate this problem as a linear program problems. There are examples in the book. (b). Find the best solution (using any LP software or any other method, such as the Hungarian Method). Which jobs should be assigned to which machines? What cost? To use the Hungarian Method, do the following: Select the lowest value in each row and subtract that from every other value in the row. Now each row would have a zero. . Select the lowest value inn each column and subtract that from every other value in the column (if the column does not already have a zero). Now both the rows and columns would have zeros (at least one) Test for Optimality: Cross out all the zeros using minimum number of lines, drawing lines horizontally or vertically (not diagonally). If the number of lines you took to strike out the zeros is equal to the number of rows, optimality achieved. Assign the jobs focusing on the columns that have zeros. Remember: One to one assignment! . If optimality not achieved: Take the lowest uncovered value, subtract that from all the uncovered values, add it to the intersection point and strike out the zeros again. Check again if optimality is achieved