Author: indiafreenotes

Queuing theory is the study of queues and the random processes that characterize them. It deals with making mathematical sense of real-life scenarios. For example, a mob of people queuing up at a bank or the tasks queuing up on your computer’s back end.

In queuing theory we often want to find out how long wait times or queue lengths are, and we can use models to do this. These models are typically important in business and software applications, and queueing theory is often considered a part of operations research.

About Queuing

Any queuing activity can be summarized as entities (customers in your supermarket queue, or jobs in a computer queue) trying to get through an activity (waiting to be served). Queues happen when we can’t all access the activity at the same time: when it is not economically efficient to have enough checkout lines for everyone to go right through as soon as they were ready, or there isn’t enough server space to do an unlimited amount of computer tasks at one moment.

In queueing theory a queue does not refer simply to a neat row which is always first come, first served. This is one example of a queue, but not the only kind. A mob trying to rush for the door on Black Friday is considered a queue as well, as is a group of job applicants waiting for interviews who are picked randomly, one by one, to be interviewed.

Types of Queues and Types of Service

First In First Out, or First Come First Served, is fairly common in banking and commerce. It is the type of queue you get when you have people politely lined up, waiting for their turn.

Last In First Out is the opposite scheme; whoever has been waiting for the shortest time is served first. This type of queue management is common in asset management, where assets produced or acquired last are the ones used or disposed of first. For example: the most recent employees are often the ones laid off first.

Priority is where customers are served based on their priority level; these levels could be based on status, task urgency, or some other criteria.

Shortest Job First is when whoever needs the shortest amount of service gets taken care of first

Processor Sharing is when everyone gets served, or half-served, at the same time; service capacity is distributed evenly among everyone waiting.

There may be a single server, where a line of people or items must go through a single bottleneck, or parallel servers, where the same line is served by several servers.  Or there may be a tandem queue, where each of multiple servers has their own queue or line.

Balking when a customer decides not to wait for service because the wait time threatens to be too long. Renegingis similar, but when a customer who has waited already decides to leave because they’ve wasted too much time. Jockeying is when a customer switches between queues in a tandem queue system, trying to orchestrate the shortest wait possible.

Standard Notation for Queueing Theory

To make life easier, there’s standard notation for queueing theory that is used across the board. These standard symbols include

λ: the mean arrival rate.

μ: the mean service rate.

n: the number of people in the system.

A: the arrival process probability distribution.

B: the service process probability distribution.

C: the number of servers.

D: the maximum number of customers allowed in the system at any given time, waiting or being served (without getting bumped).

E: the maximum number of customers total.

Queuing System Components

Input Source: The input source generates customers for the service mechanism. The most important characteristic of the input source is its size. It may be either finite or infinite. Please note that the calculations are far easier for the infinite case, therefore, this assumption is often made even when the actual size is relatively large.

If the population size is finite, then the analysis of queuing model becomes more involved. The statistical pattern by which calling units are generated over time must also be specified. It may be Poisson or Exponential probability distribution.

2. Queue: It is characterized by the maximum permissible number of units that it can contain. Queues may be infinite or finite.
3. Service Discipline:It refers to the order in which members of the queue are selected for service. Frequently, the discipline is first come, first served.

Following are some other disciplines:

• LIFO (Last In First Out)
• SIRO (Service In Random Order)
• Priority System

Service Mechanism:

A specification of the service mechanism includes a description of time to complete a service and the number of customers who are satisfied at each service event. The service mechanism also prescribes the number and configuration of servers. If there is more than one service facility, the calling unit may receive service from a sequence of these. At a given facility, the unit enters one of the parallel service channels and is completely serviced by that server. Most elementary models assume one service facility with either one or a finite number of servers.The following figure shows the physical layout of service facilities.

Unusual Customer/Server Behaviour

Customer’s Behaviour

• A customer may not like to join the queue due to long waiting line.
• A customer may leave the queue after waiting for sometime due to impatience.

Collusion. Several customers may cooperate and only one of them may stand in the queue.

Jockeying. When there are a number of queues, a customer may move from one queue to another in hope of receiving the service quickly.

