Mech Eng IV

Operations Research

1994

1. Write an essay on each one of the following.

The scheduling of projects using activity networks.
The Travelling Salesman Problem.

Describe Dijkstra's Algorithm for finding a minimum length path in a graph and Kruskal's Algorithm for finding a minimum weight spanning tree in a graph, and analyse the computational complexity of these two algorithms.
Describe an algorithm for finding a maximum flow in a basic network and show how this algorithm can be used to prove the Maximum Flow Minimum Cut Theorem.

3. Consider an M|M|1|c queue with mean arrival rate l, mean service rate m (l š m) and finite capacity c. Let p_n denote the probability that there are n customers in the system after the queue has settled down and let L be the average number of customers in the system, again when the system has settled down. Prove that,

p_n =

rⁿ(1-r

1-r^c+1

and

L =

1-r

(c+1)r^c+1

1-r^c+1

where r = l/m.

A barber's shop has a total seating capacity of 10 (including the chair for the customer being served). The lone barber takes an average of 12 minutes to cut a customer's hair, and an average of 20 customers arrive each hour at the shop (arrival and service patterns are Poisson). Customers who arrive when the shop is full go to a different barber. How many customers per hour are lost, on average, due to the shop's restricted seating space?

File translated from T_EX by T_TH, version 2.00.
On 23 Dec 1999, 14:29.