OPERATION RESEARCH

UNIT-III

Queuing theory: Types of queuing situation, Queuing models with Poisson's input and
exponential service, their application to simple situations.

Network Models: PERT & CPM, Introduction, analysis of time bound project situations,
construction of net works, identification of critical path, slack and float, crashing of network for
cost reduction.

QUEUING THEORY

Queuing theory deals with problems which involve queuing (or waiting). Typical examples
might be:

 banks/supermarkets - waiting for service

 computers - waiting for a response
 failure situations - waiting for a failure to occur e.g. in a piece of machinery
 public transport - waiting for a train or a bus

As we know queues are a common every-day experience. Queues form because resources are
limited. In fact it makes economic sense to have queues. For example how many supermarket
tills you would need to avoid queuing? How many buses or trains would be needed if queues
were to be avoided/eliminated?

In designing queueing systems we need to aim for a balance between service to customers (short
queues implying many servers) and economic considerations (not too many servers).

In essence all queuing systems can be broken down into individual sub-systems consisting
of entities queuing for some activity (as shown below).
FEATURES OF QUEUING SYSTEM
Most important features of queuing model are as under:

1. Length of the queue. It indicates the average number of customers waiting in the line Large
queues indicate poor server and small queue imply too much server capacity

2. System. System means maximum capacity of the queue i.e.

System = Customers Waiting + Customer being served.

3. Waiting Time. This is the average time that a customer has to wait to get service. If waiting
time is too much long, it may result in potential loss of revenue and set back to the goodwill of
the business

4. Total Time. Total time means time taken from entry in the queue to completion of service

5. Idle Time. The relative frequency for which service system remain idle. Idle time leads to
increase in the related cost

6. Arrival Pattern. The pattern of arrival of customers at service station is known as arrival
pattern of queue. The arrival pattern can be regular or it can be irregular as at random intervals of
time. A regular pattern of arrival is not very common in the case of customers coming for
service. Generally, it is completely at random. In case the number of customer is very large, the
probability of an arrival in next interval of time does not depend upon the number of customers
already in the system. Rather where the number of customers in large the arrival is completely at
random and it follows Poisson distribution with mean equal to average number of arrivals per
unit of time.

A simple test to verify that the collected data follow Poisson distribution i.e. are truly random, is
to substitute the mean of one distribution in the following equation and obtain the mean of the
other distribution.

Mean of Exponential = 1/Mean of Poisson

7. Service Pattern. Although arrival pattern is random in most situations and can be
satisfactorily modelled by using the Poisson distribution, service pattern exhibits no obvious or
consistent pattern. However for the sake of simplicity, and in order to reduce the necessity of
complex mathematically models, simple queue theory assumes that service pattern can be
represented by treating them as being exponential.

8. Service Management. For producing service to the incoming customers at the Service Station
certain service points are established. The number of these service points mostly depends upon
the number of customers, rate of arrivals time taken for providing service to a single customer,
availability of persons/resources for producing service etc. Depending upon those variables, a
customer service channel can be either a single channel or a multichannel.

DISCIPLINE.
Some common service discipline are

(a) FIFO. A customer that finds the service center busy goes to the end of the que.
(b) LIFO. A customer that finds the service centre busy proceeds immediately to the head of the
queque. She will be served next, given that no further customers arrive.
(c) Round robin. Every customer gets a time slice. If the service is not completed, she will re-
enter the queque.
(d) Priority. Every customer has a static or dynamic priority, the server selects always the
customers with the highest priority. This scheme can use preemption or not.
APPLICATION
QUENING SITUATION
Arriving Customer

1. Passage of Customers through Shopers Checkout counters

a supermarket checkout

2. Flor of automobile traffic Automobiles Road network

through a road network.

3. Transfer of electronic Electronic messages

messages Transmission lines

Bank patrons Bank tellers

4. Banking transactions

5. Flow of computer programmes Computer programmes Central processing unit

through a computer system

6. Sale of theatre tickets Theatre-goers Ticket booking windows

7. Arrival of trucks to carry fruits

and vegetables from a central Trucks Loading crews and facilities
market