Server’s Behaviour

Failure. The service may be interrupted due to failure of a server (machinery).

Changing service rates. A server may speed up or slow down, depending on the number of customers in the queue. For example, when the queue is long, a server may speed up in response to the pressure. On the contrary, it may slow down if the queue is very small.

Batch processing. A server may service several customers simultaneously, a phenomenon known as batch processing.

Assumptions of Queuing Theory

• The source population has infinite size.
• The inter-arrival time has an exponential probability distribution with a mean arrival rate of l customer arrivals per unit time.
• There is no unusual customer behaviour.
• The service discipline is FIFO.
• The service time has an exponential probability distribution with a mean service rate of m service completions per unit time.
• The mean arrival rate is less than the mean service rate, i.e., l < m.
• There is no unusual server behaviour.

Queues happen when resources are limited. In fact, queues make economic sense; no queues would equate to costly overcapacity. Queuing theory helps in the design of balanced systems that serve customers quickly and efficiently but do not cost too much to be sustainable. All queuing systems are broken down into the entities queuing for an activity.

At its most elementary level, queuing theory involves the analysis of arrivals at a facility, such as a bank or fast food restaurant, then the service requirements of that facility, e.g., tellers or attendants.

The origin of queuing theory can be traced back to the early 1900s, found in a study of the Copenhagen telephone exchange by Agner Krarup Erlang, a Danish engineer, statistician and, mathematician. His work led to the Erlang theory of efficient networks and the field of telephone network analysis.

• Queuing theory is the study of congestion and waiting in line.
• The theory can help with creating an efficient and cost-effective workflow, allowing the user to improve traffic flow.
• Queuing theory assesses two key aspects customer arrival at the facility and service requirements.
• Often used as an operations management tool, queuing theory can address staffing, scheduling and customer service shortfalls

The North-West Corner Rule is a method adopted to compute the initial feasible solution of the transportation problem. The name North-west corner is given to this method because the basic variables are selected from the extreme left corner.

The concept of North-West Corner can be well understood through a transportation problem given below:

In the table, three sources A, B and C with the production capacity of 50 units, 40 units, 60 units of product respectively is given. Every day the demand of three retailers D, E, F is to be furnished with at least 20 units, 95 units and 35 units of product respectively. The transportation costs are also given in the matrix.

The prerequisite condition for solving the transportation problem is that demand should be equal to the supply. In case the demand is more than supply, then dummy origin is added to the table. The supply of dummy origin will be equal to the difference between the total supply and total demand. The cost associated with the dummy origin will be zero.

Similarly, in case the supply is more than the demand, then dummy source is created whose demand will be equivalent to the difference between supply and demand. Again the cost associated with the dummy source will be zero.

Once the demand and supply are equal, the following procedure is followed:

1. Select the north-west or extreme left corner of the matrix, assign as many units as possible to cell AD, within the supply and demand constraints. Such as 20 units are assigned to the first cell, that satisfies the demand of destination D while the supply is in surplus.
2. Now move horizontally and assign 30 units to the cell AE. Since 30 units are available with the source A, the supply gets fully saturated.
3. Now move vertically in the matrix and assign 40 units to Cell BE. The supply of source B also gets fully saturated.
4. Again move vertically, and assign 25 units to cell CE, the demand of destination E is fulfilled.
5. Move horizontally in the matrix and assign 35 units to cell CF, both the demand and supply of origin and destination gets saturated. Now the total cost can be computed.

The Total cost can be computed by multiplying the units assigned to each cell with the concerned transportation cost. Therefore,

Total Cost = 20*5+ 30*8+ 40*6+ 25*9+ 35*6 = Rs 1015

General Structure of Transportation Problem

The Transportation Method of linear programming is applied to the problems related to the study of the efficient transportation routes i.e. how efficiently the product from different sources of production is transported to the different destinations, such as the total transportation cost is minimum.

Here origin means the place where the product is originated or manufactured for the ultimate sales while the places where the product is required to be sold is called destination. For solving the transportation problem, the following steps are to be systematically followed:

