1.    Show whether the following problem is unimodular, and state the significance of your

answer:

Minimise 2x1 + 3x2 – x3

s.t.

x1 + x3  >= 5

x2 -x3  >= 3

x1-x2 <= 4

x1, x2, x3  >= 0

2.    State the strengths and weaknesses of (i) greedy heuristics (ii) steepest descent (iii) simulated annealing

3.    Explain (i) tabu search (ii) a memetic algorithm and state any parameters required.

Scheduling

1.    Consider the following set of jobs:

Find the sequence of jobs that result from using (i) longest processing time (ii) critical ratio. You can assume there is only one machine.

Also find the sequence of jobs  from Moores Algorithm.

Also find a sequence using earliest due date on 2 identical machines.

2.    Consider the following set of jobs on 4 machines:

Find the best schedule using Johnsons Algorithm.

Dynamic Programming

1.    Consider the following road network, consisting of one way routes: Starting Town               End Town                      Distance

A                                         B                                         32

A                                         C                                         26

A                                     D                                         15

B                                     E                                         10

B                                     F                                         8

C                                     D                                        5

C                                         E                                         8

C                                     F                                         14

D                                     E                                         27

D                                         F                                         17

D                                     G                                        37

E                                      F                                         3

E                                     G                                        22

F                                     G                                         12

Find the shortest distance from A to G using Dynamic Programming.

2.   A company that make roadsweepers is planning its production for the next four months.  Although it knows the demand for its product in months 3 and 4, it is uncertain about the demand for the first two months. It believes the demand for its product is as follows:

The company can make up to 4 roadsweepers per month and it costs £5, 000 to make one           roadsweeper, £9, 500 to make two roadsweepers, £13, 000 to make three roadsweepers and     £16, 000 to make four roadsweepers. Storing a roadsweeper costs £1, 000 per month. Given the company starts this period with zero roadsweepers in stock and wishes to end the four months