8. Registration of unemployed at
9. employment exchange Registration assistants
Unemployed personnel
10. Occurrences of fires Firemen and equipment
Fires
11. Flow of ships to the Harbour and docking facilities
seashore Ships
Policemen
12. Calls at police control room Service calls

The waiting lines develop because the service to a customer may not be rendered immediately as
the customer reaches the service facility. Thus lack of adequate service facility would cause
waiting lines of customers to be framed. The only way that the service demand can be met with
ease is to increase the service capacity (and raising the efficiency of the existing capacity if
possible) to a higher level. The capacity might be built to such high level as can always meet the
peak demand with no queues. But adding to may be a costly affair and uneconomic after a stage
because then it shall remain idle to varying degrees when there are no or few customers. A
manager, therefore, has to decide on an appropriate level of service which is neither too low nor
too high. Inefficient or poor service would cause excessive waiting which has a cost in terms of
customer frustration, loss of goods will in the long run, direct cost of idle employees etc.

Queuing models with Poisson's input and exponential service

PROBALISTIC MODEL
Where arrival and service rates are unknown and assumed to be random variable

1) Poisson distribution.

A Poisson Distribution is a discrete probability distribution which predicts the number of arrivals
in a given time. The poisson distribution involves the probability of occurrence of an arrival.
Poisson assumption is quite restrictive in some cases. It assumes that arrivals are random and
independent of all other operating conditions. Poisson distribution assumes fixed time interval of
continuous servicing which is never sure in all service.

2) Exponential distribution.
The most common type of distribution used for service times is exponential distribution. It
involves the probability of completion of a service. The queue theory provides a mathematical
frame work to present these dimensions of a queue problem in precise statistical terms and
develop a solution which can, avoiding both the extremes, meet the requirements of customers as
well as service unit. The queue theory then is to minimise the total cost of queue i.e. the cost of
providing service and cost of waiting time both, with the help of suitable mathematical model.
Various constraints are taken into consideration in developing a queue model. There is no
maximisation or minimisation of the objective function. Various alternatives are considered and
evaluated through the queue model and a final choice of appropriate alternative and appropriate
model is made.
 NETWORK MODELS: PERT & CPM
PERT and CPM are the two network-based project management techniques, which exhibit the
flow and sequence of the activities and events. Program (Project) Management and Review
Technique (PERT) is appropriate for the projects where the time needed to complete different
activities are not known.

On the other hand, the Critical Path Method or CPM is apt for the projects which are recurring
in nature.

The two scheduling methods use a common approach for designing the network and for
ascertaining its critical path. They are used in the successful completion of a project and hence
used in conjunction with each other. Nevertheless, the truth is that CPM is different from PERT
in a way that the latter concentrates on time while the former stresses on the time-cost trade-off.
In the same manner, there are many differences between PERT and CPM

Definition of PERT

PERT is an acronym for Program (Project) Evaluation and Review Technique, in which
planning, scheduling, organizing, coordinating and controlling uncertain activities take place.
The technique studies and represents the tasks undertaken to complete a project, to identify the
least time for completing a task and the minimum time required to complete the whole project. It
was developed in the late 1950s. It is aimed to reduce the time and cost of the project.

PERT uses time as a variable which represents the planned resource application along with
performance specification. In this technique, first of all, the project is divided into activities and
events. After that proper sequence is ascertained, and a network is constructed. After that time
needed in each activity is calculated and the critical path (longest path connecting all the events)
is determined.

Definition of CPM

Developed in the late 1950s, Critical Path Method or CPM is an algorithm used for planning,
scheduling, coordination and control of activities in a project. Here, it is assumed that the activity
duration is fixed and certain. CPM is used to compute the earliest and latest possible start time
for each activity.

The process differentiates the critical and non-critical activities to reduce the time and avoid the
queue generation in the process. The reason for the identification of critical activities is that, if
any activity is delayed, it will cause the whole process to suffer. That is why it is named as
Critical Path Method.

BASIS FOR
PERT CPM
COMPARISON

Meaning PERT is a project CPM is a statistical

management technique, technique of project
used to manage uncertain management that manages
activities of a project. well defined activities of a
project.

What is it? A technique of planning A method to control cost

and control of time. and time.

Orientation Event-oriented Activity-oriented

