J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

UG examination 2000

Answer FOUR questions.
All questions carry equal marks.
If more than four questions are answered only the first four answered will be marked.
Marks will be deducted in this examination if there is insufficient written explanation.

Question 1

An operational research worker is analysing brand switching between different airlines by frequent flyers. For the purposes of his analysis he has chosen a number of routes on which three different airlines A, B and C operate similar timetables and similar fares. He hascollected the following data.

                  To airline     
                 A      B    C 
From airline   A 0.90 0.03 0.07 
               B 0.15 0.80 0.05 
               C 0.20 0.30 0.50 

For example, a frequent flyer who last travelled by airline A has a probability of 0.90 of next travelling by airline A, 0.03 of next travelling by airline B and 0.07 of next travelling by airline C. Currently airlines A, B and C have 20%, 50% and 30% of the market respectively.

Question 2

A company requires a part X at the rate of 300 units per week. Part X is purchased from an external supplier who charges the company £10 for delivery of an order and £2.50 for each part purchased. The company estimate that its internal costs associated with making an order are £12.50. Assume interest rates are 5% per year and the warehousing costs associated with storage and maintenance are £0.40 per unit per year.

Your current supplier is prepared to give you three options for ordering:

Which of these options would you recommend? Give your reasons.

Question 3

. The demand for two products in each of the last four weeks is shown below.

Week               1   2   3   4 
Demand - product 1 134 212 345 467 
Demand - product 2 102 132 169 204

For product 1 calculate a forecast for week 5 using a two week moving average. For product 2 calculate a forecast for week 5 using exponential smoothing with a smoothing constant of 0.9.

These products are produced in an assembly line involving two machines (A and B). To produce one unit of product 1 requires 10 minutes processing on machine A followed by 15 minutes processing on machine B. To produce one unit of product 2 requires 3 minutes processing on machine B, then 3 minutes processing on machine A and finally a further 4 minutes processing on machine B. Currently there are 97 units of product 1 and 45 units of product 2 in stock.

Available working time on machines A and B in week 5 is forecast to be 20 and 27 hours respectively. If these machines are not sufficient to produce all of the required demand of product 1 and product 2 additional units can be bought from an external supplier at a cost of £15 for each unit of product 1 purchased and £25 for each unit of product 2 purchased.

Question 4

The following table defines the various activities in a small construction project:

Activity    Completion time (weeks) 
A                 4 
B                 5
C                 2 
D                 9 
E                 7 
F                 6 
G                 5 
H                 2 
I                 4
J                 3 
K                 5 
L                 6

The immediate precedence relationships are:

Activity                          Activity 
number                            number 
A         must be finished before D,E,F can start 
B                                 G 
G                                 I 
H                                 J,K,L 
E                                 J 
C                                 B 
J,K                               I 

In addition there must be a time lag of at least 4 weeks between the end of activity D and the start of activity G.

Question 5

A national store chain has decided to investigate using data envelopment analysis to compare stores. Previously they have used ratio analysis to compare their stores. As a pilot study they have taken seven of their local branches. The data for these branches is shown below.

Branch   Turnover   Floor        Personnel cost 
         (£'m)      space        (£'000) 
                    (sq metres)
A        1.3        1100         150 
B        3.4        2600         250 
C        2.6        2510         370 
D        0.9         800         240 
E        2.8        1300         340 
F        4.7        3900         780 
G        3.4        2900         340

For example branch A had a total turnover of £1.3 million, has a floor space of 1100 square metres and a total personnel cost of £150,000. All of these figures relate to the previous accounting year.

Question 6

In an airport terminal building there are a number of gates. These gates are used for passengers to board departing aircraft. To ease the problem of assigning gates to aircraft the terminal operator has divided time into 15 minute "slots". Once assigned to a gate each aircraft is allowed two of these slots (i.e. 30 consecutive minutes) for the purposes of boarding. Once an aircraft has finished boarding then the gate must be left free for 15 minutes before another aircraft can be assigned to it.

Currently there are 10 aircraft scheduled for boarding. Their details are as below:

Aircraft  Earliest slot   Latest slot 
1               3              4 
2               2              5 
3               1              1 
4               4              5 
5               2              3 
6               1              3 
7               1              2 
8               3              5 
9               3              4 

10              3              5

For example the earliest at which aircraft 1 needs a gate is slot 3 (i.e. 45 minutes from the current base time of zero) and the latest time at which they would like a gate is slot 4 (i.e. 60 minutes from the current base time of zero). The terminal operator commonly refers to "slot time" and hence would say that aircraft 1 has a slot time window of [3,4].

Currently there are four gates available to assign to these aircraft. In the event that no gate can be assigned to an aircraft within its slot time window then the terminal operator suffers a penalty cost of £500 for each unit of slot time that an aircraft has to wait outside its slot time window before it is assigned to a gate.

Formulate the problem of assigning gates to aircraft as a zero-one integer linear program.