1. Obtaining the initial feasible solution, which means identifying the solution that satisfies the requirements of demand and supply. There are several methods through which the initial feasible solution can be obtained; these are:

• North-West Corner
• Least Cost Method
• Vogel’s Approximation Method

Note: It is to be ensured that the number of cells occupied should be equal to m+n-1, where “m” is the number of rows while “n” is the number of columns.

2. Testing the optimality of the initial feasible solution. Once the feasible solution is obtained, the next step is to check whether it is optimum or not. There are two methods used for testing the optimality:

• Stepping-stone Method
• Modified Distribution Method (MODI)

The final step is to revise the solution until the optimum solution is obtained.

The two most common objectives of transportation problem could be:

i)maximize the profit of transporting “n” units of product to the destination “y”

ii) Minimize the cost of shipping “n” units of product to the destination “y”.

The Vogel’s Approximation Method or VAM is an iterative procedure calculated to find out the initial feasible solution of the transportation problem. Like Least cost Method, here also the shipping cost is taken into consideration, but in a relative sense.

The following is the flow chart showing the steps involved in solving the transportation problem using the Vogel’s Approximation Method:

The concept of Vogel’s Approximation Method can be well understood through an illustration given below:

1. First of all the difference between two least cost cells are calculated for each row and column, which can be seen in the iteration given for each row and column. Then the largest difference is selected, which is 4 in this case. So, allocate 20 units to cell BD, since the minimum cost is to be chosen for the allocation. Now, only 20 units are left with the source B.
2. Column D is deleted, again the difference betweenthe least cost cells is calculated for each row and column, as seen in the iteration below. The largest difference value comes to be 3, so allocate 35 units to cell AF and 15 units to the cell AE. With this, the Supply and demand of source A and origin F gets saturated, so delete both the row A and Column F.
3. Now, single column E is left, since no difference can be found out, so allocate 60 units to the cell CE and 20 units to cell BE, as only 20 units are left with source B. Hence the demand and supply are completely met.

Now the total cost can be computed, by multiplying the units assigned to each cell with the cost concerned. Therefore,

Total Cost = 20*3 + 35*1 + 15*4 + 60*4 + 20*8 = Rs 555

Note: Vogel’s Approximation Method is also called as Penalty Method because the difference costs chosen are nothing but the penalties of not choosing the least cost routes.

If the basic feasible solution of a transportation problem with m origins and n destinations has fewer than m + n – 1 positive xij (occupied cells), the problem is said to be a degenerate transportation problem. Degeneracy can occur at two stages:

1. At the initial solution
2. During the testing of the optimal solution

If modified distribution method (MODI) is applied to test for optimality, it will not be possible to find all the variables ui and vj since the number of allocated cells and their corresponding cij values is not enough.

Consider the following example:

The initial basic feasible solution (by north-west rule) is:

No. of factories (origins) m = 3, no. of dealers (destinations) n = 4

So m + n – 1 = 3 + 4 – 1 = 6. But no. of allocations = 5.

So the solution is degenerate.

The Modified Distribution Method or MODI is an efficient method of checking the optimality of the initial feasible solution.

The concept of MODI can be further comprehended through an illustration given below:

1. Initial basic feasible solution is given below

2. Now, calculate the values of ui and vj by using the equation
ui+vj = Cij
Substituting the value of u1 as 0
U1+V1 = C11, 0+V1 = 6 or V1 = 6
U1 +V2 = C12, 0+V2 = 4 or V2 = 4
U2+V2 = C22, U2+4 = 8 or U2 = 4
U3+ V2 = C32, U3+4 = 4 or U3 = 0
U3+V3 = C33, 0+V3 = 2 or V3 =2

3. Next step is to calculate the opportunity cost of the unoccupied cells (AF, BD, BF, CD) by using the following formula

Cij – (ui+Vi)
AF = C13 – (U1+V3),  1- (0+2) = -1 or 1
BD = C21 – (U2+v1),   3- (4+6) = -7 or 7
BF = C23 – (U2+V3),   7- (4+2) = 1 or -1
CD = C31- (U3+V1),    4- (0+6) = -2 or 2