Evolution Evolved as Research & Evolved as Construction

Development project project

Model Probabilistic Model Deterministic Model

Focuses on Time Time-cost trade-off

Estimates Three time estimates One time estimate

Appropriate for High precision time Reasonable time estimate

estimate

Management of Unpredictable Activities Predictable activities

Nature of jobs Non-repetitive nature Repetitive nature

Critical and Non- No differentiation Differentiated

critical activities

Suitable for Research and Non-research projects like

Development Project civil construction, ship
building etc.

Crashing concept Not Applicable Applicable

APPLICATIONS OF NETWORK MODELS

In addition to PERT and CPM, there are several other network models. For example the
Minimal-Spanning Tree Technique. This technique determines the path through the network that
connects all the points while minimizing total distance. This technique is widely used to connect
all the houses to electrical power, water system in such a way that minimizes the total distance or
length of power lines or water pipes.

Another technique is 'Maximal Flow Technique'. This technique finds the maximum Bow of any
quantity or substance through a network. This technique can determine the maximum number of
vehicles that can go through a network of roads from one location to another. Finally the
Shortest-Route Technique can be used to determine the shortest route from one city to another
through a network of roads.

These models were successfully applied by the U.S. chemical firm of Dupont in the construction
and maintenance of chemical plant. Another American Company Perini Pacific always used the
network analysis for bidding. In so many cases the company was awarded the contract for a high
bid, because of the vast knowledge in the field.
Central Electricity Generating Board of U.K. used the network analysis successfully to plan and
control the maintenance of kead by power station. This resulted in 40%, reduction in time
required for the procedure. PERT was also used by the U.S. navy to control the construction and
implementation of the Polarisis missile system.

The other applications of the above models are as under:

1. Planning, scheduling, monitoring and control of large and complex projects

2. Construction of factories, highways, building, bridges, cinemas etc.
3. Helpful to Army for its Missile development.
4. Assembly line scheduling.
5. Installation of computers and high tech machineries.
6. Developing advertising programmes.
7. Development and launching of new products.
8. Helpful to management for its research and development projects.
9. To make marketing strategies
10. Helpful to find traffic flow patterns in big cities.
11. Preparing inventory plans.
12. Maintenance of big and heavy equipments in chemical, cement, steel plant
13. Assembly line scheduling etc.

OBJECTIVES OF NETWORK ANALYSIS

Almost any large project can be subdivided into series of smaller activities that can be analysed
with PERT

The following are the main objectives of the network.

1. Helpful in planning. Network analysis is powerful tool for planning, scheduling and
controlling.

2. Inter-relationship of various activities. Network analysis creates inter relationship and inter-
dependence of various activities of project or a programme. This relationship helps in bringing
out the technological interdependencies of the various activities. At the same time it helps in
integrating the project planning.

3. Cost control. In certain cases we can measure cost of delay in the completion of the project.
This cost can be compared to the cost of the resources required to carry out the various activities
at various speeds. Their total cost can be calculated and minimized.
4. Minimization of maintenance time. Network analysis helps the management to minimise the
total maintenance time. If the cost of production overhead is very then it may be economically
justifiable to minimize the maintenance time, regardless of high resource costs.

5. Reduction of time. Sometime we have to arrange existing resources with a view to reducing
the total time for the project, rather than reducing cost.

6. Control on idle resources. Net work analysis also helps to control the idle resources. we
should not allow large fluctuations in the use of limited resources. We should adhere to our
scheduled cost and time. For example if we need 30 plumbers for 1st and last week of 10 weeks
project, but only 10 plumbers will be required for the rest of the intervening period, then cost of
having men idle would have to be compared with the cost of hiring men on temporary basis.

7. Avoiding delays, interruptions. Network analysis develops discipline and systematic

approach in planning scheduling etc. This is not the case in traditional methods. Network
techniques help the managers to avoid delays, interruptions in production and control large and
complex projects.

CONSTRUCTION OF NET WORKS

RULES TO FRAME A NETWORK

