3. (a) Describe how you would solve the travelling salesman problem using: i. Random Descent [5 marks] ii. Genetic Algorithm [6 marks] (b) Consider the following set of 6 jobs, together with their durations and due dates. Job Duration Due Date A 27 80 B 16 69 20 67 D 38 70 E 19 75 F 22 100 i. Assuming there is only one machine, find a sequence of jobs using the critical ratio method and state the average tardiness. [6 marks] ii. Assuming there is only one machine, use Moores Algorithm to find the se- quence with the minimum number of late jobs. [4 marks) iii. Assuming there are two identical machines, find a new schedule using the Earliest Due Date Method. [4 marks]