4. Choose the largest positive opportunity cost, which is 7 and draw a closed path, as shown in the matrix below. Start from the unoccupied cell and assign “+” or “–“sign alternatively. Therefore, The most favored cell is BD, assign as many units as possible.

5. The matrix below shows the maximum allocation to the cell BD, and that number of units are added to the cell with a positive sign and subtracted from the cell with a negative sign.

6. Again, repeat the steps from 1 to 4 i.e. find out the opportunity costs for each unoccupied cell and assign the maximum possible units to the cell having the largest opportunity cost. This process will go on until the optimum solution is reached.

The Modified distribution method is an improvement over the stepping stone method since; it can be applied more efficiently when a large number of sources and destinations are involved, which becomes quite difficult or tedious in case of stepping stone method.

Modified distribution method reduces the number of steps involved in the evaluation of empty cells, thereby minimizes the complexity and gives a straightforward computational scheme through which the opportunity cost of each empty cell can be determined.

Assignment Problem is a special type of linear programming problem which deals with the allocation of the various resources to the various activities on one to one basis. It does it in such a way that the cost or time involved in the process is minimum and profit or sale is maximum. Though there problems can be solved by simplex method or by transportation method but assignment model gives a simpler approach for these problems.

In a factory, a supervisor may have six workers available and six jobs to fire. He will have to take decision regarding which job should be given to which worker. Problem forms one to one basis. This is an assignment problem.

Assignment Model:

Suppose there are n facilitates and n jobs it is clear that in this case, there will be n assignments. Each facility or say worker can perform each job, one at a time. But there should be certain procedure by which assignment should be made so that the profit is maximized or the cost or time is minimized.

In the table, Co_ij is defined as the cost when j^th job is assigned to i^th worker. It maybe noted here that this is a special case of transportation problem when the number of rows is equal to number of columns.

Mathematical Formulation:

Any basic feasible solution of an Assignment problem consists (2n – 1) variables of which the (n – 1) variables are zero, n is number of jobs or number of facilities. Due to this high degeneracy, if we solve the problem by usual transportation method, it will be a complex and time consuming work. Thus a separate technique is derived for it. Before going to the absolute method it is very important to formulate the problem.

Suppose x_jj is a variable which is defined as

1 if the i^th job is assigned to j^th machine or facility

0 if the i^th job is not assigned to j^th machine or facility.

Now as the problem forms one to one basis or one job is to be assigned to one facility or machine.

The total assignment cost will be given by

The above definition can be developed into mathematical model as follows:

Determine x_ij > 0 (i, j = 1,2, 3…n) in order to

Subjected to constraints

and x_ij is either zero or one.

Method to solve Problem (Hungarian Technique):

Consider the objective function of minimization type. Following steps are involved in solving this Assignment problem,

1. Locate the smallest cost element in each row of the given cost table starting with the first row. Now, this smallest element is subtracted form each element of that row. So, we will be getting at least one zero in each row of this new table.
2. Having constructed the table (as by step-1) take the columns of the table. Starting from first column locate the smallest cost element in each column. Now subtract this smallest element from each element of that column. Having performed the step 1 and step 2, we will be getting at least one zero in each column in the reduced cost table.
3. Now, the assignments are made for the reduced table in following manner.

(i) Rows are examined successively, until the row with exactly single (one) zero is found. Assignment is made to this single zero by putting square □ around it and in the corresponding column, all other zeros are crossed out (x) because these will not be used to make any other assignment in this column. Step is conducted for each row.

(ii) Step 3 (i) in now performed on the columns as follow:- columns are examined successively till a column with exactly one zero is found. Now , assignment is made to this single zero by putting the square around it and at the same time, all other zeros in the corresponding rows are crossed out (x) step is conducted for each column.

(iii) Step 3, (i) and 3 (ii) are repeated till all the zeros are either marked or crossed out. Now, if the number of marked zeros or the assignments made are equal to number of rows or columns, optimum solution has been achieved. There will be exactly single assignment in each or columns without any assignment. In this case, we will go to step 4.