1. In network diagram arrows( ) represents activities and circles the events. The length of
an arrow is of no significance.
2. Each activity must start and end in a node. The tail of an activity represents the start and head
the completion of work.
3. The event no. 1 denotes the start of project and is called initial node or event. All activities
emerging from event (1) should not be preceded by any other activity Event carrying the highest
number denotes the completion event.
4. Events should be numbered in an ascending order so that for each activity (i,j) (i is less than j).
5. Only one activity can span across a pair of events.
(a) An event number should not be repeated or duplicated.
(b) Two activities should not be identified by the same completion events.
(C) Activities must be represented either by their symbol or by the corresponding order of
starting and completion events.
6. No dangling is allowed unless especially desired in the question.
7. The logical sequence between activities must follow the following rules.
(a) An event can't occur until all the incoming activities into it have been completed.
(b) Though a dummy activity does not consume either resources or time even then it has to
follow the rules stated above.

IDENTIFICATION OF CRITICAL PATH

What Is Critical Path?

 Critical path is the longest sequence of activities in a project plan which must be
completed on time for the project to complete on its due date.
 Most projects are broken down into tasks, or activities (whatever you want to call the
smaller bits that need to be completed in order to get the project done). The critical path
is the series of those tasks that, when followed in sequential order and accounting for all
the above variables, will take the longest to complete the project.
 Simply put, critical path calculates the SHORTEST project duration possible by lining up
the LONGEST sequence of dependent tasks necessary to complete the project.
IMPORTANCE:

Critical Path is called “critical” because it’s the “red alert” of paths. If your project doesn’t
follow the sequence and timing of the critical path, it won’t be finished before the deadline
successfully

Steps to identify critical path:

STEP 1. Divide the Project into Tasks

 Make a list of your tasks

 Assign each task with a name or a shortcode

STEP 2. Order and Identify Dependencies

 Put your tasks in a logical line-up

 Identify dependencies

STEP 3. Create the Network Diagram

Now, you can make your task line-up visual. The good old pen-and-paper method may work
well; a more sophisticated way of doing this is by using a network diagram such as a PERT and
connecting your tasks in the chart.

STEP 4. Estimate Duration

 Clearly define the beginning and end date for each task.

 Taking into account order and dependencies, set each task’s estimated duration.

STEP 5. Perform Resource Leveling

The main aim of resource leveling is to allocate resources efficiently so that the completion of a
project lies within the given time, and no resource conflicts take place. Resource conflicts may
lead to:
  Delays in the completion of specific tasks.

 Difficulties in assigning resources.

 Inability to change task dependencies.

 Removing tasks as needed.

 Adding more tasks as needed.

 Overall delays and budget overruns of projects.

STEP 6. Determine the Critical Path

Find the longest sequence of project tasks in the diagram. This sequence is the critical path for
your project!
SLACK AND FLOAT

The terms slack and float describe the length of time that an activity can be delayed without
delaying the finish date of a subsequent activity, or the finish date of the entire project. The
terms are most commonly applied to a network analysis technique, known as the Critical Path
Method, which was developed by the DuPont Corporation in 1957.

Slack Versus Float

The terms "slack" and "float" are often used interchangeably. However, the main difference
between float and slack is that slack is typically associated with inactivity, while float is
associated with activity. Slack time allows an activity to start later than originally planned,
while float time allows an activity to take longer than originally planned.

There are two types of float:

a) Total Float

Total float is measured as the difference between the early and late start dates (LS - ES) or the
early and late finish dates (LF – EF). Total float is shared between the activities in a sequence. A
sequence is defined as the activities between a point of path divergence and path convergence.
Total float represents the amount of time an activity can be delayed without delaying the overall
project duration and is also called “float” or “slack”.

b) Free Float

Free float is measured by subtracting the early finish (EF) of the activity from the early start (ES)
of the successor activity.

Free float represents the amount of time that a schedule activity can be delayed without delaying
the early start date of any immediate successor activity within the network path.

Free float is only calculated on the last activity in an activity sequence.

Example

If activity 1.4 has a duration of 6 days and is occurring concurrently with activity 1.5 which has a
duration of 9 days, activity 1.4 has 3 days of total float. Meaning, it can be delayed up to three
days without any effect on the project.

However, if activity 1.4 is delayed by 5 days, there is now a negative float situation: -2 days.
This reflects the fact that the project will now take two days longer than anticipated.