4. At this stage, draw the minimum number of lines (horizontal and vertical) necessary to cover all zeros in the matrix obtained in step 3, Following procedure is adopted:

(i) Tick mark () all rows that do not have any assignment.

(ii) Now tick mark() all these columns that have zero in the tick marked rows.

(iii) Now tick mark all the rows that are not already marked and that have assignment in the marked columns.

(iv) All the steps i.e. (4(i), 4(ii), 4(iii) are repeated until no more rows or columns can be marked.

(v) Now draw straight lines which pass through all the un marked rows and marked columns. It can also be noticed that in an n x n matrix, always less than ‘n’ lines will cover all the zeros if there is no solution among them.

5. In step 4, if the number of lines drawn are equal to n or the number of rows, then it is the optimum solution if not, then go to step 6.
6. Select the smallest element among all the uncovered elements. Now, this element is subtracted from all the uncovered elements and added to the element which lies at the intersection of two lines. This is the matrix for fresh assignments.
7. Repeat the procedure from step (3) until the number of assignments becomes equal to the number of rows or number of columns.

There are problems where certain facilities have to be assigned to a number of jobs so as to maximize the overall performance of the assignment. The problem can be converted into a minimization problem in the following ways and then Hungarian method can be used for its solution.

1. Change the signs of all values given in the table.
2. Select the highest element in the entire assignment table and subtract all the elements of the table from the highest element.

Example: A marketing manager has five salesmen and sales districts. Considering the capabilities of the salesmen and the nature of districts, the marketing manager estimates that sales per month (in hundred rupees) for each salesman in each district would be as follows. Find the assignment of salesmen to districts that will result in maximum sales.

Maximization Problem

Maximization assignment problem is transformed into minimization problem by

Solution: The given maximization problem is converted into minimization problem by subtracting from the highest sales value (i.e., 41) with all elements of the given table.

Conversion to Minimization Problem

Reduce the matrix row-wise

Matrix Reduced Row-wise

Reduce the matrix column-wise and draw minimum number of lines to cover all the zeros in the matrix, as shown in Table.

Matrix Reduced Column-wise and Zeros Covered

Number of lines drawn ≠ Order of matrix. Hence not optimal.

Select the least uncovered element, i.e., 4 and subtract it from other uncovered elements, add it to the elements at intersection of line and leave the elements that are covered with single line unchanged, Table.

Added & Subtracted the least Uncovered Element

Now, number of lines drawn = Order of matrix, hence optimality is reached. There are two alternative assignments due to presence of zero elements in cells (4, C), (4, D), (5, C) and (5, D).

Two Alternative Assignments

Therefore,

Whenever the cost matrix of an assignment problem is not a square matrix, that is, whenever the number of sources is not equal to the number of destinations, the assignment problem is called an unbalanced assignment problem. In such problems, dummy rows (or columns) are added in the matrix so as to complete it to form a square matrix. The dummy rows or columns will contain all costs elements as zeroes. The Hungarian method may be used to solve the problem.

Example: A company has five machines that are used for four jobs. Each job can be assigned to one and only one machine. The cost of each job on each machine is given in the following Table.

Unbalanced Maximization Assignment problem example

Assignment Problem

Solution: Convert the 4 × 5 matrix into a square matrix by adding a dummy row D5.

Dummy Row D5 Added

Row-wise Reduction of the Matrix

Column-wise reduction is not necessary since all columns contain a single zero. Now, draw minimum number of lines to cover all the zeros, as shown in Table.

All Zeros in the Matrix Covered

Number of lines drawn ≠ Order of matrix. Hence not optimal.

Select the least uncovered element, i.e., 1, subtract it from other uncovered elements, add to the elements at intersection of lines and leave the elements that are covered with single line unchanged as shown in Table.

Subtracted or Added to Elements

Number of lines drawn ≠ Order of matrix. Hence not optimal.

Again Added or Subtracted 1 from Elements

Number of lines drawn = Order of matrix. Hence optimality is reached. Now assign the jobs to machines, as shown in Table.

Assigning Jobs to Machines

Example : In a plant layout, four different machines M1, M2, M3 and M4 are to be erected in a machine shop. There are five vacant areas A, B, C, D and E. Because of limited space, Machine M2 cannot be erected at area C and Machine M4 cannot be erected at area A. The cost of erection of machines is given in the Table.

Assignment Problem

Find the optimal assignment plan.

Solution: As the given matrix is not balanced, add a dummy row D5 with zero cost values. Assign a high cost H for (M2, C) and (M4, A). While selecting the lowest cost element neglect the high cost assigned H, as shown in Table below.

Dummy Row D5 Added

Row-wise reduction of the matrix is shown in Table.

Matrix Reduced Row-wise

Note: Column-wise reduction is not necessary, as each column has at least one single zero. Now, draw minimum number of lines to cover all the zeros, see Table.

Lines Drawn to Cover all Zeros

Number of lines drawn ≠ Order of matrix. Hence not Optimal. Select the smallest uncovered element, in this case 1. Subtract 1 from all other uncovered element and add 1 with the elements at the intersection. The element covered by single line remains unchanged. These changes are shown in Table. Now try to draw minimum number of lines to cover all the zeros.

Added or Subtracted 1 from Elements

Now number of lines drawn = Order of matrix, hence optimality is reached. Optimal assignment of machines to areas are shown in Table.

Optimal Assignment

Hence, the optimal solution is:

Network technique is a technique for planning, scheduling (programming) and controlling the progress of projects. This is very useful for projects which are complex in nature or where activities are subject to considerable degree of uncertainty in performance time.

This technique provides an effective management, determines the project duration more accurately, identifies the activities which are critical at different stages of project completion to enable to pay more attention on these activities, analyse the scheduling at regular interval for taking corrective action well in advance, facilitates in optimistic resources utilisation, helps management for taking timely and better decisions for effective monitoring and control during execution of the project.

Objectives of Network Analysis:

Network analysis entails a group of techniques for presenting information relating to time and resources so as to assist in the planning, scheduling, and controlling of projects. The infor­mation, usually represented by a network, includes the sequences, interdependencies, interre­lationships, and criticality of various activities of the project.

A network analysis has following objectives:

1. Powerful tool of planning, scheduling and control.
2. Shows the inter-relationships of the activities of a project or a programme.
3. Minimises total cost where the cost of delays and cost of resources required to carry out the tasks can be measured.
4. Minimise total time where required e.g. in maintenance of production-line machinery in a factory.
5. Minimization of idle resources.
6. Minimise production delays.
7. To provide systematic approach in planning and scheduling.
8. Follow an integrated approach and bring about better coordination between the de­partments.
9. Focusses attention on critical activities of the project.

• Provides up-to-date status information.
• Suggest areas for increasing efficiency, and reduction of cost.

Applications of Network Technique:

(i) Planning,

(ii) Construction of buildings, bridges, highways, railways, stadiums, irrigation projects, factories, power projects etc.

(iii) Assembly line scheduling,

(iv) Development and launching of new products,

(v) Strategic and tactical military planning,

(vi) Research and development,

(vii) Market penetration programmes,

(viii) Planning of political campaigns,

(ix) Maintenance and overhauling of complicated or large machineries,

(x) organising big conferences etc.

Advantages of Network Technique:

1. Detailed and thoughtful planning provides better analysis and logical thinking.
2. Identifies the critical activities and focus them to provide greater managerial atten­tion.
3. Network technique enables to forecast project duration more accurately.
4. It is a powerful tool for optimisation of resources by using the concept of slack.
5. It provides a scientific basis for monitoring, review and control, to evaluate effect of slippages.
6. It helps in taking decision;

(i) To over-come delays,

(ii) To crashing programme,

(iii) Optimising resources, and

(iv) On other corrective actions.

7. It helps in getting better co-ordination amongst related fields.
8. It is an effective management tool through a common and simple language, providing common understanding.

Limitations of Network Techniques:

(i) Network technique is simply a tool to help the management; hence its effectiveness depends on how well it is used by the management.

(ii) Its accuracy depends on the estimation of the data used in the network.

(iii) It is useful only if it is updated regularly and decisions for corrective actions are taken timely.