INDEX:

UNIT-I

• Introduction to Operations Research: Basics definition, scope, objectives, phases, models and limitations of Operations Research.
• Linear Programming Problem – Formulation of LPP, Graphical solution of LPP.
• Simplex Method, Artificial variables, Big-M method, two-phase method, degeneracy and unbound solutions.

UNIT-II

• Transportation Problem: Formulation, solution, unbalanced Transportation problem. Finding basic feasible solutions – Northwest corner rule, least cost method and Vogel’s approximation method. Optimality test: the stepping stone method and MODI method.
• Assignment Model: Formulation, Hungarian method for optimal solution, Solving unbalanced problem, Travelling salesman problem and assignment problem.

UNIT-1

 

Meaning and Definition of Operation Research:

It is the method of analysis by which management receives aid for their decisions. Though the name of this method, Operation Research (O.R.) is relatively new, but the method used for this is not a new one. Operation Research is concerned with the application of the principles and the methods of science to the problems of strategy.

The subject of operation research was born during Second World War in U.K., and was used for military strategy. During World War II, a group of scientists, having representatives from mathematics, statistics, physical and social sciences were entrusted to the study of various military operations. This team was very success­ful and greatly contributed to the meticulous handling of entire operation and related problems of the operation.

The need for assigning such studies for operations arose because military strategies and their decisions become so important and costly and therefore, the best scientists, under the sponsorship of military organs were grouped together to provide quantitative information’s by adopting scientific techniques and methods for facilitating in taking decisions.

After the World War II, it was started applying in the fields of industry, trade, agriculture, planning and various other fields of economy.

The operation research can be defined as:

Definitions:

(i) It is the application of scientific methods, techniques and tools to problems involving the operations of a system so as to provide those in the control of the system with optimum solutions to the problems.

(ii) Operation Research is a tool for taking decisions which searches for the optimum results in parity with the overall objectives and constraints of the organisation.

(iii) O.R. is a scientific method of providing executive department with a quantitative basis of decisions regarding the operations under their control.

(iv) O.R. is a scientific approach to problem solving for management.

(v) O.R. is an aid for executive in making his decisions by providing him with the needed quantitative information’s based on the scientific method of analysis.

(vi) O.R. is the application of modern methods of mathematical science to complex prob­lems involving management of large systems of men, machines, materials, and money in industry, business, government and defence. The distinctive approach is to develop a scientific model of the system incorporating measurement of factors such as chance and risk, to predict and compare the outcome of alternative decisions, strategies or controls.

(vii) It is the application of the scientific methods by scientists and subject specialists to the study of the given operation. Its purpose is to give administration, a basis for predicting quantitatively the most effective results of an operation under given set of variable conditions and thereby to provide a sound basis for “decision-making”.

In fact in Operation Research, research techniques and scientific methods are employed for the analysis and also for studying the current or future problems. Thus, Operation Research offers alternative plans for a problem to the management for decisions.

Although it is very clear that operation research never make decisions for the man­agement, instead the method presents management with a careful scientific and quantitative analysis of problem so that the management will be in a better position to make sounder deci­sions.

It can be used for solving different types of problems, such as:

1. Problems dealing with the waiting line, the arrival of units or persons requiring ser­vice.
2. Problems dealing with the allocation of material or activities among limited facilities.

iii. Equipment replacement problems.

1. Problems dealing with production processing i.e., production control and material ship­ment.

But it may be remembered that operation research never replaces a manager as decision maker. The ultimate and full responsibility for analyzing all factors and making decision will be of the manager.

In the more wide sense, operation research does not deal with the everyday problems such as output by the one worker or machine capacity; instead it is concerned with the overall aspect of business operation such as something as the relationship between inventory, sales, and productions and scheduling. It may also deal with the overall flow of goods and services from plants to consumers.

The team doing operation research may have statisticians, psychologists, labour specialists, mathematicians and others depending upon the requirement for the problems.

Phases in Operation Research Study:

Since, the main objective of operation research is to provide better quantitative information’s for making decision. Now our aim is to learn how we can have better decisions.

The procedure for making decisions with the OR study generally involves the following phases:

(i) Judgment Phase:

1. Determination of operation.
2. Determination of objectives.

iii. Determination of effectiveness of measures.

1. Determination of type of problem, its origin and causes.

(ii) Research Phase:

1. Observation and data collection for better understanding of the problem.
2. Formulation of relevant hypothesis and models.

iii. Analysis of available information and verification of hypothesis.

1. Production and generation of results and consideration of alternatives.

(iii) Action Phase:

1. Recommendations for remedial action to those who first posed the problem, this includes the assumptions made, scope and limitations, alternative courses of ac­tion and their effect.
2. Putting the solution to work: implementation.

Without OR, in many cases, we follow these phases in full, but in other cases, we leave important steps out. Judgment and subjective decision-making are not good enough. Thus industries look to operation research for more objective way to make decisions. It is found that method used should consider the emotional and subjective factors also.

For example, the skill and creative labour are important factors in our business and if management wants to have a new location, the management has to consider the personal feeling of the employees for the location which he chooses.

Scope of Operation Research:

In its recent years of organized development, O.R. has solved successfully many cases of research for military, the government and industry. The basic problem in most of the develop­ing countries in Asia and Africa is to remove poverty and hunger as quickly as possible. So there is a great scope for economist, statisticians, administrators, politicians and technicians working in a team to solve this problem by an O.R. approach.

On the other hand, with the explosion of population and consequent shortage of food, every country is facing the problem of optimum allocation of land for various crops in accordance with climatic conditions and available facilities. The problem of optimal distribution of water from a resource like a canal for irrigation purposes is faced by developing country. Hence a good amount of scientific work can be done in this direction.

In the field of Industrial Engineering, there is a claim of problems, starting from the pro­curement of material to the dispatch of finished products. Management is always interested in optimizing profits.

Hence in order to provide decision on scientific basis, O.R. study team con­siders various alternative methods and their effects on existing system. The O.R. approach is equally useful for the economists, administrators, planners, irrigation or agricultural experts and statisticians etc.

Operation research approach helps in operation management. Operation management can be defined as the management of systems for providing goods or services, and is concerned with the design and operation of systems for the manufacture, transport, supply or service. The operating systems convert the inputs to the satisfaction of customers need.

Thus the operation management is concerned with the optimum utilization of resources i.e. effective utilization of resources with minimum loss, underutilization or waste. In other words, it is concerned with the satisfactory customer service and optimum resource utilization. Inputs for an operating system may be material, machine and human resource.

O.R. study is complete only when we also consider human factors to the alternatives made available. Operation Research is done by a team of scientists or experts from different related disciplines.

For example, for solving a problem related to the inventory management, O.R. team must include an engineer who knows about stores and material management, a cost ac­countant a mathematician-cum-statistician. For large and complicated problems, the team must include a mathematician, a statistician, one or two engineers, an economist, computer program­mer, psychologist etc.

Some of the problems which can be analyzed by operations research are given hereunder:

1. Finance, Budgeting and Investment:
2. Cash flow analysis, long range capital requirement, investment portfolios, divi­dend policies,
3. Claim procedure, and

iii. Credit policies.

2. Marketing:
3. Product selection, competitive actions,
4. Number of salesmen, frequencies of calling on, and

iii. Advertising strategies with respect to cost and time.

3. Purchasing:
4. Buying policies, varying prices,
5. Determination of quantities and timing of purchases,

iii. Bidding policies,

1. Replacement policies, and
2. Exploitation of new material resources.
3. Production Management:
4. Physical distribution: Location and size of warehouses, distribution centers and retail outlets, distribution policies.
5. Facilities Planning: Number and location of factories, warehouses etc. Loading and unloading facilities.

iii. Manufacturing: Production scheduling and sequencing stabilization of produc­tion, employment, layoffs, and optimum product mix.

1. Maintenance policies, crew size.
2. Project scheduling and allocation of resources.
3. Personnel Management:
4. Mixes of age and skills,
5. Recruiting policies, and

iii. Job assignments.

6. Research and Development:
7. Areas of concentration for R&D.
8. Reliability and alternate decisions.

iii. Determination of time-cost trade off and control of development projects.

Characteristics (Features) of Operation Research:

Main characteristics of operations research (O.R.) are follows:

(i) Inter-Disciplinary Team Approach:

This requires an inter-disciplinary team includ­ing individuals with skills in mathematics, statistics, economics, engineering, mate­rial sciences, computer etc.

(ii) Wholistic Approach to the System:

While evaluating any decision, the important interactions and their impact on the whole organization against the functions originally involved are reviewed.

(iii) Methodological Approach:

O.R. utilizes the scientific method to solve the problem

(iv) Objective Approach:

O.R. attempts to find the best or optimal solution to the prob­lem under consideration, taking into account the goals of the organization.

Methodology of Operation Research:

Operation Research, is a scientific approach for decision-making, and therefore must follow following steps:

1. Formulating the Problem:

The problem must be first clearly defined. It is common to start the O.R. study with tentative formulation of the problem, which is reformulated over and again during the study. The study must also consider economic aspects.

While formulating the O.R. study, analysts must analyses following major components:

(i) The environment:

Environment involves physical, social and economic factors which are likely to affect the problem under consideration. O.R. team or analysts must study the organisation contents including men, materials, machines, suppliers, consumers, competitors, the government and the public.

(ii) Decision-makers:

Operation analyst must study the decision-maker and his rela­tionship to the problem at hand.

(iii) Objectives:

Considering the problem as whole, objectives should be defined.

(iv) Alternatives:

The O.R. study determines as to which alternative course of action is most effective to achieve the desired objectives. Expected reactions of the competitors to the alternative must also be considered.

2. Deriving Solution:

Models are used to determine the solution either by simulation or by mathematical analysis. Mathematical analysis for deriving optimum solution includes ana­lytical or numerical procedure, and uses various branches of mathematics.

3. Testing the Model and Solution:

A properly formulated and correctly manipulated model is useful in predicting the effect of changes in control variables on the overall system effectiveness. The validity of the solution is checked by comparing the results with those ob­tained without using the model.

4. Establishing Controls over the Solution:

The solution derived from a model remains effective so long as the uncontrolled variables retain their values and the relationship. The solution goes out of control, if the values of one or more variables vary or relationship between them undergoes a change. In such circumstances the models need to be modified to take the changes into account.

5. Implementing the Solution:

Solution so obtained should be translated into operating procedure to make it easily understandable and applied by the concerned persons. After apply­ing the solution to the system, O.R. group must study the response of the system to the changes made.

Operation Research Models:

Operation Research model is an idealized representation of the real life situation and repre­sents one or more aspects of reality. Examples of operation research models are: a map, activity charts balance sheets, PERT network, break-even equation, economic ordering quantity equation etc. Objective of the model is to provide a means for analyzing the behaviour of the system for improving its performance.

Classification of Models:

Models can be classified on the basis of following factors:

1. By degree of Abstraction:
2. Mathematical models.
3. Language models.
4. By Function:
5. Descriptive models.
6. Predictive models.

iii. Normative models for repetitive problems.

3. By Structure:
4. Physical models.
5. Analogue (graphical) models.

iii. Symbolic or mathematical models.

4. By Nature of Environment:
5. Deterministic models.
6. Probabilistic models.
7. By the Time Horizon:
8. Static models.
9. Dynamic models.

Characteristics of a Good Model:

1. Assumptions should be simple and few.
2. Variables should be as less as possible.

iii. It should be able to assimilate the system environmental changes without change in its framework.

1. It should be easy to construct.

Constructing the Model:

A mathematical model is a set of equations in which the system or problem is described. The equations represent objective func­tion and constraints. Objective function is a mathematical expressions of objectives (cost or profit of the operation), while constraints are mathematical expressions of the limitations on the fulfillment of the objectives.

These expressions consist of controllable and uncontrollable variables.

The general form of a mathematical model is:

O = f (x_i, y_i)

where O = Objective function

x_i = Controllable variables

y_i = Uncontrollable variables

f = Relationship between O, and x_i, y_i.

Since model is only an approximation of the real situation, hence it may not include all the variables.

Simplification in Operation Research Models:

While constructing the model, efforts should be made to simplify them, but only up to the extent so that there is no significant loss of accuracy.

Some of the common simplifications are:

1. Omitting certain variables.
2. Aggregating (or grouping) variables.

iii. Changing the nature of variables e.g., considering variables as constant or continuous.

1. Changing relationship between variables i.e., considering them as linear or straight line.
2. Modify constraints.

Techniques of Operation Research:

Important techniques of Operation Research are being described hereunder:

(i) Inventory Control Models:

Operation Research study involves balancing inventory costs against one or more of the following costs:

1. Shortage costs.
2. Ordering costs.

iii. Storage costs.

1. Interest costs.

This study helps in taking decisions about:

1. How much to purchase.
2. When to order.

iii. Whether to manufacture or to purchase i.e., make and buy decisions.

The most well-known use is in the form of Economic Order Quantity equation for finding economic lot size.

(ii) Waiting Line Models:

These models are used for minimising the waiting time and idle time together with the costs associated therewith.

Waiting line models are of two types:

(a) Queuing theory, which is applicable for determining the number of service facilities and/or the timing of arrivals for servicing.

(b) Sequencing theory which is applicable for determining the sequence of the servicing.

(iii) Replacement Models:

These models are used for determining the time of replacement or maintenance of item, which may either:

(i) Become obsolete, or

(ii) Become inefficient for use, and

(iii) Become beyond economical to repair or maintain.

(iv) Allocation Models:

These models are used to solve the problems arising when:

(a) There are number of activities which are to be performed and there are number of alternative ways of doing them,

(b) The resources or facilities are limited, which do not allow each activity to be performed in best possible way. Thus these models help to combine activities and available resources so as to optimise and get a solution to obtain an overall effectiveness.

(v) Competitive Strategies:

Such type of strategies are adopted where, efficiency of deci­sion of one agency is dependent on the decision of another agency. Examples of such strategies are game of cards or chess, fixing of prices in a competitive market where these strategies are termed as “theory”.

(vi) Linear Programming Technique:

These techniques are used for solving operation problems having many variables subject to certain restrictions. In such problems, objectives are—profit, costs, quantities manufactured etc. whereas restrictions may be e.g. policies of government, capacity of the plant, demand of the product, availability of raw materials, water or power and storage capacity etc.

(vii) Sequencing Models:

These are concerned with the selection of an appropriate sequence of performing a series of jobs to be done on a service facility or machine so as to optimise some efficiency measure of performance of the system.

(viii) Simulation Models:

Simulation is an experimental method used to study behaviour over time.

(ix) Network Models:

This is an approach to planning, scheduling and controlling complex projects.

Applications of Operation Research:

These techniques are applied to a very wide range of problems.

Here only some of the common applications are being mentioned:

(i) Distribution or Transportation Problems:

In such problems, various centres with their demands are given and various warehouses with their stock positions are also known, then by using linear programming technique, we can find out most economical distribution of the products to various centres from various warehouses.

(ii) Product Mix:

These techniques can be applied to determine best mix of the products for a plant with available resources, so as to get maximum profit or minimum cost of produc­tion.

(iii) Production Planning:

These techniques can also be applied to allocate various jobs to different machines so as to get maximum profit or to maximise production or to minimise total production time.

(iv) Assignment of Personnel:

Similarly, this technique can be applied for assignment of different personnel with different aptitude to different jobs so as to complete the task within a minimum time.

(v) Agricultural Production:

We can also apply this technique to maximise cultivator’s profit, involving cultivation of number of items with different returns and cropping time in different type of lands having variable fertility.

(vi) Financial Applications:

Many financial decision making problems can be solved by using linear programming technique.

Some of them are:

(i) To select best portfolio in order to maximize return on investment out of alternative investment opportunities like bonds, stocks etc. Such problems are generally faced by the managers of mutual funds, banks and insurance companies.

(ii) In deciding financial mix strategies, involving the selection of means for financing firm, projects, inventories etc.

Limitations of Operations Research:

1. These do not take into account qualitative and emotional factors.
2. These are applicable to only specific categories of decision-making problems.

iii. These are required to be interpreted correctly.

1. Due to conventional thinking, changes face lot of resistance from workers and some­times even from employer.
2. Models are only idealized representation of reality and not be regarded as absolute.

Graphical Method: Owing to the importance of linear programming models in various industries, many types of algorithms have been developed over the years to solve them. Some famous mentions include the Simplex method, the Hungarian approach, and others. Here we are going to concentrate on one of the most basic methods to handle a linear programming problem i.e. the graphical method. The Graphical Method

We will first discuss the steps of the algorithm:

Step 1: Formulate the LP (Linear programming) problem

We have already understood the mathematical formulation of an LP problem in a previous section. Note that this is the most crucial step as all the subsequent steps depend on our analysis here.

Step 2: Construct a graph and plot the constraint lines

The graph must be constructed in ‘n’ dimensions, where ‘n’ is the number of decision variables. This should give you an idea about the complexity of this step if the number of decision variables increases.

One must know that one cannot imagine more than 3-dimensions anyway! The constraint lines can be constructed by joining the horizontal and vertical intercepts found from each constraint equation.

Step 3: Determine the valid side of each constraint line

This is used to determine the domain of the available space, which can result in a feasible solution. How to check? A simple method is to put the coordinates of the origin (0,0) in the problem and determine whether the objective function takes on a physical solution or not. If yes, then the side of the constraint lines on which the origin lies is the valid side. Otherwise it lies on the opposite one.

Step 4: Identify the feasible solution region

The feasible solution region on the graph is the one which is satisfied by all the constraints. It could be viewed as the intersection of the valid regions of each constraint line as well. Choosing any point in this area would result in a valid solution for our objective function.

Step 5: Plot the objective function on the graph

It will clearly be a straight line since we are dealing with linear equations here. One must be sure to draw it differently from the constraint lines to avoid confusion. Choose the constant value in the equation of the objective function randomly, just to make it clearly distinguishable.

Step 6: Find the optimum point

Optimum Points

An optimum point always lies on one of the corners of the feasible region. How to find it? Place a ruler on the graph sheet, parallel to the objective function. Be sure to keep the orientation of this ruler fixed in space. We only need the direction of the straight line of the objective function. Now begin from the far corner of the graph and tend to slide it towards the origin.

• If the goal is to minimize the objective function, find the point of contact of the ruler with the feasible region, which is the closest to the origin. This is the optimum point for minimizing the function.
• If the goal is to maximize the objective function, find the point of contact of the ruler with the feasible region, which is the farthest from the origin. This is the optimum point for maximizing the function.

Artificial variable:

When the problems related to the mixed constraints are given and the simplex method has to be applied, then the artificial variable is introduced. The artificial variable refers to the kind of variable which is introduced in the linear program model to obtain the initial basic feasible solution. It is utilized for the equality constraints and for the greater than or equal inequality constraints. There is no meaning of the artificial variables in the physical sense.

The variable refers to the number, characteristics, or quantity which can be counted or measured. A variable also is known as a data item. Some kinds of the variable are control variable, discrete variable, random variables, continuous variable, observed variable, moderating variable, dummy variables, binary variable and scale variable.

In the equation which has the surplus variable, the artificial variable is introduced. In order to ensure that only the basic feasible solution needs to be considered, the nonnegative constraint is satisfied by the artificial variable.

ARTIFICIAL  VARIABLE TECHNIQUES

You may recall that while introducing the slack and surplus variables, we had assigned a zero cost to them in the objective function. Moreover, the slack variables readily provided the initial basic feasible solution. There are, however, many linear programming problems where slack variables cannot provide such a solution. To solve such linear programming problems, there are two (closely related) methods, viz.,

Use penalty (or Big  ‘M’) method to

       Minimize  z  = 4x_i + 3x₂

      subject to the constraints :

2x₁+ x₂  ≥ 10,   -3x₁, +  2x₂  ≤ 6

x₁ + x₂ ≥ 6,   x₁ ≥ 0 and x₂  ≥ 0.

Solution. Introducing surplus (negative slack) variables x₃  ≥ 0,  x₅  ≥ 0 and slack variable x₄  ≥ 0 in the constraint inequations, the problem becomes

Maximize  z*  =  – 4x₁ – 3x₂ + 0.x₃ + 0.x₄ + 0.x₅

subject to the constraints :

2x₁ + x₂ – x₃ = 10,  – 3x₁ + 2x₂ + x₄ =  6

x_l + x₂ – x₅ =  6,  x_j ≥ 0 Q(j = 1,2, 3, 4, 5)

Clearly, we do not have a ready basic feasible solution. The surplus variables carry negative coefficients (-1). We introduce two new variables A₁ ≥ 0 and A₂ ≥ 0 in the first and third equations respectively. These extraneous variables, commonly termed as artificial variables, play the same role as that of slack variables in providing a starting basic feasible solution.

We assign a very high penalty cost (say –M, M ≥ 0) to these variables in the objective function so that they may be driven to zero while reaching optimality.

Now the following initial basic feasible solution is available :

A_l = 10, x₄ = 6   and A₂ =  6

with B = (a₆ , a₄, a₇) as the basis matrix. The cost matrix corresponding to basic feasible solution is c_B = ( –M, 0, -M )

Now, corresponding to the basic variables A₁, x₄ and A₂. the matrix Y = B^-1A and the net evaluations z_j – c_j (j = 1, 2, …. 7) are computed. The initial basic feasible solution is displayed in the following simplex table :

We observe that the most negative zj – cj is  4 – 3M (= z_l – c₁). The corresponding column vector y₁, therefore, enters the basis. Further, since min.  = 5;  the element y₁₁ (=2) becomes the leading element for the first iteration

First Iteration:   Introduce y₂ and drop y₇.

In the above table, we omitted all entries of column vector y₆, because the artificial variables A_l has left the basis and we would not like it to re-enter in any subsequent iterations.

Now since the most negative (z_j—c_j) is  z₂-c₂; the non-basic vector y₂ enters the basis. Further, since min   is 2 which occurs for the  element y₃₂ ( = 1/2), the corresponding basis vector y₇ leaves the basis and the element  y₃₂ becomes the leading element for the next iteration.

Final Iteration: Optimum Solution,

It is clear from the table that all z_j – c_j are positive. Therefore an optimum basic feasible solution has been attained which is given by

x₁= 4, x₂ = 2,  maximum  z = 22.

2. Maximize z = 3x₁, + 2x₂   subject to the constraints :

2x₁ + x₂  ≤ 2,  3x₁ + 4x₂  ≥  12, x₁, x₂  ≥ 0.

 Solution:

Introducing slack variable x₃ ≥ 0,  surplus variable x₅ ≥ 0 and an artificial variable A₁ ≥ 0, the reformulated L.P.P. can be written as :

Maximize z  = 3x₁ + 2x₂ + 0.x₃ + 0.x₄ – MA₁

subject to the constraints :

2x₁ + x₂ + x₃ = 2,

3x₁ + 4x₂ – x₄ + A₁ = 12

x₁, x₂, x₃, x₄ ≥ 0 and A₁≥ 0.

An obvious   starting basic feasible solution is :

x3 = 2   and   A₁ = 12.

The iterative simplex tables are :

Initial Iteration:  Introduce y₂ and drop y₃.

Final Iteration.   No solution.

Here the coefficient of M in each z_j – c_j is non-negative and an artificial vector appears in the basis, not at the zero level. Thus the given L.P.P. does not possess any feasible solution.

 

TWO PHASE METHOD IN SIMPLEX:

First Phase:

(a) All the terms on R.H.S. should be non negative. If some are -ve then they must be made +ve as explained earlier.

(b) Express constraints in standard form.

(c) Add artificial variables in equality constraints or (>) type constraints.

(d) Form a new objective function W which consisted of the sum of all the artificial variables

W = A₁ + A₂ + …………………… + A_m

Function (W) is known as infeasibility form.

(e) Function W is to be minimized subject to constraints of original problem and the optimum basic feasible solution is obtained.

Any of the following three cases may arise:

(i) Min. W > 0 and at least one artificial variable appears in column “Basic variables” at Positive level. In such case, no feasible solution exists for the original L.P.P. and the procedure is stopped.

(ii) Min. W = 0 and at least one artificial variable appears in column “Basic Variables” at zero level. In such a case, the optimum basic feasible solution to the infeasibility form may or may not be a basic feasible solution to the given (original) L.P.P. To obtain a basic feasible solution, we continue phase I and try to drive all artificial variables out of the basis and then proceed to phase II.

(iii) Min. W=0 and no artificial variable appears in the column “Basic variables” current solution’. In such a case a basic feasible solution to the original L.P.P. has been found. Proceed to phase II.

Second Phase:

Use he optimum basic feasible solution of phase I as a starting solution for the original L.P.P. Using simplex method make iterations till an optimal basic feasible solution for it is obtained.

It may be noted that the new objective function W is always of minimization type regardless of whether the given (original ) L.P.P. is of maximization or minimization type. Let us take the following example.

Example 1 (Two phase simplex Method):

Use two-phase simplex Method to

Minimize Z =-3X – 2Y – 2Z

Subject to 5X + 7Y + 4Z < 7

-4X + 7Y+ 5Z > –2

3X + 4 V – 6Z > 29/7

X, Y, Z >0

Solution:

First Phase

It consists of following steps.

(a) In second constraint, R.H.S. is -ve, there fore it is made +ve by multiplying with minus sign on both sides

4X – 7Y – 5Z < 2

(b) Adding slack variables in the constraints

5X + 7Y + 4Z + S₁ =7

4X – 7Y – 5Z + S₂ =2

3X + 4Y – 6Z – S₃ = 29/7

where X, Y, Z, S₁, S₂, S₃ > 0

 

(c) Put X = Y= Z = 0, we get S₁ = 7, S₂ = 2, S₃ = -29/7. as initial solution. But series S₃ is -ve , we will add artificial variable A,i.e.

 

3X+ 4Y- 6Z- S₃+ A₁ =29/7

(d) Objective function which is minimization type is made maximization type i.e.

Maximize Z = 3X + 2Y + 2Z

 

(e) We introduce new objective function W = A₁ for the first phase which is to be minimized.

 

(f) Substituting X = Y = Z = S₃ = 0 in the constraints we get S₁ = 7, S₂ = 2, /A₁ = 29/7 as initial basic feasible solution Table 1 if formed.

ality test

As Cj-Ej is negative under same columns (minimization problem) the current basic feasible solution can be improved.

Iterate towards and optimal solution:

Performing iterations to get an optimal solution.

Replace S₁ by X₂. this is shown in table below

In table there is tie for the key row X column is the key column and y column is the first column of the identity. Following the method for tie breaking we find that y column does not break the tie. The next column of the identity i.e. S₂-column yields A₁-row as the key row. Thus (1/7) is the key element is made unity in table

Replace A₁ by X as shown in table below

Table 5 give optimal solution. Also since minimum W=0 and there is no artificial variable in the basic variables i.e. in the current solution, Table5 gives basic feasible solution for the Phase-ll

Second Phase:

The original objective function is

Maximize Z = 3x + 2y + 2Z + OS, + 0S₂ + 0S₃

It is to be maximized using original constraints. Using solution of phase I as the starting solution for phase II and carrying out computation using simplex algorithm we get Table 6

Key element is made unity in table7

Replace S₂ by X₃.

 

UNIT-2

TRANSPORTATION PROBLEM:

The study of optimal transportation and allocation of resources is; transportation theory or transport theory. The French mathematician Gaspard Monge formalized this problem in 1781. Major advances were made in the field during World War II by the Soviet mathematician and economist Leonid Kantorovich hence known as the Monge–Kantorovich transportation problem.

An important type of transportation problem which is addressed by the Linear Programming(LP) is in the area of physical distribution of goods and services from several supply centres to demand centres. In other words, transportation problems deal with the movement of commodities from different sources to different destinations, with the overall objective of minimizing transportation costs. Such a linear programming formulation of the transportation problem is also known as the Hitchcock–Koopmans transportation problem.

Applications of transportation model are used in the airline industry, Research and Development, Travelling Salesman, Transhipment, etc.

PREREQUISITES

To solve a transportation problem, the following information must be given:

• m= The number of sources.
• n= The number of destinations.
• The total quantity available at each source.
• The total quantity required at each destination.
• The cost of transportation of one unit of the commodity from each source to each destination.

ASSUMPTIONS

The following basic assumptions are made before using any transportation technique:

• The total quantity available at all the sources is equal to the total quantity required the destinations. If they do not match each other, dummy sources or dummy destinations are added.
• The unit transportation cost from one origin to a destination is known and certain.
• The unit cost is independent of the number of goods transported.
• The objective is to minimize the total transportation cost.
• Although transportation problems can be formulated as a LPP, other easier algorithms are developed for solving them.

SOLVING A TRANSPORTATION PROBLEM

There are basically 3 main steps

1. Formulation of the transportation model in LPP
2. Find a Basic feasible Solution (BFS)
3. Optimality test

Let’s go in detail

1. FORMULATION OF TRANSPORTATION MODEL in LPP

While solving an operation research problem, the key part lay in formulating the model by decoding the problem. For transportation problem usually, the problem will be given in a tabular form or matrix form called transportation table or cost-effective matrix.

Let’s check an example below.

 

An example transportation problem with Source ={A,B,C} with total supply=70 and Destinations={1,2,3} with total demand=70 [image by author]

Here,

Source = {A, B, C}

They represent sources with supply capacity 10,35,25 units of commodities respectively (given in orange)

Hence, total supply=10+35+25=70

Destinations= {1,2,3}

They represent destinations that require 20,25,25 units of commodities respectively (given in green).

Hence, total demand=20+25+25=70

The elements represented in the matrix (given in white) are called cost. i.e., the unit cost involved in moving unit commodity from one origin to another destination.

For example,

The cost incurred in moving 1 unit of the commodity from source A to destination 1= ₹2/-

 

The cost incurred in moving 1 unit of the commodity from source A to destination 1= ₹2/- (here, we are looking at the cross-section of source A and destination 1) [image by author]

Likewise,

The cost incurred in moving one unit of the commodity from source B to destination 2= ₹4/-

and so on. [Here, we are looking at the cross-section of source and destination]

TYPES OF TRANSPORTATION PROBLEM

Before going further, let’s check different types of transportation problem.

There are basically 2 types of transportation problem:

1. Balanced Transportation Problem
2. Unbalanced Transportation Problem

 

Classification of transportation problem into balanced and unbalanced on the basic of the available supply and required demand. [image by author]

Let’s peep into it.

1. Balanced Transportation Problem

total quantity available = total quantity required

i.e., Total supply= Total demand

Let’s check the example below.

 

An example balanced transportation problem with Source ={A,B,C} with total supply=75 and Destinations={1,2,3} with total demand=75 [image by author]

Here,

Total supply=75

Total demand=75

Hence, Total supply= Total demand

2. Unbalanced Transportation Problem

total quantity available ≠ total quantity required

i.e., Total supply≠ Total demand

The total quantity available at all the sources is equal to the total quantity required the destinations. If they do not match each other, dummy sources or dummy destination are added to make it a standard transportation problem.

There are 2 situations leading to this unbalanced condition

(i). Total Supply> Total Demand

(ii). Total supply< Total demand

(i). Total Supply> Total Demand

I.e., the total quantity available > total quantity required

Let’s check the example below.

An example unbalanced transportation problem with Source ={A,B,C} with total supply=65 and Destinations={1,2,3} with total demand=60 [image by author]

Here,

Total supply=65

Total demand=60

Hence, Total supply> Total demand

In such cases, we add a dummy destination giving dummy demand with each cost as zero (0) but dummy demand for the dummy destination as total supply-total demand.

An example unbalanced transportation problem with Source ={A,B,C} with total supply=65 and Destinations={1,2,3} with dummy demand=5 making total demand=65 [image by author]

In this example, dummy demand= 65–60=5

Thus, total supply= total demand

(ii). Total supply< Total demand

I.e., the total quantity available <total quantity required

Let’s check the example below.

 

An example unbalanced transportation problem with Source ={A,B,C} with total supply=65 and Destinations={1,2,3} with total demand=75 [image by author]

Here,

Total supply=65

Total demand=75

Hence, Total supply<Total demand

In such cases, we add a dummy source giving dummy supply with each cost as zero (0) but dummy supply for the dummy destination as total demand-total supply.

An example unbalanced transportation problem with Source ={A,B,C} with total supply=65 and Destinations={1,2,3} with dummy supply=10 making total supply=75 [image by author]

In this example, dummy supply= 75–65=10.

Thus, total supply= total demand

The solution that every problem in transportation looks for is that of the quantity from each source should go to which destination so that all demands at and at the same time the costs are kept to a minimum.

For this, we have to convert every problem to a standard problem to go further.

2. BASIC FEASIBLE SOLUTION(BFS)

There are different methods available to obtain the initial basic feasible solution. They are:

(1). North-West(N-W) Corner Rule

(2). Least Cost Method (or The Matrix Minimum Method)

(3). Vogel’s Approximation Method [VAM] (or Penalty Method)

Let’s dive into each method.

For that let’s consider an example problem for better understanding.

The question is given below.

[image by author]

The first step is to make it a standard transportation problem.

For that check whether it is a balanced or unbalanced transportation problem.

[image by author]

The given problem is a balanced transportation problem. So, let’s proceed.

Now, we have to find a basic feasible solution. For the same, we have 3 different methods. Let’s check one by one with the help of this problem.

(1). North-West(N-W) Corner Rule

N-W direction [image by author]

Select North-West Corner cell. i.e., cost of the intersection of 1st row and 1st column. [Here, 5(given in blue)]

Compare the demand and supply of that cell. [Here, 65 and 70 (given in red)]

 

[image by author]

Allocate the cell with the least value [Here, 65 (given in yellow)]

Subtract the excluded cell with the least value. i.e., the allocated cell vale. [Here, 70–65=5]

 

[image by author]

Eliminate the column or row accordingly by striking it off. [Here, the column with destination 1 (marked with red line)]

Always the total demand and supply will remain the same. (You can consider this method to verify whether you are going on the correct path or not.) Because we are allocating the cells with new values in such a way that the total demand and supply will remain the same.

[i.e., Here, 42+43+65=150 (total demand) and 5+30+50+65=150 (total supply)]

Now continue the process with remaining cells.

Again, find the North-West(N-W) cell and do the same steps as given above.

Let’s see the same in this example.

[image by author]

 

[image by author]

 

[image by author]

 

[image by author]

Here, both the demand and supply will be the same which will be further allocated in the remaining single cell. [Here, 43] (This is another method to verify whether all the above steps were correct or not.)

Methods to verify the correctness of the process:

The total demand and supply will remain the same throughout the steps.

In the last step, the single-cell will be allocated with the value in either with demand or supply as both will have the same values.

If the demand and supply have the same values; a tie, you can choose any one of them to allocate the cell making other value zero. (It’s purely user’s choice to decide which one to select.👍)

The final table with all allocated cell will be like this.

This gives the initial feasible solution by the N-W Corner method.

[image by author]

Now let’s calculate the cost associated with these allocations.

To find the same add all the products of all allocated cell values (given in yellow) and the cost of the respective cell (given in blue).

i.e., Total cost=(65×5) +(5×7) +(30×4) +(7×7) +(43×7)

=325+35+120+49+301

=830

Now, let’s understand what we have found out

₹830-represents the total cost involved in moving the commodities.

The path followed is represented by the red arrows as we found by the N-W Corner method.

 

[image by author]

Let’s represent the same in a table

 

the final solution table [image by author]

This may or may not represent the optimal solution for this problem i.e., there may exist other ways of allocating which may give a better solution with a lower total cost.
An optimality test has to be carried out to test whether the obtained answer is optimal. If not, the optimality test leads us to one for a probable improvement.

(2). Least Cost Method (or Matrix Minimum method)

Let’s discuss with the same example.

 

[image by author]

 

[image by author]

Select the least value among all the costs (given in white). i.e., minimum cost. [Here, 4(given in blue)]

Here, there are two cells with the least cost. It’s purely user’s choice to decide which one to select.

If there are more than 1 cell with the same least cost; a tie, you can choose anyone among them. (It’s purely user’s choice to decide which one to select.👍)

[image by author]

Compare the demand and supply of that cell. [Here, 30 and 65 (given in red)]Allocate the cell with the least value [Here, 30 (given in yellow)]

Subtract the excluded cell with the least value. i.e., the allocated cell value. [Here, 65–30=35]

Eliminate the column or row accordingly by striking it off. [Here, the row with source B (marked with red line)]

Always the total demand and supply will remain the same. (You can consider this method to verify whether you are going on the correct path or not.) Because we are allocating the cells with new values in such a way that the total demand and supply will remain the same.

[i.e., here, 35+42+43+30=150 (total demand) and 70+50+30=150 (total supply)]

Now continue the process with remaining cells.

Again, find the least cost cell and do the same steps as given above.

Let’s see the same in this example.

[image by author]

 

[image by author]

 

[image by author]

 

[image by author]

Here, both the demand and supply will be the same which will be further allocated in the remaining single cell. [Here, 43] (This is another method to verify whether all the above steps were correct or not.)

Methods to verify the correctness of the process:

The total demand and supply will remain the same through the steps.

In the last step, the single the cell will be allocated with the value in either with demand or supply as both will have the same values.

If the demand and supply have the same values; a tie, you can choose any one of them to allocate the cell making other value zero. (It’s purely user’s choice to decide which one to select.👍)

The final table with all the allocated cell will be like this.

This gives initially feasible solution by the least-cost method.

 

[image by author]

Now let’s calculate the cost associated with these allocations.

To find the same add all the products of all allocated cell values (given in yellow) and the cost of the respective cell (given in blue).

i.e., Total cost=(35×5) +(30×4) +(35×7) +(7×7) +(43×7)

=175+120+245+49+301

=890

Now, let’s understand what we have found out

₹890-represents the total cost involved in moving the commodities.

The path followed is reprinted by the red arrows as we found by the least-cost method.

 

[image by author]

Let’s represent the same in a table.

 

the final solution table [image by author]

This may or may not represent the optimal solution for this problem i.e., there may exist other ways of allocating which may give a better solution with a lower total cost
An optimality test has to be carried out to test whether the obtained answer is optimal. If not, the optimality test leads us to one for a probable improvement.

(3). Vogel’s Approximation Method [VAM] (or Penalty Method)

Let’s discuss with the same example.

 

[image by author]

Selecting the cost cell to be allocated is not that easy in VAM as if we discussed in the N-W Corner method and least cost cell method. (Chill dude,it’s not that difficult though. 😇But the process is a bit lengthier than before.😅)

In the VAM, we have to first in the differences between the two lowest costs in each row and column. These are known as penalties/ extra costs.

The difference between the two smallest values is considered.

 

 

Here, Penalties= {2,0,1,1,3,1}]

Now find the maximum value among the penalties irrespective of row or column.

[Here, max (Penalties)=3 (given in pink)]

If there is a tie, choose anyone. (It’s purely user’s choice to decide which one to select.👍)

Now, look into the respective row or column accordingly.

[Here, the column (given in pink)]

Select the least value among all the costs (given in pink). i.e., minimum cost. [Here, 4(given in blue in the figure below)]

If there are more than 1 cell with the same least cost; a tie, you can choose anyone among them. (It’s purely user’s choice to decide which one to select.👍)

 

Allocate the cell with the least value [Here, 30 (given in yellow)]

Subtract the excluded cell with the least value. i.e., the allocated cell vale. [Here, 42–30=12]

Eliminate the column or row accordingly by striking it off. [Here, the column with source B (marked with red line)]

Always the total demand and supply will remain the same. (You can consider this method to verify whether you are going on the correct path or not.) Because we are allocating the cells with new values in such a way that the total demand and supply will remain the same.

[i.e., here, 65+12+43+30=150 (total demand) and 70+50+30=150 (total supply)]

Now continue the process with remaining cells.

Again, find the penalty and do the same steps as given above.

Let’s see the same in this example.

Here, both the demand and supply will be the same which will be further allocated in the remaining single cell. [Here, 43] (This is another method to verify whether all the above steps were correct or not.)

Methods to verify the correctness of the process:

The total demand and supply will remain the same through the steps.

In the last step, the single the cell will be allocated with the value in either with demand or supply as both will have the same values.

If the demand and supply have the same values; a tie, you can choose any one of them to allocate the cell making other value zero. (It’s purely user’s choice to decide which one to select.👍)

The final table with all the allocated cell will be like this.

This gives an initial feasible solution by VAM.

[image by author]

Now let’s calculate the cost associated with these allocations.

To find the same add all the products of all allocated cell values (given in yellow) and the cost of the respective cell (given in blue).

i.e., Total cost=(65×5) +(5×7) +(30×4) +(7×7) +(43×7)

=325+35+120+49+301

=830

Now, let’s understand what we have found out

₹830-represents the total cost involved in moving the commodities.

The path followed is represented by the red arrows as we found by VAM.

[image by author]

 

the final solution

This may or may not represent the optimal solution for this problem i.e., there may exist other ways of allocating which may give a better solution with a lower total cost.
An optimality test has to be carried out to test whether the obtained answer is optimal. If not, the optimality test leads us to one for a probable improvement.

3. OPTIMALITY Test

While a basic feasible solution may take care of all the sources and location restrictions it need not give a solution with the least cost. There could be several basic feasible solutions but the one that minimizes the total transportation cost is said to be the optimal solution. After a basic feasible solution has been identified by anyone of the methods listed above, the solution is to be further tested for Optimality tests

 

Assignment models:

Assignment models is one of topics of operations research. It consists of assigning a specific (person or worker) to a specific (task or job) assuming that there are the number of persons equal to the number of tasks available. The optimal result is to assignment one person to one job, contrast to the transportation models the source is connected to one or more of destination. The most common method to solve assignment models is the Hungarian method. In this paper introduced another method to solve assignment models by use the graph in the general formula directly.

The edges are represented the cost of assigning person to task, the nods are represented the tasks and persons. The solution will be by choosing the minimum cost (edge) from the costs (edges) and delete the selected edge as well as nodes associated with the edge, then delete all other edges associated with the nodes. Repeat the process until all workers are assigned to each tasks and be the solution is the optimal solution.

 

Keywords: Assignment problems, Hungarian method, Graph theory

 

1  Introduction

 

“The best person for the job” is an apt description of the assignment model. [3] An important topic, put forward immediately after the transportation problem, is the assignment problem. This is particularly important in the theory of decision making. [4] The assignment models is a special state of a linear programming models and its similar to the transportation model. The different between the assignment models and transportation models is the focuses on the fact that transportation models assignment the multiple sources to multiple destinations while the assignment models assignment one source to one destinations, which is a special case of transportation models. [7]

 

 

 

The situation can be illustrated by the assignment of workers with varying degrees of skill to jobs. [5]

The assignment models arises because available resources such as (workers, jobs or machines etc.) have varying degrees of skills for showing the different activities. [1]

Therefore, distance, time, profit or cost of performing different activities are be different. The assignment models are completely specified by its two components, the assignment which represents the underlying combinatorial structure and the objective function to be optimized. [1]

Assignment models deals with the topic how to assign n workers to n jobs such that the cost incurred is minimized. [7]

It was developed and published in 1955 by H. Kuhn, who gave the name “Hungarian method” because the method in general based on the earlier works of two Hungarian mathematicians: D. Kőnig and J. Egerváry and is therefore known as Hungarian method of assignment models. [1], [2]

Each assignment models has a matrix or table connected with it. Generally the row include the peoples or objects we wish to assign, and the column include the tasks or jobs we want them assigned. Consider a problem of assignment of n sources (resource) to n destinations (activities) so as to minimum the overall time or cost in such a way that each sources can connect with one and only one destination. The general Graph theory of assignment model is given as under. [4], [7]

 

 

 

 

 

 

Figure (1): Network representation of the assignment problem

 

 

 

The cost matrix (Cij) is given as under. [7]

 

Figure (2): Matrix of Costs

 

Let the cost of i^th persons assigned to j^th jobs be represent by cij.

Let the number of unites by assignment the persons ith to a jobs jth be represent by

Xij.

Xij = 1 if i person is assigned j job.

Or Xij = 0 if i person is not assigned j job. The objective function is:

n        n

ååcij xij

 

Min Z=

i=1 j =1

 

 

å

Subject to the constraint

 

å

X

= 1

n

i=1         ij

and

n

X

j =1         ij

= 1

, Xij =1 or 0

 

 

For all i=1,2,…,n     and j =1,2,…,n [3], [5], [7]

 

2  Hungarian Method

 

Step (1): select the smallest number from each row and subtract it from the other numbers in the same row as well as for the columns.

Step (2): Draw the minimum number of vertical and horizontal lines to cover all zeros in all rows and columns in the matrix. Let the minimum number of lines is L and the number of columns or rows is n.

If L = n, the matrix then an optimal assignment can be find, then proceed to step (5).

If L < n then proceed to step (3).

Step (3): Determine the smallest number in the matrix, not covered by L lines. Subtract this minimum number from all uncovered numbers and add the same number at the intersection of horizontal and vertical lines.

Step (4): Repeat step (2) and step (3) until L = n become.

 

 

 

Step (5): To find assignment by test assigning all the zeroes in the rows and columns. The solution is optimal when assigning one and only one zero per row and column in given matrix.

Step (6): Repeat the step (5) until to exactly find one zero to be assignment in each row (column), then process ends.

Step (7): Write the numbers that corresponding to the zeros assigned in the previous step in the main matrix and calculate the objective function. [7]

 

3  The proposed method

 

In the proposed model use the graph theory depends of the assignment model and according to the following steps:

1. Converting the problem into a graph theory according to the general formulation of the assignment model.

2 – Choose the lowest cost between workers and tasks.

3. Delete the selected edge as well as the nods associated with
4. Repeat the previous step to obtain each worker associated with only one
5. Calculate the objective
6. When exist more than one edges has the same cost, we find a multi-solution and find the objective function for each solution and choose the lowest value for the objective

 

4  Example 1

Four jobs J1, J2, J3 and J4 are to be assigned to four persons P1, P2, P3 and P4. The processing costs are given in the following matrix. Find the optimal assignment which will lower the total processing cost.

 

First: Solution by Hungarian method.

Step (1): Row subtraction

 

Step (2): Column subtraction

 

 

 

 

 

Step (3):

Step (4):

Step (5) and Step (6):

Step (7):

So the optimal assignment for all persons to jobs as shown in the following: P1 → J1 =8

P2 → J3 =12 P3 → J2 =19 P4 → J4 =9

4       4

 

 

Total minimum cost is Z=

ååcij xij

i=1 j =1

 

Z= 8 × 1+ 12 × 1+ 19× 1+9× 1 = 48

 

 

 

Second: Solution by proposed method

Step (1):

Step (2):

Min cost P1 → J1 =8

Step (3):

Delete P1 and J1

 

Step (4):

Min cost P4 → J4 = 9 Delete P4 and J4

 

Min cost P2 → J3 = 12 Delete P2 and J3

 

 

 

 

Min cost P3 → J2 = 19

Step (5):

4        4

ååcij xij

 

Total minimum cost is Z=

i=1 j=1

 

Z= 8 × 1+ 9 × 1+ 12× 1+9× 1 = 48

 

5  Conclusion

 

The proposed method is easier and faster than the known Hungarian method and the final output of the proposed method is similar to an solution to produced when using the Hungarian method.

 

UNIT-3

Introduction to Sequencing:

Sequencing Problems,

Solution to Sequencing Problem – Processing n-jobs through one machine, Processing n-jobs through two machines,

Processing n-jobs through Three Machines, Processing two through m- machines, processing n-jobs through m-machines.

         Network Models:

         PERT AND CPM

Introduction

Analysis

Construction & Identification

Slack and Float Variable

 

INTRODUCTION

The short-term schedules show an optimal order (sequence) and time in which jobs are processed as well as show timetables for jobs, equipment, people, materials, facilities and all other resources that are needed to support the production plan. The schedules should use resources efficiently to give low costs and high utilisations. Other purpose of scheduling are, minimising customers wait time for a product, meeting promised delivery dates, keeping stock levels low, giving preferred working pattern, minimising waiting time of patients in a hospital for different types of tests and so on.

The general scheduling or sequencing problem may be described as: Let there be n jobs to be performed one at a time on each of m machines. The sequence (order) of the machines in which each job should be performed is given. The actual or expected time required by the jobs on each of the machines is also given. The general sequencing problem, therefore, is to find the sequence out of (n!)^m possible sequences which minimise the total elapsed time between the start of the job in the first machine and the completion of the last job on the last machine.

In particular, if n = 3 and m= 3, then total number of possible sequences will be (3!)³ = 216. Theoretically, it may be possible to find optimum sequence but it will require a big computational time. Thus, one should adopt sequencing technique.

To find optimum sequence we first calculate the total elapsed time for each of the possible sequences. As stated earlier, even if values of m and n are very small, it is difficult to get the desired sequence with total minimum elapsed time. However, due to certain rules designed by Johnson, the task of determining an optimum sequence has become quite easy.

 

NOTATIONS, TERMINOLOGY AND ASSUMPTIONS

Notations

tij = Processing time (time required) for job i on machine j.

T = Total elapsed time for processing all the jobs. This includes idle time, if any. Iij = Idle time on machine j from the end of job (j – 1) to the start of job i.

 

Terminology

• Number of Machines: The number of machines refer to the number of service facilities through which a job must pass before it is assumed to be
• Processing Time: It is the time required by a job on each
• Processing Order: It refers to the order (sequence) in which machines are required for completing the
• Idle Time on a Machine: It is the time for which a machine does not have a job to process, e idle time from the end of job (i-1) to the start of job i.
• Total Elapsed Time: It is the time interval between starting the first job and completing the last job including the idle time (if any) in a particular order by the given set of
• No Passing Rule: It refers to the rule of maintaining the order in which jobs are to be processed on given machines. For example, if n jobs are to be processed on two

machines M1 and M2 in the order M1 M2, then each job should go to machine M1 first and then to M2.

 

Assumptions

1. The processing time on different machines are exactly known and are independent of the order of the jobs in which they are to be
2. The time taken by the job in moving from one machine to another is
3. Once a job has begun on a machine, it must be completed before another job can begin on the same
4. All jobs are known and are ready for processing before the period under consideration begins.
5. Only one job can be processed on a given machine at a
6. Machines to be used are of different
7. The order of completion of jobs are independent of the sequence of

 

PROCESSING n JOBS THROUGH TWO MACHINES

Let there be n jobs, each of which is to be processed through two machines, M1 and M2 in the order M1 M2, i.e. each job has to be passed through the same sequence of operations. In other words, a job is assigned on machine M1 first and after it has been completely processed on machine M1, it is assigned to machine M2. If the machine M2 is not free at the moment for processing the same job, then the job has to wait in waiting line for its turn on machine M2,

i.e. passing is not allowed.

Since passing is not allowed, therefore, machine M1 will remain busy in processing all the n jobs one-by-one which machine M2 may remain idle time of the second machine. This can be achieved only by determining sequence of n jobs which are to be processed on two machines M1 and M2. The procedure suggested by Johnson for determining the optimal sequence can  be summarised as follows:

 

The Algorithm

Step 1              List the jobs along with their processing times on each machine in a table as shown below:

Processing Time on Machine	Job Number 1                 2               3                  n
M1	t11                  t12                 t13                      t1n
M2	t21                  t22                 t23                         t2n

Step 2              Examine the columns for processing times on machines M1 and M2, and find the smallest processing time in each column, i.e find out, min. (t1j, t2j) for all j.

Step 3(a)             If the smallest processing time is on machine M1, then schedule the job as early as possible without moving jobs already schedules, i.e place the job in the first available position in the sequence. If the processing time is on machine M2, then schedule the job as late as possible without moving any jobs already scheduled, i.e. place the job in the last available position in the sequence.

1. If there is a tie in selecting the minimum of all the processing times, then there may be three situations:

 

1. Minimum among all processing times is same for the machine e. min (t1j, t2j) = t2k = t2r,then process the kth job first and the rth job last.
2. If the tie for the minimum occurs among processing times t1j on machine M1 only, thenselect the job corresponding to the smallest job subscript
3. If the tie for the minimum occurs among processing times t2j on machine M2, then selectthe job corresponding to the largest job corresponding to the largest job subscript

 

Step 4             Remove the assigned jobs from the table. If the table is empty, stop and go to Step 5. Otherwise, got to Step 2.

 

Step 5              Calculate idle time for machines M1 and M2:

1. Idletime for machine M1 = (Total Elapsed Time) – (Time when the last job in a sequence

finishes on machine M1)

1. Idletime for machine M2 = Time at which the first job in a sequence finishes on machine

 

M1 + ∑

𝑛

𝑗=2

{(Time when the jth job in a sequence starts on machine M2) – (Time when the

 

(j – 1)th job in a sequence finishes on machine M2)}.

 

𝑗=1

Step 6              The total elapsed time to process all jobs through two machines is given by Total Elapsed time = Time when the nth job in a sequence finishes on Machine M2.

 

= ∑

𝑛

𝑗=1

𝑀2𝑗 + ∑^𝑛

𝐼2𝑗

 

where M2j = Time required for processing jth job on machine M2.

I2j = Time for which machine M2 remains idle after processing (j – 1)th job and before starting work in jth job.

EXAMPLE 1

Find the sequence that minimises the total elapsed time required to complete the following tasks on two machines:

Task	A	B	C	D	E	F	G	H	I
Machine I	2	5	4	9	6	8	7	5	4
Machine II	6	8	7	4	3	9	3	8	11

Solution:

The smallest processing time between the two machines is 2 which corresponds to task A on Machine I. Thus, task A is scheduled as early as possible to give the sequence as shown below:

A

After the task A has been set for processing first, we are left with 8 tasks and their processing times as given below:

Task	B	C	D	E	F	G	H	I
Machine I	5	4	9	6	8	7	5	4
Machine II	8	7	4	3	9	3	8	11

The minimum processing time in this reduced problem is 3 which corresponds to task E and G both on machine II. Since the corresponding processing time of task E on machine I is less than the corresponding processing time of task G on machine I, therefore, task E will be scheduled in the last and task G shall be scheduled before it. Tasks E and G will not be considered further. Thus, current partial sequence of scheduling tasks becomes:

A

G

E

A set of processing times now gets reduced to:

Task	B	C	D	F	H	I
Machine I	5	4	9	8	5	4
Machine II	8	7	4	9	8	11

The smallest processing time in this reduced problem is 4, which corresponds to task C and I on machine I and to task D on machine II. Thus task C will be placed in the second sequence cell and task I in the third sequence cell and task D in the sequence cell before task G. The entries of the partial sequence are now:

A

C

I

D

G

E

The set of processing time now gets reduced as follows:

Task	B	F	H
Machine I	5	8	5
Machine II	8	9	8

the smallest processing time in this reduced problem is 5, which corresponds to tasks B and H both on machine I. Since the corresponding processing times of B and h on machine II is same, therefore, either of these two tasks can be placed in fourth and fifth sequence cells. Thus, it indicates an alternative optimal sequence. the optimal sequences are, therefore, given below:

A

C

I

B

H

F

D

G

E

 

A

C

I

H

B

F

D

G

E

The minimum elapsed time for machines I and II is calculated as shown in Table 1.

Task Sequence	Machine I		Machine II
	Time In	Time Out	Time In	Time Out
A	0	2	2	8
C	2	6	8	15
I	6	10	15	26
B	10	15	26	34
H	15	20	34	42
F	20	28	42	51
D	28	37	51	55
G	37	44	55	58
E	44	50	58	61

In table 1, the minimum elapsed time, i.e time from start of task A to completion of last task  E is 61 hours. During this time the machine I remains idle for 61 – 50 = 11 hours. The idle time for machine II is equal to the time at which the first task A in the sequence finishes on machine I plus the last task E in the sequence starts on machine II minus the last but one task G finishes on machine II, i.e 2 + 58 – 58 = 2 hours.

PROCESSING n JOBS THROUGH THREE MACHINES

Johnson provides an extension of his procedure to the case in which there are three instead of two machines. Each job is to be processed through three machines M1, M2 and M3. The list of jobs with their processing times is given below. An optimal solution to this problem can be obtained if either or both of the following conditions hold good.

Processing time on Machine	Job Number
	1	2	3	4
M1 M2 M3	t11 t21 t31	t12 t22 t32	t13 t23 t33	t1n t2n t3n

1. The minimum processing time on machine M1 is at least as great as the maximum processing time on machine M2, that is,

min t1j ≥ max t1j,            j = 1, 2, 3, …n

2. The minimum processing time on machine M3 is at least as great as the maximum processing time on machine M2, that is

min t3j ≥ max t2j,             j = 1, 2, 3, …n

If either or both the above conditions hold good, then the steps of the algorithm can be summarised in the following steps:

 

THE ALGORITHM

Step 1: Examine processing times of given jobs on all three machines and if either one or both the above conditions hold, then go to step 2, otherwise the algorithm fails.

Step 2: Introduce two fictitious machines, say G and H with corresponding processing times given by

1. tGj = t1j + t2j,   j = 1, 2, 3,…. n.

that is, processing time on machine G is the sum of the processing times on machines M1 and M2, and

1. tHj = t2j + t3j,   j = 1, 2, 3,…. n.

that is, processing time on machine H is the sum of the processing times on machines M2 and M3.

Step 3: Determine the optimal sequence of jobs for this n-job, two machine equivalent sequencing problem with the prescribed ordering GH in the same way as discussed earlier.

EXAMPLE

Find the sequence that minimises the total time required in performing the following jobs on three machines in the order ABC. Processing times (in hours) are given in the following  table:

Job	1	2	3	4	5
Machine A	8	10	6	7	11
Machine B	5	6	2	3	4
Machine C	4	9	8	6	5

 

Solution: Here, min (tAj) = 6; Min (tCj) = 4; max (tBj) = 6. Since min (tAj) ≥ (tBj) for all j is satisfied, the given problem can be converted into a problem of 5 jobs and two machines. The processing time on two fictitious machines G and H can be determined by the following relationships:

tGj = tAj + tBj, j = 1, 2, 3, n.

and tHj = tBj + tCj, j = 1, 2, 3, n.

The processing times for the new problem are given below:

Job	1	2	3	4	5
Machine G Machine H	8 + 5 = 13 5 + 4 = 9	10 + 6 = 16 6 + 9 = 15	6 + 2 = 8 2 + 8 = 10	7 + 3 = 10 3 + 6 = 9	11 + 4 = 15 4 + 5 = 9

When the algorithm described for n jobs on two machines is applied to this problem, the optimal sequence so obtained is given by

3

2

5

1

4

The total minimum elapsed time is given in Table 1:

Job Sequence	Machine A		Machine B		Machine C
	Time In	Time Out	Time In	Time Out	Time In	Time Out
3	0	6	6	8	8	16
2	6	16	16	22	22	31
5	16	27	27	31	31	36
1	27	35	35	40	40	44
4	35	42	42	45	45	51

Table 1 indicates that the minimum total elapsed time is 51 hours. The idle time for machines A, B and C is 9 (=51 – 42) hours, 6 (= 51 – 45) hours and 9 (= 8 – 0) + (45 – 44) hours, respectively.

 

PROCESSING n JOBS THROUGH m MACHINES

Let there be n jobs, each of which is to be processed through m machines, say  M1, M2,……. Mm

in the order M1, M2,……. Mm. The optimal solution to this problem can be obtained if either or

both of the following conditions hold good.

(a)    Min {t1j} ≥ Max { t1j}; j = 2, 3, ….. m – 1

and or (b) Min {tmj} ≥ Max { tij}; j = 2, 3, ….. m – 1

that is, the minimum processing time on machines M1 and Mm is as great as the maximum processing time on any of the remaining (m – 1) machines.

If either or both these conditions hold good, then the steps of the algorithm can be summarised in the following steps:

Step 1: Find, Min { t1j}, Min {tmj} and max {tij}and verify above conditions. If either or both the conditions mentioned above hold, then go to step 2. Otherwise the algorithm fails.

Step 2: Convert m-machine problem into 2-machine problem by introducing two fictitious machines, say

(i) tGj = t1j + t2j + t3j  +……+tm – 1j   j = 1, 2, 3,… n.

i.e. processing time of n-jobs on machine G is the sum of the processing times on Machines M1, M2 Mm – 1j

(ii) tHj = t2j + t3j + t4j +……+ tmj   j = 1, 2, 3,…. n.

 

i.e. processing time of n-jobs on machine H is the sum of the processing times on Machines M1, M2 Mmj.

Step 3: The new processing times so obtained can now be used for solving n-job, two machines equivalent sequencing problem with the prescribed ordering HG in the same way as t2j + t3j +……+tm – 1j = k (constant)

for all j = 1, 2, 3, ….. m – 1, then the optimal sequence can be obtained for n-jobs and two machines M1 and Mm in the order M1 Mm as usual.

2. If t1j = tmj and tGj = tHj, for all j = 1, 2, 3, n, then total number of optimal sequences will

be n and total minimum elapsed time in these cases would also be the same.

3. The method described above for solving n-jobs and m-machines sequencing problem is not a general method. It is applicable only to certain problems where the minimum cost (or time) of processing the jobs through first and/or last machine is more than or equal to the cost (or time) of processing the jobs through remaining

EXAMPLES

1. Find an optimal sequence for the following sequencing problems of four jobs and five machines when passing is not allowed of which processing time (in hours) is given below:

Job	Machines
	M1	M2	M3	M4	M5
A	7	5	2	3	9
B	6	6	4	5	10
C	5	4	5	6	8
D	8	3	3	2	6

Also find the total elapsed time. Solution: Here,

Min (tM1, j) = 5 = tM1, C

Min (tM5, j) = 6 = tM5, D

and Max { tM2, j, tM3, j, tM4, j} = {6, 5, 6} respectively.

Since the condition of Min (tM5, j) ≥ Max { tM2, j, tM3, j, tM4, j} is satisfied, therefore the given problem can be converted into a four jobs and two machines problem as G and H. The processing times of four jobs denoted by tGj and tHj on G and H, respectively are as follows:

Job	A	B	C	D
Machine G Machine H	17 19	21 25	20 23	16 14

where tGj = ∑𝑚−1 𝑡𝑖𝑗 and tHj = ∑𝑚 𝑡𝑖𝑗.

𝑖=1                                                    𝑖=2

Now using the optimal sequence algorithm, the following optimal sequence can be obtained.

A

C

B

D

The total elapsed time corresponding to the optimal sequence can be calculated as shown in Table 1, using the individual processing times given in the original problem.

Table 1 shows that the minimum total elapsed time is 51 hours. The idle time for machines M1, M2, M3, M4 and M5 is 25, 33, 37 and 18 hrs respectively.

Table 1            Minimum Elapsed Time

Job Sequence	Machine
	M1	M2	M3	M4	M5
A B	0 – 7 7 – 12	7 – 12 12 – 18	12 – 14 16- 21	14 – 17 21 – 27	16 – 26 27 – 35

 

C D

12 – 18 18 – 26

18 – 24 26 – 29

24 – 28 29 – 32

28 – 33 33 – 35

35 – 45 45 – 51

 

2. Solve the following sequencing problem giving an optimal solution when passing is not allowed.

Machine	Job
	A	B	C	D	E
M1	11	13	9	16	17
M2	4	3	5	2	6
M3	6	7	5	8	4
M4	15	8	13	9	11

Solution: From the data of the problem it is observed that Min (tM1, j) = 9 = tM1, C

Min (tM4, j) = 8 = tM4, B

and Max { tM2, j} = 6 = , tM2, E;   Max { tM3, j} = 8 = , tM2, D. Since both the conditions

Min (tM1, j) ≥ Max { tM2, j; tM3, j} ; j = 1, 2,…. , 5

are satisfied, therefore given problem can be converted into a 5-jobs and 2-machine problem as G and H.

Further, it may be noted that, tM2, j +  tM3, j  = 10 (a fixed constant) for all j (j = 1, 2,.. , 5).

Thus the given problem is reduced to a problem of solving 5-jobs through 2-machines M1 and M4 in the order M1 M4. This means machines M2 and M4 will have no effect on the optimality of the sequences.

The processing times of 5 jobs on machine M1 and M4 is as follows:

Job	A	B	C	D	E
Machine M1 Machine M4	11 15	13 8	9 13	16 9	17 11

Now using the algorithm described earlier, the optimal sequence so obtained as follows:

C

A

E

D

B

The total elapsed time corresponding to the optimal sequence is 83 hours as shown in table 1, using the individual processing times given in the original problem:

Table 1 Minimum Total Elapsed Time

Job Sequence	Machine
	M1	M2	M3	M4
C	0 – 9	9 – 14	14 – 19	19 – 32
A	9 – 20	20 – 24	24 – 30	32 – 45
E	29 – 36	36 – 42	42 – 46	46 – 57
D	36 – 52	52 – 54	54 – 62	62 – 71
B	52 – 65	65 – 68	68 – 75	75 – 83

 

PROCESSING TWO JOBS THROUGH m MACHINES

Let there be two jobs A and B each of  which is to processed on m machines say M1, M2,         ,

Mm in two different orders. The technological ordering of each of the two jobs through m machines is known in advance. Such ordering may not be same for both the jobs. The exact  or expected processing times on the given machines are known. Each machine can perform

 

only one job at a time. The objective is to determine an optimal sequence of processing the jobs so as to minimise total elapsed time.

The optimal sequence in this case can be obtained by using graph. The procedure can be illustrated by taking examples.

Example 1: Use the graphical method to minimise the time needed to process the following jobs on the machines shown, i.e. each machine find the job which should be done first. Also calculate the total elapsed time to complete both jobs.

Machine

 

Job 1 {Sequence:	A	B	C	D	E
Time (hrs)	3	4	2	6	2

 

Machine

 

Job 2 {Sequence:	A	B	C	D	E
Time (hrs)	5	4	3	2	6

Solution

The solution procedure for solving the above problem can be summarised in the following steps:

1. Draw the set of axes at right angle to each other where x-axis represents the processing time of job 1 on different machines while job 2 remains idle and y-axis represents processing time of job 2 while job 2 remain
2. Mark the processing times for jobs 1 and 2 on x-axis and y-axis, respectively according to the given order of machines as shown in the figure:

 

 

20                   Idle time for Job 1

Idle time for job 1

 

14

12

A

9

 

 

C

5

 

B

0           3               7     9               15       17 Job 1

 

Graphical solution of 2-Jobs and m-Machines Sequencing Problem

For example, machine A takes 3 hours for job 1 and 3 hours for job 2. Construct the rectangle for machine A as shown in above Figure. Similarly, construct other rectangles for machines B, C, D and E.

 

3. Construct various blocks starting from the origin by pairing the same machine until a point marked ‘finished’ is
4. Draw a line starting from origin to the point marked ‘finish’ by moving horizontally, vertically and diagonally along a line which makes an angle of 45° with the horizontal axis. Moving horizontally along this line indicates that first job is under process while second job is idle. Similarly, moving vertically along this line indicates that the second job is under process while first job is The diagonal movement along this line shows that both the jobs are under process simultaneously.

Since simultaneous processing of both jobs on a machine is not possible, therefore, diagonal movement is not allowed. In other words, diagonal movement through rectangle areas is not allowed.

5. An optimal path is one that minimises the idle time for both the Thus, we must choose the path on which diagonal movement is maximum as shown in the above figure.
6. Total elapsed time is obtained by adding the idle time for either job to the processing time for that In this example, the idle time for the chosen path is found to be 5 hrs and 2 hrs for jobs 1 and 2, respectively. The total elapsed time is calculated as follows:

Elapsed time, Job 1 = Processing time of Job 1 + Idle time for Job 1

= 17 + (2 + 3) = 22 hrs.

Elapsed time, Job 2 = Processing time of Job 2 + Idle time for Job 2

= 22 + (17-15) = 24 hours.

EXERCISES

1. Explain the four elements that characterise a sequencing
2. Explain the principal assumptions made while dealing with sequencing
3. Give Johnson’s procedure for determining an optimal sequence for processing n items on two machines. Give justification of the rule used in the
4. What is no passing rule in a sequencing algorithm? Explain the principal assumptions made while dealing with sequencing
5. Give three different examples of sequencing problems from your daily
6. We have five jobs, each of which must be processed on the two machines A and B in the order Processing times in hours are given in the table below:

Job	1	2	3	4	5
Machine A	5	1	9	3	10
Machine B	2	6	7	8	4

7. We have 5 jobs each of which must go through the machines A, B and C in the order Processing times (in hours) is as follows:

Job	1	2	3	4	5
Machine A	5	7	6	9	5
Machine B	2	1	4	5	3
Machine C	3	7	5	6	7

8. What do you understand by the following terms in the context of sequence of jobs:
9. Job arrival pattern 2. Number of machines 3. The flow pattern in the shop
10. the criteria of evaluating the performance of a schedule.
11. Find an optimal sequence for the following sequencing problem of four jobs and five machines (when passing is not allowed) of which processing time (in hrs) is as follows:

Job	1	2	3	4
Machine M1	6	5	4	7
Machine M2	4	5	3	2
Machine M3	1	3	4	2
Machine M4	2	4	5	1
Machine M5	8	9	7	5

Also find the total elapsed time.

10. Two jobs are to be processed on four machines A, B, C and D. The technological order for these jobs on machines is as follows:

Job 1:  A         B         C         D Job 2: D                        B         A         C

Processing times are given in the following table:

Machines

	A	B	C	D
Job 1	4	6	7	3
Job 2	4	7	5	8

Find the optimal sequence of jobs on each of the machines.

 

 

Network Models:

A Project such as setting up of a new milk plant, research and development in an organization, development of a new milk product, marketing of a product etc. is a combination of interrelated activities (tasks) which must be executed in a certain order before the entire task can be completed. The activities are interrelated in a logical sequence in such a way that same activities can not start until some others are completed. An activity in a project usually viewed as job requiring resources for its completion. The objectives of project management can be described in terms of a successful project which has been finished on time, within the budgeted cost and to technical specifications and to the satisfaction level of end users. Normally for any project, one may be interested in answering questions such as

1. i)  What will be the expected time of project completion?
2. ii) What is the effect of delay of any activity on the overall completion of project?

iii) How to reduce the time to perform certain activities in case of availability of additional funds?

1. iv) What is the probability of completion of project in time?

 

The OR techniques used for planning, scheduling and controlling large and complex projects are often referred to as network analysis. A network is a graphical representation consisting of certain configuration of arrows and nodes for showing the logical sequence of various tasks to be performed to achieve the project objectives. Around five decades ago the planning tool was Gantt bar chart which specifies start and finish time for each activity on a horizontal time scale. The disadvantage is that there is no interdependency among the many activities which control the progress of the project. Now-a-days we use a technical tool for planning, scheduling and controlling stages of the projects known as Critical Path Method (CPM) and Project Evaluation & Review Technique (PERT). The techniques of PERT and CPM prove extremely valuable in assisting the mangers in handling such projects and thus discharging their project management responsibilities both at planning and controlling stages of the projects. Commonly used project management techniques are:

1. a)Critical Path Method (CPM) and
2. b)Project Evaluation and Review Technique (PERT)

18.2  Historical Development

CPM/PERT or Network Analysis as the technique is sometimes called, developed along two parallel streams, one industrial and the other military. CPM was developed in 1957 by  J. E. Kelly of Remington Rand and M. R. Walker of E. I. Du Pont de Nemours & Co. PERT was devised in 1958 for the POLARIS missile program by the Program Evaluation Branch of the Special Projects office of the U. S. Navy, helped by the Lockheed Missile Systems division and the Consultant firm of Booz-Allen & Hamilton.

Both are basically time oriented methods laid to determination of a time schedule for project. The major difference between these two techniques is that PERT is a Probabilistic approach for the determination of time estimates of different activities not exactly known to us. In the case of CPM, different estimates are known as they are deterministic in nature. But now a days both these techniques are used for one purpose. Initially the PERT technique was applied to research and development projects while the CPM was used towards construction projects.

18.3  Methodology in CPM/PERT Technique

The methodology involved in network scheduling by CPM/PERT for any project consists of the following four stages:

18.3.1  Planning

It is started by splitting the total project into small projects. The smaller projects are further divided into different activities and are analyzed by a department or section. The relationship of each activity with respect to other activities are defined and established.

18.3.2  Scheduling

The objective of scheduling is to give the earliest and the latest allowable start and finish time of each activity as well as its relationship with other activities in the project. The schedule must pinpoint the critical path i.e. time activities which require special attention if the project is to be completed in time.

18.3.3  Allocation of resources

Allocation of resources is performed to achieve the desired objective. Resource is a physical variable such as labour, finance, space, equipment etc. which will impose a limitation for completion of a project.

18.3.4  Controlling

The final phase in the project management is controlling. After making the network plan and identification of the Critical path, the project is controlled by checking progress against the schedule, assigning and scheduling manpower and equipment and analyzing the effects of delays. This is done by progress report from time to time and updating the network continuously. Arrow diagram and time charts are used for making periodic progress reports.

18.4  Basic Terminology used in Network Analysis

Network analysis is the general name given to certain specific techniques which can be used for the planning, management and control of projects. A fundamental method in both PERT and CPM is the use of network systems as a means of graphically depicting the current problems or proposed projects in network diagram. A network diagram is the first thing to sketch an arrow diagram which shows inter-dependencies and the precedence relationship among activities of the project. Before illustrating the network representation of a project, let us define some basic definitions:

18.4.1  Activity

Any individual operation, which utilizes resources and has a beginning and an end is called an activity. An arrow is used to depict an activity with its head indicating the direction of progress in the project. It is of four types:

1. a)Predecessor activity:activity that must be completed immediately prior to the start of another activity.
2. b)Successor activity:activity which cannot be started until one or more of other activities are completed but immediately succeed them are called successor activity.
3. c)Concurrent:  Activity which can be accomplished concurrently is known as concurrent activity. An activity can be predecessor or successor to an event or it may be concurrent with the one or more of the other activities.
4. d)Dummy activity:An activity which does not consume any kind of resources but merely depicts the technological dependence is called a dummy activity. Dummy activity is inserted in a network to classify the activity pattern in the following situations:
5. i)To make activities with common starting and finishing points distinguishable.
6. ii)To identify and maintain the proper precedence relationship between activities those are not connected by events.

Let�s consider a situation where A and B are concurrent activities and activity D is dependent on B and C is dependent on both A and B. Such a situation can be handled by use of dummy activity.

When two or more activities are exactly parallel such that they would start at the same node (event) and finish at the same node. A dummy would be inserted between the end of one of the activities and the common finishing node.

This is to ensure that each activity has a unique description when refer to by its start and finish node number. Dummy are often used to improve the layout of network. When they may not strictly necessary to represents the logic involved. This often happens at the start or finish of a network where a number of activities either start from a certain point or converge to particular point.

18.4.2  Event

The beginning and end points of an activity are called events or nodes or connector. This is usually represented by circle in a network.

 

Here, A is known as the activity.

The events can be further classified into three categories:

1. a)Merge Event: When two or more activities come from an event it is known as merge event.
2. b)Burst Event:When more than one activity leaves an event is known as burst event.
3. c)Merge & Burst Event:An activity may be merged and burst at the same time.

18.4.3  Difference between event and activity

An event is that particular instant of time at which some specific part of project is to be achieved while an activity is the actual performance of a task. An activity requires time and resources for its completion. Events are generally described by such words as complete, start, issue, approves, taste etc. while the word like design, process, test, develop, prepare etc. shows that a work is being accomplished and thus represent activity. While drawing networks, it is assumed that

1. a)The movement is from left to right and
2. b)Head event has a number higher than the tail event.

Thus the activity (i-j) always means that job which begins at event (i) is completed at event (j).

 

 

Network representation is based on the following two axioms.

1. a)  An event is not said to be complete until all the activities flowing into it are completed.
2. b)  No subsequent activities can begin until its tail event is reached or completed.

2.1 Introduction to CPM / PERT Techniques

 

CPM/PERT or Network Analysis as the technique is sometimes called, developed along two parallel streams, one industrial and the other military.

 

CPM (Critical Path Method) was the discovery of M.R.Walker of E.I.Du Pont de Nemours & Co. and J.E.Kelly of Remington Rand, circa 1957. The computation was designed for the UNIVAC-I computer. The first test was made in 1958, when CPM was applied to the construction of a new chemical plant. In March 1959, the method was applied to maintenance shut-down at the Du Pont works in Louisville, Kentucky. Unproductive time was reduced from 125 to 93 hours.

 

PERT (Project Evaluation and Review Technique) was devised in 1958 for the POLARIS missile program by the Program Evaluation Branch of the Special Projects office of the U.S.Navy, helped by the Lockheed Missile Systems division and the Consultant firm of Booz-Allen & Hamilton. The calculations were so arranged so that they could be carried out on the IBM Naval Ordinance Research Computer (NORC) at Dahlgren, Virginia.

 

 

The methods are essentially network-oriented techniques using the same principle. PERT and CPM are basically time-oriented methods in the sense that they both lead to determination of a time schedule for the project. The significant difference between two approaches is that the time estimates for the different activities in CPM were assumed to be deterministic while in PERT these are described probabilistically. These techniques are referred as project scheduling techniques.

 

 

In CPM activities are shown as a network of precedence relationships using activity-on- node network construction

• Single estimate of activity time

 

• Deterministic activity times

 

USED IN: Production management – for the jobs of repetitive in nature where the activity time estimates can be predicted with considerable certainty due to the existence of past experience.

In PERT activities are shown as a network of precedence relationships using activity-on- arrow network construction

• Multiple time estimates

 

• Probabilistic activity times

 

USED IN: Project management – for non-repetitive jobs (research and development work), where the time and cost estimates tend to be quite uncertain. This technique uses probabilistic time estimates.

Benefits of PERT/CPM

 

• Useful at many stages of project management

 

• Mathematically simple

 

 

• Give critical path and slack time

 

• Provide project documentation

 

• Useful in monitoring costs

 

Limitations of PERT/CPM

 

• Clearly defined, independent and stable activities

 

• Specified precedence relationships

 

• Over emphasis on critical paths

 

 

2.2   Applications of CPM / PERT

 

 

These methods have been applied to a wide variety of problems in industries and have found acceptance even in government organizations. These include

• Construction of a dam or a canal system in a region
• Construction of a building or highway
• Maintenance or overhaul of airplanes or oil refinery
• Space flight
• Cost control of a project using PERT / COST
• Designing a prototype of a machine
• Development of supersonic planes

 

2.3  Basic Steps in PERT / CPM

 

 

Project scheduling by PERT / CPM consists of four main steps

 

 

1.       Planning

 

• The planning phase is started by splitting the total project in to small projects. These smaller projects in turn are divided into activities and are analyzed by the department or
• The relationship of each activity with respect to other activities are defined and established and the corresponding responsibilities and the authority are also stated.
• Thus the possibility of overlooking any task necessary for the completion of the project is reduced

 

2.       Scheduling

• The ultimate objective of the scheduling phase is to prepare a time chart showing the start and finish times for each activity as well as its relationship to other activities of the
• Moreover the schedule must pinpoint the critical path activities which require special attention if the project is to be completed in
• For non-critical activities, the schedule must show the amount of slack or float times which can be used advantageously when such activities are delayed or when limited resources are to be utilized

 

3.       Allocation of resources

• Allocation of resources is performed to achieve the desired objective. A resource is a physical variable such as labour, finance, equipment and space which will impose a limitation on time for the
• When resources are limited and conflicting, demands are made for the same type of resources a systematic method for allocation of resources become
• Resource allocation usually incurs a compromise and the choice of this compromise depends on the judgment of

 

4.       Controlling

 

• The final phase in project management is controlling. Critical path methods facilitate the application of the principle of management by expectation to identify areas that are critical to the completion of the
• By having progress reports from time to time and updating the network continuously, a better financial as well as technical control over the project is exercised.
• Arrow diagrams and time charts are used for making periodic progress reports. If required, a new course of action is determined for the remaining portion of the project.

 

 

2.4   The Framework for PERT and CPM

 

Essentially, there are six steps which are common to both the techniques. The procedure is listed below:

 

1. Define the Project and all of its significant activities or tasks. The Project (made

up of several tasks) should have only a single start activity and a single finish activity.

 

1. Develop the relationships among the activities. Decide which activities must precede and which must follow

 

• Draw the “Network” connecting all the activities. Each Activity should have unique event numbers. Dummy arrows are used where required to avoid giving the same numbering to two

 

1. Assign time and/or cost estimates to each activity

 

1. Compute the longest time path through the network. This is called the critical path.

 

 

1. Use the Network to help plan, schedule, and monitor and control the

 

The Key Concept used by CPM/PERT is that a small set of activities, which make up the longest path through the activity network control the entire project. If these “critical” activities could be identified and assigned to responsible persons, management resources could be optimally used by concentrating on the few activities which determine the fate of the entire project.

 

Non-critical activities can be replanned, rescheduled and resources for them can be reallocated flexibly, without affecting the whole project.

 

Five useful questions to ask when preparing an activity network are:

 

• Is this a Start Activity?
• Is this a Finish Activity?
• What Activity Precedes this?
• What Activity Follows this?
• What Activity is Concurrent with this?

 

2.5  Network Diagram Representation

 

 

In a network representation of a project certain definitions are used

 

 

1.  Activity

Any individual operation which utilizes resources and has an end and a beginning is called activity. An arrow is commonly used to represent an activity with its head indicating the direction of progress in the project. These are classified into four categories

1. Predecessor activity – Activities that must be completed immediately prior to the start of another activity are called predecessor

 

 

2. Successor activity – Activities that cannot be started until one or more of other activities are completed but immediately succeed them are called successor activities.
3. Concurrent activity – Activities which can be accomplished concurrently are known as concurrent activities. It may be noted that an activity can be a predecessor or a successor to an event or it may be concurrent with one or more of other
4. Dummy activity – An activity which does not consume any kind of resource but merely depicts the technological dependence is called a dummy

 

The dummy activity is inserted in the network to clarify the activity pattern in the following two situations

• To make activities with common starting and finishing points distinguishable
• To identify and maintain the proper precedence relationship between activities that is not connected by

For example, consider a situation where A and B are concurrent activities. C is dependent on A and D is dependent on A and B both. Such a situation can be handled by using a dummy activity as shown in the figure.

2.  Event

An event represents a point in time signifying the completion of some activities and the beginning of new ones. This is usually represented by a circle in a network which is also called a node or connector.

The events are classified in to three categories

1. Merge event – When more than one activity comes and joins an event such an event is known as merge event.

 

 

2. Burst event – When more than one activity leaves an event such an event is known as burst
3. Merge and Burst event – An activity may be merge and burst event at the same time as with respect to some activities it can be a merge event and with respect to some other activities it may be a burst

 

 

3.  Sequencing

The first prerequisite in the development of network is to maintain the precedence relationships. In order to make a network, the following points should be taken into considerations

• What job or jobs precede it?
• What job or jobs could run concurrently?
• What job or jobs follow it?
• What controls the start and finish of a job?

Since all further calculations are based on the network, it is necessary that a network be drawn with full care.

2.6   Rules for Drawing Network Diagram

 

 

Rule 1

Each activity is represented by one and only one arrow in the network

 

 

Rule 2

No two activities can be identified by the same end events

 

 

Rule 3

In order to ensure the correct precedence relationship in the arrow diagram, following questions must be checked whenever any activity is added to the network

• What activity must be completed immediately before this activity can start?
• What activities must follow this activity?
• What activities must occur simultaneously with this activity?

 

In case of large network, it is essential that certain good habits be practiced to draw an easy to follow network

• Try to avoid arrows which cross each other
• Use straight arrows
• Do not attempt to represent duration of activity by its arrow length
• Use arrows from left to right. Avoid mixing two directions, vertical and standing arrows may be used if
• Use dummies freely in rough draft but final network should not have any redundant
• The network has only one entry point called start event and one point of emergence called the end event.

 

2.7   Common Errors in Drawing Networks

 

 

 

The three types of errors are most commonly observed in drawing network diagrams

 

 

1.  Dangling

To disconnect an activity before the completion of all activities in a network diagram is known as dangling. As shown in the figure activities (5 – 10) and (6 – 7) are not the last activities in the network. So the diagram is wrong and indicates the error of dangling

 

 

 

2.  Looping or Cycling

Looping error is also known as cycling error in a network diagram. Drawing an endless loop in a network is known as error of looping as shown in the following figure.

 

 

3.  Redundancy

 

 

Unnecessarily inserting the dummy activity in network logic is known as the error of redundancy as shown in the following diagram

 

 

 

2.8   Advantages and Disadvantages

 

PERT/CPM has the following advantages

 

• A PERT/CPM chart explicitly defines and makes visible dependencies (precedence relationships) between the elements,

 

• PERT/CPM facilitates identification of the critical path and makes this visible,

 

• PERT/CPM facilitates identification of early start, late start, and slack for each activity,

 

• PERT/CPM provides for potentially reduced project duration due to better understanding of dependencies leading to improved overlapping of activities and tasks where

 

 

PERT/CPM has the following disadvantages:

 

• There can be potentially hundreds or thousands of activities and individual dependency relationships,

 

• The network charts tend to be large and unwieldy requiring several pages to print and requiring special size paper,

 

• The lack of a timeframe on most PERT/CPM charts makes it harder to show status although colours can help (e.g., specific colour for completed nodes),

 

• When the PERT/CPM charts become unwieldy, they are no longer used to manage the

 

 

 

 

2.9   Critical Path in Network Analysis

 

 

Basic Scheduling Computations

 

 

The notations used are

(i, j) = Activity with tail event i and head event j E_i = Earliest occurrence time of event i

L_j = Latest allowable occurrence time of event j D_ij = Estimated completion time of activity (i, j) (Es)_ij = Earliest starting time of activity (i, j) (Ef)_ij = Earliest finishing time of activity (i, j) (Ls)_ij = Latest starting time of activity (i, j) (Lf)_ij = Latest finishing time of activity (i, j)

 

The procedure is as follows

 

 

1.       Determination of Earliest time (E_j): Forward Pass computation

 

• Step 1

The computation begins from the start node and move towards the end node. For easiness, the forward pass computation starts by assuming the earliest occurrence time of zero for the initial project event.

 

·         Step 2

1. Earliest starting time of activity (i, j) is the earliest event time of the tail end event i.e. (Es)_ij = E_i
2. Earliest finish time of activity (i, j) is the earliest starting time + the activity time i.e. (Ef)_ij = (Es)_ij + D_ij or (Ef)_ij = E_i + D_ij

 

 

• Earliest event time for event j is the maximum of the earliest finish times of all activities ending in to that event i.e. E_j = max [(Ef)_ij for all immediate predecessor of (i, j)] or E_j =max [E_i + D_ij]

 

2.       Backward Pass computation (for latest allowable time)

 

 

• Step 1

For ending event assume E = L. Remember that all E’s have been computed by forward pass computations.

 

·         Step 2

Latest finish time for activity (i, j) is equal to the latest event time of event j i.e. (Lf)_ij = L_j

 

·         Step 3

Latest starting time of activity (i, j) = the latest completion time of (i, j) – the activity time or (Ls)_ij =(Lf)_ij – D_ij or (Ls)_ij = L_j – D_ij

 

·         Step 4

Latest event time for event ‘i’ is the minimum of the latest start time of all activities originating from that event i.e. L_i = min [(Ls)_ij for all immediate successor of (i, j)] = min [(Lf)_ij – D_ij] = min [L_j – D_ij]

 

3.       Determination of floats and slack times

 

 

There are three kinds of floats

 

• Total float – The amount of time by which the completion of an activity could be delayed beyond the earliest expected completion time without affecting the overall project duration

Mathematically

(Tf)_ij = (Latest start – Earliest start) for activity ( i – j) (Tf)_ij = (Ls)_ij – (Es)_ij or (Tf)_ij = (L_j – D_ij) – E_i

 

• Free float – The time by which the completion of an activity can be delayed beyond the earliest finish time without affecting the earliest start of a subsequent activity.

Mathematically

(Ff)_ij = (Earliest time for event j – Earliest time for event i) – Activity time for ( i,

j)

(Ff)_ij = (E_j – E_i) – D_ij

 

• Independent float – The amount of time by which the start of an activity can be delayed without effecting the earliest start time of any immediately following activities, assuming that the preceding activity has finished at its latest finish

Mathematically

(If)_ij = (E_j – L_i) – D_ij

The negative independent float is always taken as zero.

 

 

• Event slack – It is defined as the difference between the latest event and earliest event

Mathematically

Head event slack = L_j – E_j, Tail event slack = L_i – E_i

 

4.       Determination of critical path

 

• Critical event – The events with zero slack times are called critical events. In other words the event i is said to be critical if E_i = L_i

 

• Critical activity – The activities with zero total float are known as critical activities. In other words an activity is said to be critical if a delay in its start will cause a further delay in the completion date of the entire

 

• Critical path – The sequence of critical activities in a network is called critical path. The critical path is the longest path in the network from the starting event to ending event and defines the minimum time required to complete the

Exercise

1. What is PERT and CPM?

 

2. What are the advantages of using PERT/CPM?

 

3. Mention the applications of PERT/CPM

 

4. Explain the following terms

 

1. Earliest time

 

1. Latest time

 

1. Total activity slack

 

1. Event slack

 

1. Critical path

 

5. Explain the CPM in network

 

6. What are the rules for drawing network diagram? Also mention the common errors that occur in drawing
7. What is the difference between PERT and CPM/

 

 

8. What are the uses of PERT and CPM?

 

9. Explain the basic steps in PERT/CPM

 

10. Write the framework of PERT/CPM.

 

 

 

 

 

 

 

 

 

 

 

Unit 3

• Worked Examples on CPM
• PERT
• Worked Examples

 

 

3.1  Worked Examples on CPM

 

 

Example 1

Determine the early start and late start in respect of all node points and identify critical path for the following network.

 

 

 

 

 

Solution

Calculation of E and L for each node is shown in the network

 

 

 

 

Activity(i, j)	Normal Time (Dij)	Earliest Time		Latest Time		Float Time (Li – Dij ) – Ei
		Start (Ei)	Finish (Ei + Dij )	Start (Li – Dij )	Finish (Li)
(1, 2)	10	0	10	0	10	0
(1, 3)	8	0	8	1	9	1
(1, 4)	9	0	9	1	10	1
(2, 5)	8	10	18	10	18	0
(4, 6)	7	9	16	10	17	1

 

 

(3, 7) (5, 7) (6, 7) (5, 8) (6, 9) (7, 10) (8, 10) (9, 10)

16 7 7 6 5 12 13 15

8 18 16 18 16 25 24 21

24 25 23 24 21 37 37 36

9 18 18 18 17 25 24 22

25 25 25 24 22 37 37 37

1 0 2 0 1 0 0 1

Network Analysis Table

 

 

From the table, the critical nodes are (1, 2), (2, 5), (5, 7), (5, 8), (7, 10) and (8, 10)

 

 

From the table, there are two possible critical paths i.       1 → 2 → 5 → 8 → 10

1. 1 → 2 → 5 → 7 → 10

 

 

Example 2

Find the critical path and calculate the slack time for the following network

 

 

 

 

Solution

 

 

The earliest time and the latest time are obtained below

 

 

Activity(i, j)	Normal Time (Dij)	Earliest Time		Latest Time		Float Time (Li – Dij ) – Ei
		Start (Ei)	Finish (Ei + Dij )	Start (Li – Dij )	Finish (Li)
(1, 2)	2	0	2	5	7	5
(1, 3)	2	0	2	0	2	0
(1, 4)	1	0	1	6	7	6
(2, 6)	4	2	6	7	11	5
(3, 7)	5	2	7	3	8	1
(3, 5)	8	2	10	2	10	0
(4, 5)	3	1	4	7	10	6
(5, 9)	5	10	15	10	15	0
(6, 8)	1	6	7	11	12	5
(7, 8)	4	7	11	8	12	1
(8, 9)	3	11	14	12	15	1

 

From the above table, the critical nodes are the activities (1, 3), (3, 5) and (5, 9)

 

 

 

 

The critical path is 1 → 3 → 5 → 9

 

 

Example 3

A project has the following times schedule

 

 

Activity	Times in weeks	Activity	Times in weeks
(1 – 2) (1 – 3) (2 – 4) (3 – 4) (3 – 5) (4 – 9) (5 – 6)	4 1 1 1 6 5 4	(5 – 7) (6 – 8) (7 – 8) (8 – 9) (8 – 10) (9 – 10)	8 1 2 1 8 7

 

Construct the network and compute

1. T_E and T_L for each event
2. Float for each activity
3. Critical path and its duration

 

 

Solution

 

 

The network is

 

 

 

 

Event No.:	1	2	3	4	5	6	7	8	9	10
TE:	0	4	1	5	7	11	15	17	18	25
TL:	0	12	1	13	7	16	15	17	18	25

 

 

Float = T_L (Head event) – T_E (Tail event) – Duration

 

 

Activity	Duration	TE (Tail event)	TL (Head event)	Float
(1 – 2) (1 – 3) (2 – 4) (3 – 4) (3 – 5) (4 – 9) (5 – 6) (5 – 7) (6 – 8) (7 – 8) (8 – 9) (8 – 10) (9 – 10)	4 1 1 1 6 5 4 8 1 2 1 8 7	0 0 4 1 1 5 7 7 11 15 17 17 18	12 1 13 13 7 18 16 15 17 17 18 25 25	8 0 8 11 0 8 5 0 5 0 0 0 0

 

The resultant network shows the critical path

 

 

 

The two critical paths are

1. 1 → 3 → 5 →7 → 8 → 9 →10
2. 1 → 3 → 5 → 7 → 8 →10

 

 

3.2   Project Evaluation and Review Technique (PERT)

 

 

The main objective in the analysis through PERT is to find out the completion for a particular event within specified date. The PERT approach takes into account the uncertainties. The three time values are associated with each activity

 

1. Optimistic time – It is the shortest possible time in which the activity can be finished. It assumes that every thing goes very well. This is denoted by t₀.
2. Most likely time – It is the estimate of the normal time the activity would take. This assumes normal delays. If a graph is plotted in the time of completion and the frequency of completion in that time period, then most likely time will represent the highest frequency of occurrence. This is denoted by t_m.
3. Pessimistic time – It represents the longest time the activity could take if everything goes As in optimistic estimate, this value may be such that

 

 

only one in hundred or one in twenty will take time longer than this value. This is denoted by t_p.

 

In PERT calculation, all values are used to obtain the percent expected value.

 

 

1. Expected time – It is the average time an activity will take if it were to be repeated on large number of times and is based on the assumption that the activity time follows Beta distribution, this is given by

t_e = ( t₀ + 4 t_m + t_p ) / 6

 

2. The variance for the activity is given by

σ² = [(t_p – t_o) / 6] ²

 

3.3  Worked Examples

Example 1

For the project

 

 

 

 

 

Task:	A	B	C	D	E	F	G	H	I	J	K
Least time:	4	5	8	2	4	6	8	5	3	5	6

 

 

Greatest time:	8	10	12	7	10	15	16	9	7	11	13
Most likely time:	5	7	11	3	7	9	12	6	5	8	9

 

 

 

Find the earliest and latest expected time to each event and also critical path in the network.

Solution

 

Task	Least time(t0)	Greatest time (tp)	Most likely time (tm)	Expected time (to + tp + 4tm)/6
A B C D E F G H I J K	4 5 8 2 4 6 8 5 3 5 6	8 10 12 7 10 15 16 9 7 11 13	5 7 11 3 7 9 12 6 5 8 9	5.33 7.17 10.67 3.5 7 9.5 12 6.33 5 8 9.17

 

 

Task	Expected time (te)	Start		Finish		Total float
		Earliest	Latest	Earliest	Latest
A B C D E	5.33 7.17 10.67 3.5 7	0 0 5.33 0 16	0 8.83 5.33 10 16	5.33 7.17 16 3.5 23	5.33 16 16 13.5 23	0 8.83 0 10 0

 

 

F G H I J K

9.5 12 6.33 5 8 9.17

3.5 3.5 23 23 28 29.33

13.5 18.5 23 25.5 30.5 29.33

13 15.5 29.33 28 36 31.5

23 30.5 29.33 30.5 38.5 38.5

10 15 0 2.5 2.5 0

 

The network is

 

 

 

The critical path is A →C →E → H → K

 

 

Example 2

A project has the following characteristics

 

Activity	Most optimistic time (a)	Most pessimistic time (b)	Most likely time (m)
(1 – 2) (2 – 3) (2 – 4)	1 1 1	5 3 5	1.5 2 3

 

 

(3 – 5) (4 – 5) (4 – 6) (5 – 7) (6 – 7) (7 – 8) (7 – 9) (8 – 10) (9 – 10)

3 2 3 4 6 2 5 1 3

5 4 7 6 8 6 8 3 7

4 3 5 5 7 4 6 2 5

Construct a PERT network. Find the critical path and variance for each event.

 

Solution

 

Activity	(a)	(b)	(m)	(4m)	te (a + b + 4m)/6	v [(b – a) / 6]2
(1 – 2) (2 – 3) (2 – 4) (3 – 5) (4 – 5) (4 – 6) (5 – 7) (6 – 7) (7 – 8) (7 – 9) (8 – 10) (9 – 10)	1 1 1 3 2 3 4 6 2 5 1 3	5 3 5 5 4 7 6 8 6 8 3 7	1.5 2 3 4 3 5 5 7 4 6 2 5	6 8 12 16 12 20 20 28 16 24 8 20	2 2 3 4 3 5 5 7 4 6.17 2 5	4/9 1/9 4/9 1/9 1/9 4/9 1/9 1/9 4/9 1/4 1/9 4/9

 

 

The network is constructed as shown below

 

 

 

 

 

The critical path = 1 → 2 → 4 → 6 → 7 →9 →10

 

Example 3

 

Calculate the variance and the expected time for each activity

 

 

Solution

 

Activity	(to)	(tm)	(tp)	te (to + tp + 4tm)/6	v [(tp – to) / 6]2
(1 – 2) (1 – 3) (1 – 4)	3 6 7	6 7 9	10 12 12	6.2 7.7 9.2	1.36 1.00 0.69

 

 

(2 – 3) (2 – 5) (3 – 6) (4 – 7) (5 – 8) (6 – 7) (6 – 9) (8 – 9) (7 – 10) (9 – 11) (10 – 11)

0 8 10 8 12 8 13 4 10 6 10

0 12 12 13 14 9 16 7 13 8 12

0 17 15 19 15 10 19 10 17 12 14

0.0 12.2 12.2 13.2 13.9 9.0 16.0 7.0 13.2 8.4 12.0

0.00 2.25 0.69 3.36 0.25 0.11 1.00 1.00 1.36 1.00 0.66

 

 

Example 4

 

A project is represented by the network as shown below and has the following data

 

 

 

Task:	A	B	C	D	E	F	G	H	I
Least time:	5	18	26	16	15	6	7	7	3

 

 

Greatest time:	10	22	40	20	25	12	12	9	5
Most likely time:	15	20	33	18	20	9	10	8	4

 

Determine the following

 

1. Expected task time and their variance

 

2. Earliest and latest time

 

 

 

Solution

 

 

 

 

 

 

 

 

 

1.

 

Activity	Least time (t0)	Greatest time (tp)	Most likely time (tm)	Expected time (to + tp + 4tm)/6	Variance (σ2)
(1-2) (1-3) (1-4) (2-5) (2-6) (3-6) (4-7) (5-7) (6-7)	5 18 26 16 15 6 7 7 3	10 22 40 20 25 12 12 9 5	8 20 33 18 20 9 10 8 4	7.8 20.0 33.0 18.0 20.0 9.0 9.8 8.0 4.0	0.69 0.44 5.43 0.44 2.78 1.00 0.69 0.11 0.11

 

 

 

 

2.

 

Earliest time

 

E₁ = 0

 

E₂ = 0 +7.8 = 7.8

 

E₃ = 0 +20 = 20

 

E₄ = 0 +33 = 33

 

E₅ = 7.8 + 18 = 25.8

 

E₆ = max [7.8 + 20, 20 + 9] = 29

 

E₇ = max [33 + 9.8, 25.8 + 8, 29 + 4] = 42.8

 

Latest time

 

L₇ = 42.8

 

L₆ = 42.8 – 4 = 38.8

 

L₅ = 42.8 – 8 = 34.3

 

L₄ = 42.8 – 9.8 = 33

 

L₃ = 38.8 – 9 = 29.8

 

L₂ = min [34.8 – 18, 38.8 – 20] = 16.8

 

L₁ = min [16.8 – 7.8, 29.8 – 20, 33 – 33] = 0

 

 

 

Exercise

 

 

1. What is PERT?

 

2. For the following data, draw network. Find the critical path, slack time after calculating the earliest expected time and the latest allowable time

 

 

 

Activity	Duration	Activity	Duration
(1 – 2) (1 – 3) (2 – 4) (2 – 5) (2 – 6) (3– 7) (3 – 8) (4 – 9)	5 8 6 4 4 5 3 1	(5 – 9) (6 – 10) (7 – 10) (8 – 11) (9 – 12) (10 – 12) (11 – 13) (12 – 13)	3 5 4 9 2 4 1 7

 

[Ans. Critical path: 1 → 3 → 7 → 10 → 12 →13]

 

3. A project schedule has the following characteristics

 

Activity	Most optimistic time	Most likely time	Most pessimistic time
(1 – 2) (2 – 3) (2 – 4) (3 – 5) (4 – 5) (4 – 6) (5 – 7) (6 – 7) (7 – 8)	1 1 1 3 2 3 4 6 2	2 2 3 4 5 5 5 7 4	3 3 5 5 4 7 6 8 6

 

 

(7 – 9) (8 – 10) (9 – 10)

4 1 3

6 2 5

8 3 7

 

 

Construct a PERT network and find out

1. The earliest possible time
2. Latest allowable time
3. Slack values
4. Critical path

4. Explain the following terms
   1. optimistic time
   2. Most likely time
   3. Pessimistic time
   4. Expected time
   5. Variance
5. Calculate the variance and the expected time for each activity

 

 

 

 

UNIT-IV

Replacement Model:

Replacement of Items that deteriorate whose maintenance costs increase with time without change in the money value.

Replacement of items that fail suddenly:

individual replacement policy,

group replacement policy.

Inventory Models:

Models with deterministic demand model

(a) demand rate uniform and production rate infinite, model

(b) demand rate non-uniform and production rate infinite, model

(c) demand rate uniform and production rate finite.

      REPLACEMENT  MODELS

INTRODUCTION

The problem of replacement is felt when the job performing units such as men, machines, equipments, parts etc. become less effective or useless due to either sudden or gradual deterioration in their efficiency, failure or breakdown. By replacing them with new ones at frequent intervals, maintenance and other overhead costs can be reduced. However, such replacements would increase the need of capital cost for new ones.

For example,

1. A vehicle tends to wear out with time due to constant use. More money needs to be spent on it on account of increased repair and operating cost. A stage comes when it becomes uneconomical to maintain the vehicle and it is better to replace it with a new one. Here the replacement decision may be taken to balance the increasing maintenance cost with the decreasing money value of the vehicle as time
2. In case of highway tubelights where time of failure is not predictable for individual tubes, replacement is done only after individual failure. However, it may be economical to replace such tubes on a schedule basis before their failure. Here the replacement decision may be taken to balance between the wasted life of a tube before failure and cost incurred when a tube fails completely during

Thus, the basic problem in such situations is to formulate a replacement policy to determine an age (or period) at which the replacement of the given machinery/equipment is most economical keeping in view all possible alternatives.

In this chapter, we shall discuss the replacement policies in the context of the following three types of replacement situations:

1. Items such as machines, vehicles, tyres etc. whose efficiency deteriorates with age due to constant use and which need increased operating and maintenance costs. In such cases deterioration level is predictable and is represented by a. Increased maintenance/operational cost, its waste or scrap value and damage to item and safety risk.
2. Items such as light bulbs and tubes, electric motors, radio, television parts etc. which do not give any indication of deteriorations with time but fail all of a sudden and become completely useless. Such cases require an anticipation of failures to specify the probability of failure for any future time With this probability distribution and the cost information, it is desired to formulate optimal, replacement policy to balance the wasted life of an item replaced before failure against the costs incurred when the item fail in service.
3. The existing working staff in an organisation gradually reduces due to retirement, death, retrenchment and other

 

TYPES OF FAILURE

The term ‘failure’ here will be discussed in the context of replacement decisions. There are two types of failures: 1. Gradual failure and 2. Sudden failure.

Gradual Failure

Gradual Failure is progressive in nature. That is, as the life of an item increases its  operational efficiency also deteriorates resulting in

• increased running (maintenance and operating)
• decrease in its

 

• decrease in the resale or salvage

Mechanical items like pistons, rings, bearings etc., and automobile types fall under this category.

Sudden Failure

This type of failure occurs in items after some period of giving desired service rather than deterioration while in service. The period of desired service is not constant but follows some frequency distribution which may be progressive, retrogressive or random in nature.

1. Progressive Failure: If the probability of failure of an item increases with the increase in its life, then such failure is called progressive failure. For example, light bulbs and tubes fail progressively.
2. Retrogressive Failure: If the probability of failure in the beginning of the life of an item is more but as time passes the chances of its failure becomes less, then such failure is said to be
3. Random Failure: In this type of failure, the constant probability of failure is associated with items that fail from random cases such as physical shocks, not related to age. For example, vacuum tubes in air-born equipment have been found to fail at a rate independent of the age of the

 

REPLACEMENT OF ITEMS WHOSE EFFICIENCY DETERIORATES WITH TIME

When operational efficiency of an item deteriorates with time (gradual failure), it is economical to replace the same with a new one. For example, the maintenance cost of a machine increases with time and a stage is reached when it may not be economical to allow machine to continue in the system. Besides, there could be a number of alternative choices and one may like to compare available alternatives on the basis of the running costs (average maintenance and operating costs) involved. In this section, we shall discuss various techniques for making such comparisons under different conditions. While making such comparisons it is assumed that suitable expressions for running costs are available.

 

Model 1 Replacement Policy for items Whose Running Cost Increases with Time and Value of Money Remains Constant During a Period

Theorem 1

The cost of maintenance of a machine is given as a function increasing with time and its scrap value is constant.

1. If time is measured continuously, then the average annual cost will be minimised by replacing the machine when the average cost to date becomes equal to the current maintenance cost.
2. If time is measured in discrete units, then the average annual cost will be minimised by replacing the machine when the next period’s maintenance cost becomes greater than the current average

PROOF: The aim here is to determine the optimal replacement age of an equipment whose running cost increases with time and the value of money remains constant (i.e. value is not counted) during that period.

Let C = capital or purchase cost of new equipment

S = Scrap (or salvage) value of the equipment at the end of t years

 

R(t) = running cost of equipment for the year t n = replacement age of the equipment.

1. When time ‘t’ is a continuous variable: If the equipment is used for t years, then the total cost incurred over this period is given by

TC = Capital (or purchase) cost – Scrap value at the end of t years + Running cost for t years.

 

= C – S +

∫𝑛 𝑅(𝑡)𝑑𝑡

 

0

0

Therefore, the average cost per unit time incurred over the period of n years is:

 

ATCn  = 1

𝑛

C – S +

∫𝑛 𝑅(𝑡)𝑑𝑡

———————— (1)

 

 

To obtain optimal value n for which ATCn is minimum, differentiate ATCn with respect to n, and set the first derivative equal to zero. That is, for minimum of ATCn.

 

^𝑑 {ATC } = – ¹

 

{C – S} + 𝑅 (𝑛) – 1

 

^𝑛 (𝑡)𝑑𝑡 = 0

 

0

𝑑𝑛

n           𝑛2

𝑛             𝑛2 ∫0

 

or R (n) = ¹

𝑛

R (n) = ATCn

C – S +

∫𝑛 𝑅(𝑡)𝑑𝑡

, n≠0—————- (2)

 

Hence, the following replacement policy can be derived with help of Eq. 2.

Policy

Replace the equipment when the average annual cost for n years becomes equal to the current

/annual running cost. That is,

 

 

R (n) =

C – S +

∫𝑛 𝑅(𝑡)𝑑𝑡

 

 

0

𝑡=0

1. When time ‘t’ is a discrete variable: The average cost incurred over the period n is given by

 

ATCn  = 1

𝑛

C – S + ∑^𝑛

𝑅 (𝑡)

—————————-(3)

 

 

 

𝑡=0

If C – S and ∑^𝑛

𝑅 (𝑡)

are assumed to be monotonically decreasing and increasing

 

respectively, then there will exist a value of n for which ATCn is minimum. Thus we shall have inequalities

ATCn – 1 > ATCn < ATCn+1 or ATCn – 1 – ATCn > 0

and ATCn+1 – ATCn > 0

𝑡=1

𝑡=1

Eq. (3) for period n + 1, we get

 

ATCn = 1

𝑛+1

C – S + ∑^𝑛=0 𝑅 (𝑡)     =

C – S + ∑^𝑛=0 𝑅 (𝑡) + R (n + 1)

 

 

 

𝑛 C − S + ∑𝑛 𝑅 (𝑡)

𝑅 (𝑛+1)                𝑛

𝑅 (𝑛+1)

 

=                    𝑡=0                +

=         . ATCn +

 

𝑛+1                          𝑛

Therefore,

𝑛+1

𝑛+1

𝑛+1

 

ATCn+1 – ATCn = 𝑛

ATCn + 𝐴 (𝑛+1) – ATCn = 𝑅 (𝑛+1) + ATCn [

– 1] = 𝑅 (𝑛+1) – ATCn

 

𝑛+1

𝑛+1

𝑛+1

𝑛+1

𝑛+1

𝑛+1

 

Since ATCn+1 – ATCn > 0, we get

𝑅 (𝑛+1) – ATCn > 0

𝑛+1               𝑛+1

 

R (n + 1) – ATCn  > 0 or R (n + 1) > ATCn—————————————- (4)

Similarly,

ATCn – 1 – ATCn > 0, implies that R (n + 1) < ATCn – 1. This provides the following replacement policy.

 

𝑡=0

Policy 1: If the next year, running cost R(n + 1) is more than average cost of nth year, ATCn, then it is economical to replace at the end of n years. That is

 

R (n + 1) >  1

𝑛

C – S + ∑^𝑛

𝑅 (𝑡)

 

 

Policy 2: If the present year’s running cost is less than the previous year’s average cost, ATCn

– 1, then do not replace. That is

𝑡=0

R (n) <          C – S + ∑^𝑛−1 𝑅 (𝑡)

 

EXAMPLE

A firm is considering replacement of a machine, whose cost price is Rs. 12, 200 and scrap value is Rs. 200. The running (maintenance and operating) costs are found from experience to be as follows:

Year	1	2	3	4	5	6	7	8
Running cost (Rs.)	200	500	800	1200	1800	2500	3200	4000

When should the machine be replaced?

 

Solution: We are given the running cost, R(n), the scrape value S – Rs. 200 and the cost of the machine, C = Rs. 12, 200. In order to determine the optimal time n when the machine should be replaced, first we calculate average cost per year during the life of the machine as shown in table below:

TABLE

Year of Service n	Running Cost (Rs.) R(n)	Cumulative Running Cost (Rs.) Ʃ R(n)	Depreciation Cost (Rs.) C – S	Total Cost (Rs.) TC	Average Cost (Rs.) ATCn
1	2	3	4	5 = 3 + 4	6 = 5/1
1 2 3 4 5 6 7 8	200 500 800 1200 1800 2500 3200 4000	200 700 1500 2700 4500 7000 10200 14200	12000 12000 12000 12000 12000 12000 12000 12000	12, 200 12, 700 13, 500 14, 700 16, 500 19, 000 22, 200 26, 200	12, 200 6350 4500 3675 3300 3167 3171 3275

From the table, it may be noted that the average cost per year, ATCn is minimum in the sixth year (Rs. 3, 167). Also the average cost in the seventh year (Rs. 3171) is more than the cost in the sixth year. Hence, the machine should be replaced after every six years.

 

• The data collected in running a machine, the cost of which is 60, 000 are given below:

 

Year	1	2	3	4	5
Resale Value (Rs.)	42, 000	30, 000	20, 400	14, 400	9, 650
Cost of Spares (Rs.)	4, 000	4, 270	4, 880	5, 700	6, 800
Cost of Labour (Rs.)	14, 000	16, 000	18, 000	21, 000	25, 000

Determine the optimum period for replacement of the machine.

 

Solution: The costs of spares and labour together determine running (operational or maintenance) cost. Thus, the running costs and the resale price of the machine in successive years are as follows:

Year:	1	2	3	4	5
Resale Value (Rs.)	42, 000	30, 000	20, 400	14, 400	9, 650
Running Cost (Rs.)	18, 000	20, 270	22, 880	26, 700	31, 800

The calculations of average running cost per year during the life of the machine are shown in table 1.

Year of Service n	Running Cost (Rs.) R(n)	Cumulative Running Cost (Rs.) Ʃ R(n)	Resale Value (Rs.) S	Depreciation Cost (Rs.) C – S	Total Cost (Rs.) TC	Average Cost (Rs.) ATCn
1	2	3	4	5 = 60, 000	6 = 3 + 5	7 = 6/1
1 2 3 4 5	18, 000 20, 270 22, 880 26, 700 31, 800	18, 000 38, 270 61, 150 87, 850 1, 19, 650	42, 000 30, 000 20, 400 14, 400 9, 650	18, 000 30, 000 39, 600 45, 600 50, 350	36, 000 68, 270 1, 00, 750 1, 33, 450 1, 70, 000	36, 000.00 34, 135.00 33, 583.00 33, 362.00 34, 000.00

The calculations in table 1 reveal that the average cost is lowest during the fourth year. Hence, the machine should be replaced after every fourth year, otherwise the average cost per year for running the machine would start increasing.

 

REPLACEMENT OF ITEMS THAT FAIL COMPLETELY

It is somehow difficult to predict that a particular equipment will fail at a particular time. This uncertainty can be avoided by deriving the probability distribution of failures. Here, it is assumed that the failures occur only at the end of the period, say t. Thus, the objective becomes to find the value of t which minimises the total cost involved for the replacement.

 

Mortality Tables: These tables are used to derive the probability distribution of life span of an equipment in question. Let

M (f)                = Number of survivors at any time t M(t – 1)                            = Number of survivors at any time t – 1 N         = Initial number of equipments

Then the probability of failure during time period t is given by

P (t) = (𝑡−1)− 𝑀(𝑡)

𝑁

The probability that an equipment has survived to an age (t – 1). and will fail during the interval (t – 1) to t can be defined as the conditional probability of failure. It is given by

Pc (t) = (𝑡−1)− 𝑀(𝑡)

(𝑡−1)

 

The probability of survival to an age t is given by

Ps(t) = 𝑀(𝑡)

𝑁

Mortality Theorem 1: A large population is subject to a given mortality law for a very long period of time. All deaths are immediately replaced by births and there are no other entries or exits. Show that the age distribution ultimately becomes stable and that the number of deaths per unit time becomes constant and is equal to the size of the total population divided by the mean age at death.

Proof: Without any loss of generality, it is assumed that death (or failure) occurs just before the age of (k + 1) years, where k is an integer. That is, life span of an item lies between t = 0 and t = k. Let us define f(t) = number of births (replacements) at time t, and

p(x) = probability of death (failure) just before the age x + 1, i.e. failure at time x.

 

and ∑

𝑘

𝑥=0

(𝑥) = 1

 

If f(t – x) represents the number of births at time t – x, t = k, k +1, k + 2,….then the age of newly borns attain the age x at time t illustrated in the figure below:

 

Age	0	x		x + 1
Time	t – x		t	t + 1

 

Hence the expected number of deaths of such newly borns before reaching the time t + 1 (i.e. at time t) will be

𝑥=0

Expected number of death =  ∑^𝑘    𝑝(𝑥)f(t – x), t = k, k + 1, …..

Since all deaths (failures) at time t are replaced immediately by births (replacements) at time t

+ 1, expected number of births are:

𝑥=0

f(t + 1) = ∑^𝑘    𝑝(𝑥)f(t – x), t = k, k + 1, …..                                                              (1)

The solution to the difference Eq. (9) in t can be obtained by putting the value f(t) = Aα^‘, where A is some constant. Then Eq. (9) becomes

𝑥=0

Aα^{t + 1} = A ∑^𝑘     (𝑥) α^{t – x}                                                                                            (2)

𝑥=0

Dividing both sides of Eq. (10) by Aα^{t – k}, we get

 

α          ∑=

k + 1         𝑘

𝑥=0

(𝑥) α^{k – x} = α^k ∑^𝑘

(𝑥) α^{– x}

 

= α^k {p (0) + p (1) α^-1 + p(2) α^-2 + }

or α^{k + 1} – {p (0) α^k + p (1) α^{k – 1} + p (2) α^{k – 2}} = 0                                                                     (3) Equation (3) is of degree (k + 1) and will, therefore, have exactly (k + 1) roots. Let us denote the roots of Eq. (3) by α0, α1, α2, , αk.

For α = 1, the L. H. S of equation (3), becomes

L.H.S = 1 – {p(0) + p (1) + p (2) + + p (w)}

 

= 1 – ∑

𝑤

𝑥=0

(𝑥) = 0 R. H.S

 

Hence, one root of Eq. (3) is α = 1. Let us denote this root by α0. The general solution of Eq.

• will then be of the form

f (t) = A0  α^t0  + A1 α^t1 +      + Ak α^tk

= A0  + A1 α^t1 +      + Ak α^tk

where A0, A1, A2, …. Ak  are constant whose values are to be calculated.                              (4)

 

Since one of the roots of Eq. (3), α0 = 1 is positive, according to the Descrae’s sign rule all other roots α1, α2, , αk will be negative and their absolute value is less than unity, i.e. |αi| <

1, i = 1, 2, 3, ….., k. It follows that the value of these roots tends to be zero as t   ∞. With the result that Eq. (4) becomes f(t) = A0. This indicates that the number of deaths (as well as births) becomes constant at any time.

Now the problem is to determine the value of the constant A0. For this we can proceed as follows:

Let us define

g (x) = Probability of survival for more than x years.

or g (x) = 1 – Prob (survivor will die before attaining the age x)

= 1 – {p(0) + p(1) +     p(x -1)}

Obviously, it can be assumed that g(0) = 1.

Since the number of births as well as deaths has become constant and equal to A0, expected number of survivors of age x is given by A0 . g(x).

As deaths are immediately replaced by births, size N of the population remains constant. That is,

 

𝑥=0

N = A0 ∑𝑘

Or

A0 =      𝑁

(𝑥) α1, α2,…….. , αk

 

…………     (4)

 

∑

𝑘

𝑥=0

𝑔(𝑥)

 

The denominator in Eq. (4) represents the average age at death. This can also be proved as follows:

From finite differences, we know that

∆(x) = (x + 1) – x = 1

 

∑

𝑏

𝑥=𝑎

(𝑥) ∆ℎ(x) = f (b + 1) h(b + 1) – f (a) h(a) – ∑^𝑏

(𝑥 + 1) ∆𝑔(x)

 

𝑥=𝑎

𝑥=0

= g (k + 1) (k + 1) – g (0) . 0 – ∑^𝑘     (𝑥 + 1) ∆𝑔(x)

𝑥=0

= g (k + 1) (k + 1) – ∑^𝑘    (𝑥 + 1) ∆𝑔(x)…………… (5)

But g (k + 1) = 1 – {p(0) + p(1) + p(2) +          + p(k)} = 0

since no one can survive for more than (k + 1) years of age and

∆𝑔(x) = g(x + 1) – g(x)

= {1 – p(0) – p(1) – …… – p(x)} – {1 – p(0) – p(1)       p(x – 1)} = – p(x)

Substituting the value of g(k + 1) and ∆𝑔(x) in Eq. (5), we get

 

∑

𝑘

𝑥=0

𝑔(𝑥) = ∑^𝑘

(𝑥 + 1)p (x) = Mean age at death

 

𝑥=0

Hence from Eq. (4), we get

A0 =               𝑁                             .

𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑎𝑔𝑒 𝑎𝑡 𝑑𝑒𝑎𝑡ℎ

 

 

STAFFING PROBLEM

The principles of replacement may be applied to formulate some useful recruitment and promotion policies for the staff working in the organisation. For this, we assume that life distribution for the services of staff in the organisation is already known.

Example 1:

 

An airline requires 200 assistant hostesses, 300 hostesses and 50 supervisors. Women are recruited at the age of 21, and if still in service retire at 60. Given the following life table, determine

• How many women should be recruited in each year?
• At what age should promotion take place?

Airline Hostesses’ Life Record

Age No.    in Servie	21 1000	22 600	23 480	24 384	25 307	26 261	27 228	28 206
Age No.    in Servie	29 190	30 181	31 173	32 167	33 161	34 155	35 150	36 146
Age No.    in Servie	37 141	38 136	39 131	40 125	41 119	42 113	43 106	44 99
Age No.    in Servie	45 93	46 87	47 80	48 73	49 66	50 59	51 53	52 46
Age No.    in Servie	53 39	54 33	55 27	56 22	57 18	58 14	59 11	—

Solution: If 1000 women had been recruited each year for the past 39 years, then the total number of them recruited at the age of 21 and those serving upto the age of 59 is 6, 480. Total number of women recruited in the airline are: 200 + 300 + 50 = 550.

• Number of women to be recruited every year in order to maintain a strength of 55 hostesses 550 x (1000/6840) = 85 approx.
• If the assistant hostesses are promoted at the age of x, then up to age (x – 1), 200 assistant hostesses will be Among 550 women, 200 are assistant hostesses. Therefore, out of a strength of 1, 000 there will be: 200 x (1000/550) = 364 assistant hostesses. But, from the life table given in the question, this number is available upto the age of 24 years. Thus, the promotion of assistant hostesses is due in the 25th year.

Since out of 550 recruitments only 300 hostesses are needed, if 1, 000 girls are recruited, then only 1000 x (300/550) = 545 approx will be hostesses. Hence, total number of hostesses and assistant hostesses in a recruitment will be: 545 + 364 = 909. This means, only 1000 – 909 = 91 supervisors are required. But from life table this number is available up to the age of 46 years. Thus promotion of hostesses to supervisors will be due in 47th year.

 

QUESTIONS

1. In the theory of replacement models construct an equation for the cost of maintaining a system as a function of the control variable t (the number of periods between group replacements).
2. State some of the simple replacement policies and give the average cost functions for the same explaining your
3. The cost of maintenance of a machine is given as a function that the average annual cost will be minimised by replacing the machine when the average cost to date becomes equal to the current maintenance
4. Discuss the importance of replacement
5. Explain how the theory of replacement is used in the following

• Replacement of items whose maintenance cost varies with
• Replacement of items that fail

6. Find the cost per period of individual replacement of an installation of 300 lighting bulbs, given the following

(a) cost of replacing individual bulb is Rs. 3

(b) Conditional probability of failure is given below:
Week Number                                                 :		0	1	2	3	4
Conditional Probability of Failure                   :		0	1/10	1/3	2/3	1
7. The following mortality rates have been observed for a special type of light bulbs.
Month                                                 :	1	2	3	4	5
% failing at the end of the month       :	10	25	50	80	100

In an industrial unit there are 1,000 special type of bulbs in use, and it costs Rs.10 to replace an individual bulb which has burnt out. If all bulbs were replaced simultaneously it would cost Rs. per bulb. It is proposed to replace all bulbs at fixed intervals, whether or not they have burnt out, and to continue replacing burnt out bulbs as they fail. At what intervals of time should the manager replace all the bulbs?

8. An airline, whose staff are subject to the same survival rates as in the previous problem, currently has a staff whose ages are distributed in the following table. It is estimated that for the next two years staff requirements will increase by 10% per If women are to be recruited at the age of 21, how many should be recruited for the next year and at what age will promotions take place? How many should be recruited for the following year and at what age will promotions take place?

 

Assistant Age Number	21 90	22 50	23 30	24 20	25 10		(Total 200)
Hostesses	26	27	28	29	30	31	32	33	34
Age	40	35	35	30	28	26	20	18	16
Number
Age	35	36	37	38	39	40	41
Number	12	10	8	—	8	8	6
							(Total
							300)
Supervisors
Age	42	43	44	45	46	47	48	49	50
Number	5	4	5	3	3	3	6	2	—
Age	51	52	53	54	55	56	57	58	59
Number	—	4	3	5	—	3	2	—	2
									(Total
									50)

 

 

 

 

 

INVENTORY MODELS

 

INTRODUCTION

Inventory is one of the most expensive and important assets of many companies, representing as much as 50% of total invested capital. Managers have long recognised that good inventory control is crucial. On one hand, a firm can try to reduce costs by reducing on-hand inventory levels. On the other hand, customers become dissatisfied when frequent inventory outages, called stock outs occur. Thus, companies must make the balance between low and high inventory levels. As you would expect, cost minimisation is the major factor in obtaining this delicate balance.

Inventory is any stored resource that is used to satisfy a current or future need. Raw materials, work-in-progress, and finished goods are examples of inventory. Inventory levels for finished goods, such as clothes dryers, are a direct function of market demand. By using this demand information, it is possible to determine how much raw materials (eg., sheet metal, paint, and electric motors in the case of clothes dryers) and work-in-processes are needed to produce the finished product.

Every organisation has some type of inventory planning and control system. A bank has methods to control its inventory of cash. A hospital has methods to control blood supplies and other important items. State and federal governments, schools, and virtually every manufacturing and production organisation are concerned with inventory planning and control. Studying how organisations control their inventory is equivalent to studying how they achieve their objectives by supplying goods and services to their customers. Inventory is the common thread that ties all the functions and departments of the organisation together.

Figure 4.1 illustrates the basic components of inventory planning and control system. The planning phase involves primarily what inventory is to be stocked and how it is to  be acquired (whether it is to be manufactured or purchased). This information is then used in forecasting the demand for the inventory and in controlling inventory levels. The feedback loop in figure 4.1 provides a way of revising the plan and forecast based on experiences and observation.

Through inventory planning, an organisation determines what goods and/or services are to be produced. In cases of physical products, the organisation must also determine whether to produce these goods or to purchase them from another manufacturer. When this has been determined, the next step is to forecast the demand. Many mathematical techniques can be used in forecasting demand for a particular product. The emphasis in this chapter is on inventory control – that is, how to maintain adequate inventory levels within an organisation to support a production or procurement plan that will satisfy the forecasted demand.

In this chapter, we discuss several different inventory control models that are commonly used in practice. For each model, we provide examples of how they are analysed. Although we show the equations needed to compute the relevant parameters for each model, we use EXCEL worksheets to actually calculate these values.

 

IMPORTANCE OF INVENTORY CONTROL

Inventory control serves several important functions and adds a great deal of flexibility to the operation of a firm. Five main uses of inventory are as follows:

1. Decoupling function
2. Storing resources

 

3. Irregular supply and demand
4. Quantity discounts
5. Avoiding stockouts and

Figure 4.1 Inventory Planning and Control

 

 

 

Planning on what inventory to Stock and how to acquire it.

Forecasting Parts/Product Demand

Controlling Inventory Levels

 

 

 

 

 

Feedback Measurements to revise Plans and Forecasts

 

 

1.  Decoupling Function

One of the major functions of the inventory is to decouple manufacturing processes within the organisation. If a company did not store inventory, there could be many delays and inefficiencies. For example, when one manufacturing activity has to be completed before a second activity can be started, it could stop the entire process. However, stored inventory between processes could act as a buffer.

2.  Storing Resources

Agricultural and seafood products often have definite seasons over which they can be harvested or caught, but the demand for these products is somewhat constant during the year. In these and similar cases, inventory could be used to store these resources.

In manufacturing process, raw materials can be stored by themselves, as work-in-process, or as finished products. Thus, if your company makes lawn movers, you may obtain  lawn mower tyres from another manufacturer. If you have 400 finished lawn movers and 300 tyres in inventory, you actually have 1, 900 tyres stored in inventory. 300 tyres are stored by themselves, and 1, 600 ( = 4 tyre per lawn mower X 400 lawn movers) tyres are stored on the finished lawn mowers. In the same sense, labour can be stored in inventory. If you have 500 subassemblies and it takes 50 hours of labour to produce each assembly, you actually have 25, 000 labour hours stored in inventory in the subassemblies. In general, any resource, physical or otherwise can be stored in inventory.

3.  Irregular supply and demand

When the supply and demand for the inventory item is irregular, storing certain amount as inventory can be important. If the greatest demand for Diet-Delight beverage is during the summer, the Diet-Delight company will have to make sure that there is enough supply to meet this irregular demand. This might require that the company produce more of the soft drink in the winter than is actually needed in order to meet the winter demand. The inventory levels of Diet-Delight will gradually build up over the winter, but this inventory will be needed in summer. The same is true for irregular supplies.

 

4.  Quantity Discounts

Another use of inventory is to take advantage of quantity discounts. Many suppliers offer discounts for larger orders. For example, an electric jigsaw might normally cost $10 per unit. If you order 300 or more saws at one time, your supplier may lower the cost to $8.75. Purchasing in larger quantities can substantially reduce the cost of products. There are, however, some disadvantages of buying in larger quantities. You will have higher storage costs and higher costs due to spoilage, damaged stock, theft, insurance, and so on. Furthermore, if you invest in more inventory, you will have less cash to invest elsewhere.

5.  Avoiding stockouts and shortages

Another important function in inventory is to avoid stockouts and shortages. If a company is repeatedly out of stock, customers are likely to go elsewhere to satisfy their needs. Lost goodwill can be an expensive price to pay for not having the right item at the right time.

 

INVENTORY CONTROL DECISIONS

Even though there are literally millions of different types of products manufactured in our society, there are only two fundamental decisions that you have to make when controlling inventory:

1. How much to order
2. When to order

Table 4.1 Inventory Cost Factors

Operating Cost Factors	Carrying Cost Factors
Developing and sending purchase orders Processing and inspecting incoming inventory Bill Paying Inventory Inquiries Utilities, phone bills, and so on for the purchasing department Salaries and wages for purchasing department employees Supplies such as forms and paper for the purchasing department	Cost of Capital Taxes Insurance Spoilage Theft Obsolescence Salaries and wages for warehouse employees Utilities and building costs for the warehouse Supplies such as forms and papers for the warehouse

The purpose of all inventory models is to determine  how much to order and when to order. As you know, inventory fulfils many important functions in an organisation. But as the inventory levels go up to provide these functions, the cost of holding and storing inventories also increases. Thus, we must reach a fine balance in establishing inventory levels. A major objective in controlling inventory is to minimise total inventory costs. Some of the most significant inventory costs are as follows:

1. Cost of the items
2. Cost of ordering
3. Cost of carrying or holding inventory
4. Cost of stockouts
5. Cost of safety stock, the additional inventory that may be held to help avoid

 

The inventory models discussed in the first part of this chapter assume that demand and the time it takes to receive an order are known and constant, and that no quantity discounts are given. When this is the case, the most significant costs are the cost of placing an order and the cost of holding inventory items over a period of time. Table 4.1 provides a list of important factors that make up these costs.

 

ECONOMIC ORDER QUANTITY: DETERMINING HOW MUCH TO ORDER

The Economic Order Quantity (EOQ) model is one of the oldest and most commonly known inventory control techniques. Research on its use dates back to a 1915 publication by Ford

1. Harris. This model is still used by a large number of organisations today. This technique is relatively easy to use, but it makes a number of assumptions. Some of the more important assumptions are as follows:

 

ASSUMPTIONS OF EOQ

1. Demand is known and
2. The lead time – that is, the time between the placement of the order and the receipt of the order – is known and
3. The receipt of inventory is In other words, the inventory from an order arrives in one batch, at one point in time.
4. Quantity discounts are not
5. The only variable costs are the cost of placing an order, ordering cost, and the cost of holding or storing inventory over time, carrying or holding
6. If orders are placed at the right time, stockouts and shortages can be completely avoided. With these assumptions, inventory usage has a sawtooth shape, as in Figure 4.2. Here, Q represents the amount that is If this amount is 500 units, all 500 units are arrived at one time when an order is received. Thus, the inventory level jumps from 0 to 500 units. In general, the inventory level increases from 0 to Q units when an order arrives.

Because demand is constant over time, inventory drops at a uniform rate over time. Another order is placed such that when the inventory level reaches 0, the new order is received and the inventory level again jumps to Q units, represented by the vertical lines. This process continues indefinitely over time.

 

 

 

ORDERING AND INVENTORY COSTS

The objective of most inventory models is to minimise the total cost. With the assumptions just given, the significant costs are the ordering costs and inventory carrying cost. All other costs, such as the cost of the inventory itself, are constant. Thus, if we minimise the sum of the ordering and carrying costs, we also minimise the total cost.

To help visualise this, Figure 4.3 graphs total cost as a function of the order quantity, Q. As the value of Q increases, the total number of orders placed per year decreases. Hence, the total ordering cost decreases. However as the value of Q increases, the carrying cost increases because the firm has to maintain larger average inventories.

The optimal order size, Q^*, is the quantity that minimises the total cost. Note in figure 12.3 that Q^* occurs at the point where the ordering cost curve and the carrying cost curve intersect. This is not by chance. With this particular type of cost function, the optimal quantity always occurs at a point where the ordering cost is equal to the carrying cost.

Figure 12.2 Inventory Usage Over time

 

 

Inventory Level

Q

Maximum

 

 

 

 

 

 

 

 

 

 

 

 

 

Time

 

Figure 4.3 Total Cost as a Function of Order Quantity

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Optimal Order Quantity (Q^*)                        Order Quantity in Units

Now that we have a better understanding of inventory costs, let us see how we can determine the value of Q^* that minimises the total cost. In determining the annual carrying cost, it is convenient to use the average inventory. Referring to figure 4.2, we see that the on-hand inventory ranges from a high of Q units to a low of zero units, with a uniform rate of decrease between these levels. Thus, the average inventory can be calculated as the average of the minimum and maximum inventory levels. That is,

Average Inventory = (0 +Q)/2 = Q/2————————— (1)

We multiply this average inventory by a factor called the annual inventory carrying cost per unit to determine the annual inventory cost.

 

FINDING THE ECONOMIC ORDER QUANTITY

We pointed out that the optimal order quantity, Q^*, is the point that minimises the total cost, where total cost is the sum of ordering cost and carrying cost. We also indicated graphically that the optimal order quantity was at the point where the ordering cost was equal to the carrying cost. Let us now define the following parameters:

Q^* = Optimal Order Quantity (i.e EOQ)

D = Annual Demand, in units, for the inventory item Co = Ordering cost per order

Ch = Carrying or holding cost per unit per year  P = Purchasing cost per unit of the inventory item

The unit carrying cost, Ch, is usually expressed in one of two ways, as follows:

1. As a fixed cost, for example, Ch is $0.50 per unit per

 

2. As a percentage (typically denoted by l) of the item’s unit purchase cost or price. For example, Ch is 20% of the item’s unit In general

Ch  = I X P                               (2)

For a given order quantity, Q, the ordering, holding and total costs can be computed using the following formulae:

Total Ordering Cost = (D/Q) x Co                                          (3)

Total Carrying Cost = (Q/2) x Ch                                            (4)

Total Cost = Total Ordering Cost + Total Carrying Cost + Purchase Cost

= (D/Q) x Co  + (Q/2) x Ch  + P x D                             (5)

Observe that the total purchase cost (i.e. P x D) does not depend on the value of Q. This is so because regardless of how many orders we place each year, or how many units we order each time, we will still incur the same annual total purchase cost.

The presence of Q in the denominator for the first term makes equation (5) a non-linear equation with respect to Q. Nevertheless, because the total ordering cost is equal to the total carrying cost at the optimal value of Q, we can set the terms in equation (3) and (4) equal to each other and calculate EOQ as

Q^* = √2𝐷 Co/ Ch                                                                       (6)

 

Inventory Control with Deterministic Models

Examples 1

1. The production department for a company requires 3, 600 kg of raw material for manufacturing a particular item per year. It has been estimated that the cost of placing an order is Rs. 36 and the cost of carrying inventory is 25% of the investment in the inventories. The price is Rs. 10/kg. The purchase manager wishes to determine an ordering policy for raw

Solution

From the data of the problem we know that

D = 3600 kg per year;   Co  = Rs. 36 per order;    Ch = 25% of the investment in inventories

= 10 X 0.25 = Rs. 2.50 per kg per year.

 

• The optimal lot size is given by

Q^* = √2𝐷 Co/ Ch = √2 𝑋 3600 𝑋 36 / 250 = 321.99 kg per order.

 

1. Optimal order cycle time

t^* = ^𝑄∗ = 321.99/3600 = 0.894 year

𝐷

 

• The minimum yearly variable inventory cost

TVC = √2𝐷 CoCh = √2𝑋 3600 𝑋 36 𝑋 2.5 = Rs. 804.98 per year

 

1. The minimum yearly total inventory cost

TC^* = TVC^* + DC = Rs. 804-98 + (3600 kg) (Rs. 10/kg) = Rs. 36, 804.98 per year.

 

2. A company operating 50 weeks in a year is concerned about its stocks of copper This costs Rs. 240/- a meter and there is a demand for 8, 000 meters a week. Each replenishment costs Rs. 1, 050 for administration and Rs. 1, 650 for delivery, while holding

 

costs are estimated at 25% of value held a year. Assuming no shortages are allowed, what is the optimal inventory policy for the company?

How would this analysis differ if the company wanted to maximise profit rather than minimise cost? What is the gross profit if the company sell cable for Rs. 360 a meter?

Solution

From the data of the problem, we have

Demand rate (D) = 8, 000 x 50 = 4, 00, 000 metres a year

Purchase Cost (C) = Rs. 240 a unit; Ordering cost (Co) = 1, 050 + 1, 650 = Rs. 2, 700 Holding Cost = 0.25 x 240 = Rs. 60 a meter a year

1. Optimal order quantity Q^* = √2𝐷 Co/ Ch = √2 𝑋 40,000 𝑋 2,700 = 6, 000 meters

60

 

1. Total variable inventory cost, TVC = Q^*. Ch = 6, 000 x 60 = Rs. 3, 60, 000 a year

 

1. Total inventory cost, TC = D.C + TVC = 4, 00, 000 x 240 + 3, 60, 000 = Rs. 9, 63, 60, 000

With a turnover in excess of 96 million rupees a year inventory costs are only Rs. 3, 60, 000 or 0.36%. This figure is usually low but any well run organisation should try to make all the waivings it can, however, small.

If the company wanted to maximise profit rather than minimise cost, the analysis used would remain exactly the same. This can be demonstrated by defining selling price (SP) per unit so that gross profit per unit becomes,

Profit = Revenue – Cost

= D x SP –

DC + 𝐷 Co + 𝑄 Ch

𝑄                    2

 

When this equation is solved to maximise profit with respect to Q as discussed earlier, we get the same result by applying usual method.

If company sells the cable for Rs. 360 a meter, its revenue is Rs. 360 x 4, 00, 000 = Rs. 14, 40, 00, 000 a year. Direct cost of Rs. 9, 63, 60, 000 is subtracted from this to get a gross profit of Rs. 4, 76,  40, 000 a year.

3. A chemical company is considering the optimal batch size for reorder of concentrated sulphuric acid. The management accountant has supplied the following information:

• The purchase price of H2SO4 is Rs. 150 per
• The clerical and data processing costs are 500 per order.

All the transport is done by rail. A charge of Rs. 2, 000 is made each time the special line to the factory is opened. A charge of Rs. 20 gallon is also made. The company uses 40, 000 gallons per year. Maintenance costs of stock are Rs. 400 per gallon per year.

Each gallon requires 0.5 sq ft of storage space. If warehouse space is not used, it can be rented out to another company at Rs. 200 per sq ft per annum. Available warehouse space is 1, 000 sq ft, the overhead costs being Rs. 5, 000 p.a. Assume that all free warehouse space can be rented out.

• Calculate the economic reorder size
• Calculate the minimum total annual cost of holding and reordering

Solution

Based on the data of the problem, the relevant cost components which will vary over the time period due to change in lot size quantity (Q) and which will remain fixed is summarised as follows:

 

	Relevant     Cost     for     EOQ Calculation	Irrelevant    Cost     for     EOQ Calculation
Ordering Cost         Carrying cost	·         Clerical       and                   data processing, Rs. 500; ·         Rail transport, Rs. 2000     ·         Maintenance   cost,   Rs. 200; ·         Rented cost, Rs. 200/2 = Rs. 100	·         Rail transport, Rs. 20 per gallon because a fixed money of Rs. 40, 000 x 20 = Rs. 8, 00, 000 will incur irrespective of size of Q.   ·         Overhead cost, Rs. 5, 000

Thus the relevant costs needed for calculating EOQ are: Co = Rs. 2, 500; Ch = Rs. 300.

 

Q^* (EOQ) =

2𝐷Co

√

Ch

2 𝑥 40,000 𝑥 2,500

=

√

300

= Rs. 817 (approx.) gallons.

 

 

Hence, the minimum total annual costs are:

 

 

Ordering: ^𝐷

Q∗

Co = 40,000 x 2, 500 = Rs. 1, 22, 399.02

817

 

Carrying: Q∗  Ch  = 817  x 300 =         Rs. 1, 22, 250.00

2                      2

Total                      = Rs. 2, 44, 949.02

Rail transport: 40, 000 x 2 = Rs. 8, 00, 000 Storage Overhead cost:                      = Rs. 5, 000 Purchase Cost: 40, 000 x 150 = Rs. 60, 00, 000

Total                                        = Rs. 70, 49, 949.02

4. A contractor has to supply 10, 000 bearings per day to an automobile manufacturer. He finds that when he starts production run, he can produce 25, 000 bearings per day. The cost of holding a bearing in stock for a year is Rs. 2 and the set-up cost of a production run is Rs. 180. How frequently should production run be made?

Solution

From the data of the problem in usual notation, we have

Co  = Rs. 1, 800 per production run;                 Ch = Rs. 2 per year

p = Rs. 25, 000 bearings per day                     d = 10, 000 bearings per day

D = 10, 000 x 300 = 30, 00, 000 units/year (assuming 300 working days in the year).

1. Economic batch quantity for each production run is given by

 

 

Q* = √2𝐷𝐶𝑜 (

) = √2 𝑥 30,00,000 𝑥 1,800 (         25,000

) = 1, 04, 446 bearings

 

𝐶ℎ        𝑝−𝑑

2                             25,000−10,000

 

1. Frequency of production cycles

t^* = ^𝑄∗ = 1, 04, 446/10, 000 = 10.44 days.

𝑑

5. A commodity is to be supplied at a constant rate of 25 units per A penalty cost is being charged at the rate of Rs. 10 per unit per day late for missing the scheduled delivery date. The cost of carrying the commodity in inventory is Rs. 16 per unit per month. The production process is such that each month (30 days) a batch of items is started and are available for delivery any time after the end of the month. Find the optimal level of inventory at the beginning of each month.

Solution:

From the data in usual notations, we have

D = 25 units / day;       Ch  = 16/30 = 0.53 per unit per day;      Co = Rs. 10 per unit per day; t = 30 days

Thus optimal inventory level is given by

 

 

M^* = [   ¹⁰ 0.53+10

] (25) (30) = 712 units.

 

 

SELECTIVE INVENTORY CONTROL TECHNIQUES

In practice when a firm maintained large number of items in its inventory, obviously all items cannot, and need not be controlled (i.e. keeping record of time interval between successive reviews of demand; order frequencies; expected demand rate; order quantities etc.) with equal attention.  All items are not of equal importance to the firm in such terms as sales, profits, availability etc. One way of exercising proper degree of control overall and various types of items held in stocks is to classify them into groups (or classes) on the basis of the degree of control or intensity of management effort that they require.

By selectively applying inventory control policies to these different groups, inventory objectives can be achieved with lower inventory levels than with a single policy applied to all items. These techniques are also known as selective multi-item inventory control techniques.

In this section, we shall consider certain group classifications such as: ABC, VED, FSN, HML, XYZ etc.

Classification	Basis of Classification	Purpose
ABC {Always, Better, Control}	Value of consumption	To     control     raw         material, components         and         work-in- progress    inventories   in    the normal course of business.
HML {High, Medium, Low}	Unit price of the material	Mainly to control purchases
XYZ	Value of items in storage	To review the inventories and their uses at scheduled intervals.
VED {Vital, Essential, Desirable}	Criticality of the component	To    determine   the    stocking levels of spare parts.
FSN {Fast, Slow, Non-moving}	Consumption  pattern   of   the component	To control obsolescence

 

ABC ANALYSIS

The ABC analysis consists of separating the inventory items into three groups: A, B and C according to their annual cost volume consumption (unit cost x annual consumption). Although the break points between these groups vary according to individual business conditions, a common break down might be as follows:

Category or Group	Percentage of the item	% of the Total Annual Value of the inventories (Rs.)
A	10 – 20	70 – 85
B	20 – 30	10 – 25
C	60 – 70	5 – 15

 

This type of classification is also known as the principle of law of Vital Few and Trivial Many. The ABC analysis facilitates analysis of yearly consumption value of items in the store to identify the vital few items which are generally referred to as A category items. Generally, these items accounting for about 70% of the total money value of consumption. Items accounting for about 25% of the total money value of consumption are called B category items and the remaining ones accounting for about 5% consumption value as C category items.

Carrying on the ABC analysis of the store items helps identifying the few items that are vital from financial point of view and require careful watch, scrutiny and follow-up. The application of ABC

 

analysis extends overall of the aspects of materials management like purchasing, inventory control, value analysis etc.

After the items are so classified, the inventory control policies are made on the basis of the classification ‘A’ category items require special managerial attention, therefore, fixed-interval inventory control system might be used for these items. ‘C’ category items can be managed in a little casual manner. For these items, a fixed-order quantity system might be used. The order quantities can be relatively large without incurring excessive costs. A large reserve stock can also be maintained. ‘B’ items are not so costly as to require special managerial attention, but these are not so cheap as to ignore overstocking, therefore (s, S) inventory control system might be used for these items.

The procedure of ABC analysis is summarised in the following steps:

Step 1

Obtain data on the annual usage (or consumption) in units and unit cost of each inventory unit. Multiple the annual usage in units and the value of each item to get annual value for each of these items.

Annual Value = Unit Cost x Annual Consumption

Step 2

Arrange these inventory items in a decreasing order of their value computed in step 1.

Step 3

Express the annual value of each item as percentage of the total value of all items. Also compute the cumulative percentage of annual consumption rupees spent.

Step 4

Obtain the percentage value for each of the items. That is, if there are 50 items involved in classification, then each item would represent 100/50 = 2 percent of the total items. Also cumulate these percentage values.

Step 5

Draw a graph between cumulative percentage of items (on x-axis) and cumulative annual percentage of usage value (on y-axis), and mark cut-off points where the graph changes slope as shown in figure.

Example 1

A company produces a mix of high technology products for use in hospitals. The annual sales data are as follows:

Product Type	Number      of Units	Unit Price (Rs.)	Product Type	Number      of Units	Unit Price (Rs.)
1	1, 000	2.50	10	600	1.62
2	250	0.55	11	25	33.00
3	150	6.50	12	4	15.50

 

4	300	1.00	13	1, 000	5.00
5	100	1.50	14	2, 850	2.50
6	700	1.43	15	10	0.83
7	500	7.00	16	355	0.98
8	15	4.98	17	50	1.37
9	1, 000	0.75	18	393	1.85

For inventory control reasons, the company wants to classify these items into three groups A, B and C on the basis of annual sales value of each item. You please help the company.

Solution

The annual sales volume (in Rs.) for each product and the item ranking on the basis of this volume is shown in Table.

Product ranking as per sales volume

Product Type	Number          of Units	Unit Price (Rs.)	Annual      Sales Volume (Rs.)	Ranking
1	1000	2.50	2, 500.00	4
2	250	0.55	137.50	14
3	150	6.50	975.00	6
4	300	1.00	300.00	12
5	100	1.50	150.00	13
6	700	1.43	1001.00	5
7	500	7.00	3500.00	3
8	15	4.98	74.70	16
9	1000	0.75	750.00	9
10	600	1.62	972.00	7
11	25	33.00	825.00	8
12	4	15.50	77.50	15
13	1000	5.00	5000.00	2
14	2850	2.50	7125.00	1
15	10	0.83	8.30	18
16	355	0.98	347.90	11
17	40	1.37	54.80	17
18	393	1.85	727.05	10

The cumulative percentage of products and cumulative percentage of sales for each product is given in table for the purpose of ABC classification:

ABC Classification

Rank	Product	Product Cumulative % of products	Annual Sales Volume (Rs.)	Cumulative Annual Sales Volume (Rs.)	Cumulative % Product Class of Sales
1	14	5.56	7, 125.00	7,125.00	29.05 A product 11.11%
2	13	11.11	5, 000.00	12,125.00	49.43 products and 49.43 Rs.
3	7	16.67	3, 500.00	15,625.00	63.70 B products: 38.89%

 

4	1	22.22	2, 500.00	18,125.00	73.90 Products and 42.91 Rs.
5	6	27.78	1, 001.00	19,125.00	77.97
6	3	33.33	975.00	20,101.00	81.95
7	10	38.89	825.00	21,073.00	85.92
8	11	44.44	750.00	21,898.00	89.28
9	9	50.00	727.05	22,648.00	92.34
10	18	55.56	347.90	23,375.00	95.30 C Products 44.44%
11	16	61.11	300.00	23,722.00	96.72 products and 7.66 Rs.
12	4	66.67	150.00	24,022.00	97.94
13	5	72.22	137.50	24,172.95	98.56
14	2	77.78	27.50	24,310.45	99.12
15	12	83.33	24.70	24,387.95	99.43
16	8	88.89	54.80	24,462.65	99.74
17	17	94.44	8.30	24,517.45	99.96
18	15	100.00		24,525.75	100.00

The percentage of products and percentage of annual sales volume can also be plotted on the graph.

VED Analysis

This analysis helps in separating the inventory items into three groups according to their criticality, usually called V, E, and D items in that order, VED classification calls for classification of items as Vital, Essential and Desirable.

V items are considered vital for smooth running of the system and without these items the whole system becomes inoperative. Thus adequate stock is required all the time.

 

E items are considered essential to the efficient running of the system and non-availability of these items reduces the efficiency of the system.

 

D items neither stop the system nor reduce its efficiency, but availability of such items will lead to increase in efficiency and reduction of failure.

 

This classification is largely useful in controlling inventory of spare parts. It can also be used in case of such raw materials whose availability is rare.

ABC analysis and VED analysis can also be combined to control the stocking of spare parts based on the desired customer service level as shown in the table.

ABC Classification	VED Classification
	V	E	D
A	Constant        control, Regular follow-up Low      stocks      and ordering             more frequently	Average    stock;    No risk of stock outs.	No stock
B	Average stocks	Average stock; some	Very     low     stocks;

 

	No risk of stock outs	risk can be taken	Some    risk    can    be taken.
C	High Stocks Restricted orders; No risk	Average Stock; some risk can be taken.	Low    stocks;    some risk can be taken.

HML Analysis

Based on the unit price of items, the HML classification separates inventory items, as High price, Medium price and Low price. This analysis is helpful to control purchase of various items for inventory.

FSN Analysis

The consumption pattern or inventory items forms the basis for FSN analysis. Items are classified as Fast-moving, Slow-moving and Non-moving. Sometimes items are also classified as FSND: Fast-moving; Slow-moving; Normal-moving and Dead (or Non-moving). This classification is based on the movement (or consumption pattern) and therefore helps to controlling obsolescence of various items by determining the distribution and handling patterns. Cut-off points of the three classes are usually in terms of number of issues in the previous few years.

 

XYZ Analysis

This classification is based on the closing value of items in storage. Items whose inventory values are high and moderate are classified as X-items and Y-items respectively, while items with low inventory value are termed as Z-items.

This analysis is usually undertaken once a year during the annual stock taking exercise. This helps in identifying the items which are being stocked extensively.

This classification can also be combined with ABC classification of items to control inventory of items as shown in the table below:

ABC Classification	XYZ Classification
	X	Y			Z
A	Attempt    to    reduce stocks	Attempt Z-items	to	convert	Items control	are	within
B	Stock                    and consumption            is reviewed more often	Items control	are	within	Review stock at least twice a year
C	Dispose      off      the surplus items	Check and maintain the control			Review annually		stock

XYZ-FSN classification exercise helps in the timely prevention of obsolescence.

XYZ Classification	FSN Classification
	F	S	N
X	Light inventory control	Reduce stock to very low level	Quick     disposal    of items     at     optimum price
Y	Normal inventory control	Low level of stocks	Should be disposed as early as possible.
Z	Can reduce clerical work	Low level of stocks	Can afford to dispose

 

by increasing stocks.

at lower prices.

Exercises Questions

1. Why is inventory an important consideration for managers?
2. State the purpose of inventory
3. Why would not a company all the time store large quantities of inventory to avoid shortages and stockouts?
4. Describe the major decisions that must be made in inventory
5. State some of the assumptions made in
6. Discuss in detail the major inventory costs that are used in
7. Classify the following 14 items in ABC

Code Number	Monthly Consumption (Rs.)	Code Number	Monthly Consumption (Rs.)
D-179-0	451	D-196	214
D-195-0	1,052	D-198-0	188
D-186-0	205	D-199	172
D-191	893	D-200	170
D-192	843	D-204	5,056
D-193	727	D-205	159
D-195	412	D-212	3,424

How the policies with regard to safety stocks, order quantity, material control and inventory system will be different for the items classified as A, B and C?

8. The following information is provided for an item:

Annual demand: 12, 000 units;                       Ordering Cost: Rs. 60/order

Carrying Cost: 10%;                                       Unit cost of item: Rs. 10 and Lead Time: 10 days.

There are 300 working days in a year. Determine EOQ and number of orders per year. In the past two years the demand rate has gone as high as 70 units/day. For a reordering system based on the inventory level, what should be the buffer stock? What should be the reorder level at this buffer stock? What would be the carrying costs for a year?

9. The demand for an item in a company is 18,000 units per year, and the company can produce the item at a rate of 3,000 per month. The cost of one set-up is 500 and the holding cost of one unit per month is 15 paise. The shortage cost of one unit is Rs. 240 per year. Determine the optimum manufacturing quantity and the number of shortages. Also determine the manufacturing time and the time between set-ups.
10. A product is sold at the rate of 50 pieces per day and is manufactured at a rate of 250 pieces per day. The set-up cost of the machines is 1, 000 and the storage cost is found to be Re 0.0015 per piece per day. With labour charges of Rs. 3.20 per piece, material cost at Rs.2.10 per piece and overhead cost of Rs.4.10 per piece, find the minimum cost batch size if the interest charges are 8% (assume 300 working days in a year). Compute the optimal number of cycles required in a year for the manufacture of this product.

 

 

REFERENCE: http://mu.ac.in/wp-content/uploads/2017/10/dormsem1optimizationmodel1.pdf

 

 

UNIT-3

Introduction to Sequencing:

Sequencing Problems,

Solution to Sequencing Problem – Processing n-jobs through one machine, Processing n-jobs through two machines,

Processing n-jobs through Three Machines, Processing two through m- machines, processing n-jobs through m-machines.

         Network Models:

         PERT AND CPM

Introduction

Analysis

Construction & Identification

Slack and Float Variable

 

INTRODUCTION

The short-term schedules show an optimal order (sequence) and time in which jobs are processed as well as show timetables for jobs, equipment, people, materials, facilities and all other resources that are needed to support the production plan. The schedules should use resources efficiently to give low costs and high utilisations. Other purpose of scheduling are, minimising customers wait time for a product, meeting promised delivery dates, keeping stock levels low, giving preferred working pattern, minimising waiting time of patients in a hospital for different types of tests and so on.

The general scheduling or sequencing problem may be described as: Let there be n jobs to be performed one at a time on each of m machines. The sequence (order) of the machines in which each job should be performed is given. The actual or expected time required by the jobs on each of the machines is also given. The general sequencing problem, therefore, is to find the sequence out of (n!)^m possible sequences which minimise the total elapsed time between the start of the job in the first machine and the completion of the last job on the last machine.

In particular, if n = 3 and m= 3, then total number of possible sequences will be (3!)³ = 216. Theoretically, it may be possible to find optimum sequence but it will require a big computational time. Thus, one should adopt sequencing technique.

To find optimum sequence we first calculate the total elapsed time for each of the possible sequences. As stated earlier, even if values of m and n are very small, it is difficult to get the desired sequence with total minimum elapsed time. However, due to certain rules designed by Johnson, the task of determining an optimum sequence has become quite easy.

 

NOTATIONS, TERMINOLOGY AND ASSUMPTIONS

Notations

tij = Processing time (time required) for job i on machine j.

T = Total elapsed time for processing all the jobs. This includes idle time, if any. Iij = Idle time on machine j from the end of job (j – 1) to the start of job i.

 

Terminology

• Number of Machines: The number of machines refer to the number of service facilities through which a job must pass before it is assumed to be
• Processing Time: It is the time required by a job on each
• Processing Order: It refers to the order (sequence) in which machines are required for completing the
• Idle Time on a Machine: It is the time for which a machine does not have a job to process, e idle time from the end of job (i-1) to the start of job i.
• Total Elapsed Time: It is the time interval between starting the first job and completing the last job including the idle time (if any) in a particular order by the given set of
• No Passing Rule: It refers to the rule of maintaining the order in which jobs are to be processed on given machines. For example, if n jobs are to be processed on two

machines M1 and M2 in the order M1 M2, then each job should go to machine M1 first and then to M2.

 

Assumptions

1. The processing time on different machines are exactly known and are independent of the order of the jobs in which they are to be
2. The time taken by the job in moving from one machine to another is
3. Once a job has begun on a machine, it must be completed before another job can begin on the same
4. All jobs are known and are ready for processing before the period under consideration begins.
5. Only one job can be processed on a given machine at a
6. Machines to be used are of different
7. The order of completion of jobs are independent of the sequence of

 

PROCESSING n JOBS THROUGH TWO MACHINES

Let there be n jobs, each of which is to be processed through two machines, M1 and M2 in the order M1 M2, i.e. each job has to be passed through the same sequence of operations. In other words, a job is assigned on machine M1 first and after it has been completely processed on machine M1, it is assigned to machine M2. If the machine M2 is not free at the moment for processing the same job, then the job has to wait in waiting line for its turn on machine M2,

i.e. passing is not allowed.

Since passing is not allowed, therefore, machine M1 will remain busy in processing all the n jobs one-by-one which machine M2 may remain idle time of the second machine. This can be achieved only by determining sequence of n jobs which are to be processed on two machines M1 and M2. The procedure suggested by Johnson for determining the optimal sequence can  be summarised as follows:

 

The Algorithm

Step 1              List the jobs along with their processing times on each machine in a table as shown below:

Processing Time on Machine	Job Number 1                 2               3                  n
M1	t11                  t12                 t13                      t1n
M2	t21                  t22                 t23                         t2n

Step 2              Examine the columns for processing times on machines M1 and M2, and find the smallest processing time in each column, i.e find out, min. (t1j, t2j) for all j.

Step 3(a)             If the smallest processing time is on machine M1, then schedule the job as early as possible without moving jobs already schedules, i.e place the job in the first available position in the sequence. If the processing time is on machine M2, then schedule the job as late as possible without moving any jobs already scheduled, i.e. place the job in the last available position in the sequence.

1. If there is a tie in selecting the minimum of all the processing times, then there may be three situations:

 

1. Minimum among all processing times is same for the machine e. min (t1j, t2j) = t2k = t2r,then process the kth job first and the rth job last.
2. If the tie for the minimum occurs among processing times t1j on machine M1 only, thenselect the job corresponding to the smallest job subscript
3. If the tie for the minimum occurs among processing times t2j on machine M2, then selectthe job corresponding to the largest job corresponding to the largest job subscript

 

Step 4             Remove the assigned jobs from the table. If the table is empty, stop and go to Step 5. Otherwise, got to Step 2.

 

Step 5              Calculate idle time for machines M1 and M2:

1. Idletime for machine M1 = (Total Elapsed Time) – (Time when the last job in a sequence

finishes on machine M1)

1. Idletime for machine M2 = Time at which the first job in a sequence finishes on machine

 

M1 + ∑

𝑛

𝑗=2

{(Time when the jth job in a sequence starts on machine M2) – (Time when the

 

(j – 1)th job in a sequence finishes on machine M2)}.

 

𝑗=1

Step 6              The total elapsed time to process all jobs through two machines is given by Total Elapsed time = Time when the nth job in a sequence finishes on Machine M2.

 

= ∑

𝑛

𝑗=1

𝑀2𝑗 + ∑^𝑛

𝐼2𝑗

 

where M2j = Time required for processing jth job on machine M2.

I2j = Time for which machine M2 remains idle after processing (j – 1)th job and before starting work in jth job.

EXAMPLE 1

Find the sequence that minimises the total elapsed time required to complete the following tasks on two machines:

Task	A	B	C	D	E	F	G	H	I
Machine I	2	5	4	9	6	8	7	5	4
Machine II	6	8	7	4	3	9	3	8	11

Solution:

The smallest processing time between the two machines is 2 which corresponds to task A on Machine I. Thus, task A is scheduled as early as possible to give the sequence as shown below:

A

After the task A has been set for processing first, we are left with 8 tasks and their processing times as given below:

Task	B	C	D	E	F	G	H	I
Machine I	5	4	9	6	8	7	5	4
Machine II	8	7	4	3	9	3	8	11

The minimum processing time in this reduced problem is 3 which corresponds to task E and G both on machine II. Since the corresponding processing time of task E on machine I is less than the corresponding processing time of task G on machine I, therefore, task E will be scheduled in the last and task G shall be scheduled before it. Tasks E and G will not be considered further. Thus, current partial sequence of scheduling tasks becomes:

A

G

E

A set of processing times now gets reduced to:

Task	B	C	D	F	H	I
Machine I	5	4	9	8	5	4
Machine II	8	7	4	9	8	11

The smallest processing time in this reduced problem is 4, which corresponds to task C and I on machine I and to task D on machine II. Thus task C will be placed in the second sequence cell and task I in the third sequence cell and task D in the sequence cell before task G. The entries of the partial sequence are now:

A

C

I

D

G

E

The set of processing time now gets reduced as follows:

Task	B	F	H
Machine I	5	8	5
Machine II	8	9	8

the smallest processing time in this reduced problem is 5, which corresponds to tasks B and H both on machine I. Since the corresponding processing times of B and h on machine II is same, therefore, either of these two tasks can be placed in fourth and fifth sequence cells. Thus, it indicates an alternative optimal sequence. the optimal sequences are, therefore, given below:

A

C

I

B

H

F

D

G

E

 

A

C

I

H

B

F

D

G

E

The minimum elapsed time for machines I and II is calculated as shown in Table 1.

Task Sequence	Machine I		Machine II
	Time In	Time Out	Time In	Time Out
A	0	2	2	8
C	2	6	8	15
I	6	10	15	26
B	10	15	26	34
H	15	20	34	42
F	20	28	42	51
D	28	37	51	55
G	37	44	55	58
E	44	50	58	61

In table 1, the minimum elapsed time, i.e time from start of task A to completion of last task  E is 61 hours. During this time the machine I remains idle for 61 – 50 = 11 hours. The idle time for machine II is equal to the time at which the first task A in the sequence finishes on machine I plus the last task E in the sequence starts on machine II minus the last but one task G finishes on machine II, i.e 2 + 58 – 58 = 2 hours.

PROCESSING n JOBS THROUGH THREE MACHINES

Johnson provides an extension of his procedure to the case in which there are three instead of two machines. Each job is to be processed through three machines M1, M2 and M3. The list of jobs with their processing times is given below. An optimal solution to this problem can be obtained if either or both of the following conditions hold good.

Processing time on Machine	Job Number
	1	2	3	4
M1 M2 M3	t11 t21 t31	t12 t22 t32	t13 t23 t33	t1n t2n t3n

1. The minimum processing time on machine M1 is at least as great as the maximum processing time on machine M2, that is,

min t1j ≥ max t1j,            j = 1, 2, 3, …n

2. The minimum processing time on machine M3 is at least as great as the maximum processing time on machine M2, that is

min t3j ≥ max t2j,             j = 1, 2, 3, …n

If either or both the above conditions hold good, then the steps of the algorithm can be summarised in the following steps:

 

THE ALGORITHM

Step 1: Examine processing times of given jobs on all three machines and if either one or both the above conditions hold, then go to step 2, otherwise the algorithm fails.

Step 2: Introduce two fictitious machines, say G and H with corresponding processing times given by

1. tGj = t1j + t2j,   j = 1, 2, 3,…. n.

that is, processing time on machine G is the sum of the processing times on machines M1 and M2, and

1. tHj = t2j + t3j,   j = 1, 2, 3,…. n.

that is, processing time on machine H is the sum of the processing times on machines M2 and M3.

Step 3: Determine the optimal sequence of jobs for this n-job, two machine equivalent sequencing problem with the prescribed ordering GH in the same way as discussed earlier.

EXAMPLE

Find the sequence that minimises the total time required in performing the following jobs on three machines in the order ABC. Processing times (in hours) are given in the following  table:

Job	1	2	3	4	5
Machine A	8	10	6	7	11
Machine B	5	6	2	3	4
Machine C	4	9	8	6	5

 

Solution: Here, min (tAj) = 6; Min (tCj) = 4; max (tBj) = 6. Since min (tAj) ≥ (tBj) for all j is satisfied, the given problem can be converted into a problem of 5 jobs and two machines. The processing time on two fictitious machines G and H can be determined by the following relationships:

tGj = tAj + tBj, j = 1, 2, 3, n.

and tHj = tBj + tCj, j = 1, 2, 3, n.

The processing times for the new problem are given below:

Job	1	2	3	4	5
Machine G Machine H	8 + 5 = 13 5 + 4 = 9	10 + 6 = 16 6 + 9 = 15	6 + 2 = 8 2 + 8 = 10	7 + 3 = 10 3 + 6 = 9	11 + 4 = 15 4 + 5 = 9

When the algorithm described for n jobs on two machines is applied to this problem, the optimal sequence so obtained is given by

3

2

5

1

4

The total minimum elapsed time is given in Table 1:

Job Sequence	Machine A		Machine B		Machine C
	Time In	Time Out	Time In	Time Out	Time In	Time Out
3	0	6	6	8	8	16
2	6	16	16	22	22	31
5	16	27	27	31	31	36
1	27	35	35	40	40	44
4	35	42	42	45	45	51

Table 1 indicates that the minimum total elapsed time is 51 hours. The idle time for machines A, B and C is 9 (=51 – 42) hours, 6 (= 51 – 45) hours and 9 (= 8 – 0) + (45 – 44) hours, respectively.

 

PROCESSING n JOBS THROUGH m MACHINES

Let there be n jobs, each of which is to be processed through m machines, say  M1, M2,……. Mm

in the order M1, M2,……. Mm. The optimal solution to this problem can be obtained if either or

both of the following conditions hold good.

(a)    Min {t1j} ≥ Max { t1j}; j = 2, 3, ….. m – 1

and or (b) Min {tmj} ≥ Max { tij}; j = 2, 3, ….. m – 1

that is, the minimum processing time on machines M1 and Mm is as great as the maximum processing time on any of the remaining (m – 1) machines.

If either or both these conditions hold good, then the steps of the algorithm can be summarised in the following steps:

Step 1: Find, Min { t1j}, Min {tmj} and max {tij}and verify above conditions. If either or both the conditions mentioned above hold, then go to step 2. Otherwise the algorithm fails.

Step 2: Convert m-machine problem into 2-machine problem by introducing two fictitious machines, say

(i) tGj = t1j + t2j + t3j  +……+tm – 1j   j = 1, 2, 3,… n.

i.e. processing time of n-jobs on machine G is the sum of the processing times on Machines M1, M2 Mm – 1j

(ii) tHj = t2j + t3j + t4j +……+ tmj   j = 1, 2, 3,…. n.

 

i.e. processing time of n-jobs on machine H is the sum of the processing times on Machines M1, M2 Mmj.

Step 3: The new processing times so obtained can now be used for solving n-job, two machines equivalent sequencing problem with the prescribed ordering HG in the same way as t2j + t3j +……+tm – 1j = k (constant)

for all j = 1, 2, 3, ….. m – 1, then the optimal sequence can be obtained for n-jobs and two machines M1 and Mm in the order M1 Mm as usual.

2. If t1j = tmj and tGj = tHj, for all j = 1, 2, 3, n, then total number of optimal sequences will

be n and total minimum elapsed time in these cases would also be the same.

3. The method described above for solving n-jobs and m-machines sequencing problem is not a general method. It is applicable only to certain problems where the minimum cost (or time) of processing the jobs through first and/or last machine is more than or equal to the cost (or time) of processing the jobs through remaining

EXAMPLES

1. Find an optimal sequence for the following sequencing problems of four jobs and five machines when passing is not allowed of which processing time (in hours) is given below:

Job	Machines
	M1	M2	M3	M4	M5
A	7	5	2	3	9
B	6	6	4	5	10
C	5	4	5	6	8
D	8	3	3	2	6

Also find the total elapsed time. Solution: Here,

Min (tM1, j) = 5 = tM1, C

Min (tM5, j) = 6 = tM5, D

and Max { tM2, j, tM3, j, tM4, j} = {6, 5, 6} respectively.

Since the condition of Min (tM5, j) ≥ Max { tM2, j, tM3, j, tM4, j} is satisfied, therefore the given problem can be converted into a four jobs and two machines problem as G and H. The processing times of four jobs denoted by tGj and tHj on G and H, respectively are as follows:

Job	A	B	C	D
Machine G Machine H	17 19	21 25	20 23	16 14

where tGj = ∑𝑚−1 𝑡𝑖𝑗 and tHj = ∑𝑚 𝑡𝑖𝑗.

𝑖=1                                                    𝑖=2

Now using the optimal sequence algorithm, the following optimal sequence can be obtained.

A

C

B

D

The total elapsed time corresponding to the optimal sequence can be calculated as shown in Table 1, using the individual processing times given in the original problem.

Table 1 shows that the minimum total elapsed time is 51 hours. The idle time for machines M1, M2, M3, M4 and M5 is 25, 33, 37 and 18 hrs respectively.

Table 1            Minimum Elapsed Time

Job Sequence	Machine
	M1	M2	M3	M4	M5
A B	0 – 7 7 – 12	7 – 12 12 – 18	12 – 14 16- 21	14 – 17 21 – 27	16 – 26 27 – 35

 

C D

12 – 18 18 – 26

18 – 24 26 – 29

24 – 28 29 – 32

28 – 33 33 – 35

35 – 45 45 – 51

 

2. Solve the following sequencing problem giving an optimal solution when passing is not allowed.

Machine	Job
	A	B	C	D	E
M1	11	13	9	16	17
M2	4	3	5	2	6
M3	6	7	5	8	4
M4	15	8	13	9	11

Solution: From the data of the problem it is observed that Min (tM1, j) = 9 = tM1, C

Min (tM4, j) = 8 = tM4, B

and Max { tM2, j} = 6 = , tM2, E;   Max { tM3, j} = 8 = , tM2, D. Since both the conditions

Min (tM1, j) ≥ Max { tM2, j; tM3, j} ; j = 1, 2,…. , 5

are satisfied, therefore given problem can be converted into a 5-jobs and 2-machine problem as G and H.

Further, it may be noted that, tM2, j +  tM3, j  = 10 (a fixed constant) for all j (j = 1, 2,.. , 5).

Thus the given problem is reduced to a problem of solving 5-jobs through 2-machines M1 and M4 in the order M1 M4. This means machines M2 and M4 will have no effect on the optimality of the sequences.

The processing times of 5 jobs on machine M1 and M4 is as follows:

Job	A	B	C	D	E
Machine M1 Machine M4	11 15	13 8	9 13	16 9	17 11

Now using the algorithm described earlier, the optimal sequence so obtained as follows:

C

A

E

D

B

The total elapsed time corresponding to the optimal sequence is 83 hours as shown in table 1, using the individual processing times given in the original problem:

Table 1 Minimum Total Elapsed Time

Job Sequence	Machine
	M1	M2	M3	M4
C	0 – 9	9 – 14	14 – 19	19 – 32
A	9 – 20	20 – 24	24 – 30	32 – 45
E	29 – 36	36 – 42	42 – 46	46 – 57
D	36 – 52	52 – 54	54 – 62	62 – 71
B	52 – 65	65 – 68	68 – 75	75 – 83

 

PROCESSING TWO JOBS THROUGH m MACHINES

Let there be two jobs A and B each of  which is to processed on m machines say M1, M2,         ,

Mm in two different orders. The technological ordering of each of the two jobs through m machines is known in advance. Such ordering may not be same for both the jobs. The exact  or expected processing times on the given machines are known. Each machine can perform

 

only one job at a time. The objective is to determine an optimal sequence of processing the jobs so as to minimise total elapsed time.

The optimal sequence in this case can be obtained by using graph. The procedure can be illustrated by taking examples.

Example 1: Use the graphical method to minimise the time needed to process the following jobs on the machines shown, i.e. each machine find the job which should be done first. Also calculate the total elapsed time to complete both jobs.

Machine

 

Job 1 {Sequence:	A	B	C	D	E
Time (hrs)	3	4	2	6	2

 

Machine

 

Job 2 {Sequence:	A	B	C	D	E
Time (hrs)	5	4	3	2	6

Solution

The solution procedure for solving the above problem can be summarised in the following steps:

1. Draw the set of axes at right angle to each other where x-axis represents the processing time of job 1 on different machines while job 2 remains idle and y-axis represents processing time of job 2 while job 2 remain
2. Mark the processing times for jobs 1 and 2 on x-axis and y-axis, respectively according to the given order of machines as shown in the figure:

 

 

20                   Idle time for Job 1

Idle time for job 1

 

14

12

A

9

 

 

C

5

 

B

0           3               7     9               15       17 Job 1

 

Graphical solution of 2-Jobs and m-Machines Sequencing Problem

For example, machine A takes 3 hours for job 1 and 3 hours for job 2. Construct the rectangle for machine A as shown in above Figure. Similarly, construct other rectangles for machines B, C, D and E.

 

3. Construct various blocks starting from the origin by pairing the same machine until a point marked ‘finished’ is
4. Draw a line starting from origin to the point marked ‘finish’ by moving horizontally, vertically and diagonally along a line which makes an angle of 45° with the horizontal axis. Moving horizontally along this line indicates that first job is under process while second job is idle. Similarly, moving vertically along this line indicates that the second job is under process while first job is The diagonal movement along this line shows that both the jobs are under process simultaneously.

Since simultaneous processing of both jobs on a machine is not possible, therefore, diagonal movement is not allowed. In other words, diagonal movement through rectangle areas is not allowed.

5. An optimal path is one that minimises the idle time for both the Thus, we must choose the path on which diagonal movement is maximum as shown in the above figure.
6. Total elapsed time is obtained by adding the idle time for either job to the processing time for that In this example, the idle time for the chosen path is found to be 5 hrs and 2 hrs for jobs 1 and 2, respectively. The total elapsed time is calculated as follows:

Elapsed time, Job 1 = Processing time of Job 1 + Idle time for Job 1

= 17 + (2 + 3) = 22 hrs.

Elapsed time, Job 2 = Processing time of Job 2 + Idle time for Job 2

= 22 + (17-15) = 24 hours.

EXERCISES

1. Explain the four elements that characterise a sequencing
2. Explain the principal assumptions made while dealing with sequencing
3. Give Johnson’s procedure for determining an optimal sequence for processing n items on two machines. Give justification of the rule used in the
4. What is no passing rule in a sequencing algorithm? Explain the principal assumptions made while dealing with sequencing
5. Give three different examples of sequencing problems from your daily
6. We have five jobs, each of which must be processed on the two machines A and B in the order Processing times in hours are given in the table below:

Job	1	2	3	4	5
Machine A	5	1	9	3	10
Machine B	2	6	7	8	4

7. We have 5 jobs each of which must go through the machines A, B and C in the order Processing times (in hours) is as follows:

Job	1	2	3	4	5
Machine A	5	7	6	9	5
Machine B	2	1	4	5	3
Machine C	3	7	5	6	7

8. What do you understand by the following terms in the context of sequence of jobs:
9. Job arrival pattern 2. Number of machines 3. The flow pattern in the shop
10. the criteria of evaluating the performance of a schedule.
11. Find an optimal sequence for the following sequencing problem of four jobs and five machines (when passing is not allowed) of which processing time (in hrs) is as follows:

Job	1	2	3	4
Machine M1	6	5	4	7
Machine M2	4	5	3	2
Machine M3	1	3	4	2
Machine M4	2	4	5	1
Machine M5	8	9	7	5

Also find the total elapsed time.

10. Two jobs are to be processed on four machines A, B, C and D. The technological order for these jobs on machines is as follows:

Job 1:  A         B         C         D Job 2: D                        B         A         C

Processing times are given in the following table:

Machines

	A	B	C	D
Job 1	4	6	7	3
Job 2	4	7	5	8

Find the optimal sequence of jobs on each of the machines.

 

 

Network Models:

A Project such as setting up of a new milk plant, research and development in an organization, development of a new milk product, marketing of a product etc. is a combination of interrelated activities (tasks) which must be executed in a certain order before the entire task can be completed. The activities are interrelated in a logical sequence in such a way that same activities can not start until some others are completed. An activity in a project usually viewed as job requiring resources for its completion. The objectives of project management can be described in terms of a successful project which has been finished on time, within the budgeted cost and to technical specifications and to the satisfaction level of end users. Normally for any project, one may be interested in answering questions such as

1. i)  What will be the expected time of project completion?
2. ii) What is the effect of delay of any activity on the overall completion of project?

iii) How to reduce the time to perform certain activities in case of availability of additional funds?

1. iv) What is the probability of completion of project in time?

 

The OR techniques used for planning, scheduling and controlling large and complex projects are often referred to as network analysis. A network is a graphical representation consisting of certain configuration of arrows and nodes for showing the logical sequence of various tasks to be performed to achieve the project objectives. Around five decades ago the planning tool was Gantt bar chart which specifies start and finish time for each activity on a horizontal time scale. The disadvantage is that there is no interdependency among the many activities which control the progress of the project. Now-a-days we use a technical tool for planning, scheduling and controlling stages of the projects known as Critical Path Method (CPM) and Project Evaluation & Review Technique (PERT). The techniques of PERT and CPM prove extremely valuable in assisting the mangers in handling such projects and thus discharging their project management responsibilities both at planning and controlling stages of the projects. Commonly used project management techniques are:

1. a)Critical Path Method (CPM) and
2. b)Project Evaluation and Review Technique (PERT)

18.2  Historical Development

CPM/PERT or Network Analysis as the technique is sometimes called, developed along two parallel streams, one industrial and the other military. CPM was developed in 1957 by  J. E. Kelly of Remington Rand and M. R. Walker of E. I. Du Pont de Nemours & Co. PERT was devised in 1958 for the POLARIS missile program by the Program Evaluation Branch of the Special Projects office of the U. S. Navy, helped by the Lockheed Missile Systems division and the Consultant firm of Booz-Allen & Hamilton.

Both are basically time oriented methods laid to determination of a time schedule for project. The major difference between these two techniques is that PERT is a Probabilistic approach for the determination of time estimates of different activities not exactly known to us. In the case of CPM, different estimates are known as they are deterministic in nature. But now a days both these techniques are used for one purpose. Initially the PERT technique was applied to research and development projects while the CPM was used towards construction projects.

18.3  Methodology in CPM/PERT Technique

The methodology involved in network scheduling by CPM/PERT for any project consists of the following four stages:

18.3.1  Planning

It is started by splitting the total project into small projects. The smaller projects are further divided into different activities and are analyzed by a department or section. The relationship of each activity with respect to other activities are defined and established.

18.3.2  Scheduling

The objective of scheduling is to give the earliest and the latest allowable start and finish time of each activity as well as its relationship with other activities in the project. The schedule must pinpoint the critical path i.e. time activities which require special attention if the project is to be completed in time.

18.3.3  Allocation of resources

Allocation of resources is performed to achieve the desired objective. Resource is a physical variable such as labour, finance, space, equipment etc. which will impose a limitation for completion of a project.

18.3.4  Controlling

The final phase in the project management is controlling. After making the network plan and identification of the Critical path, the project is controlled by checking progress against the schedule, assigning and scheduling manpower and equipment and analyzing the effects of delays. This is done by progress report from time to time and updating the network continuously. Arrow diagram and time charts are used for making periodic progress reports.

18.4  Basic Terminology used in Network Analysis

Network analysis is the general name given to certain specific techniques which can be used for the planning, management and control of projects. A fundamental method in both PERT and CPM is the use of network systems as a means of graphically depicting the current problems or proposed projects in network diagram. A network diagram is the first thing to sketch an arrow diagram which shows inter-dependencies and the precedence relationship among activities of the project. Before illustrating the network representation of a project, let us define some basic definitions:

18.4.1  Activity

Any individual operation, which utilizes resources and has a beginning and an end is called an activity. An arrow is used to depict an activity with its head indicating the direction of progress in the project. It is of four types:

1. a)Predecessor activity:activity that must be completed immediately prior to the start of another activity.
2. b)Successor activity:activity which cannot be started until one or more of other activities are completed but immediately succeed them are called successor activity.
3. c)Concurrent:  Activity which can be accomplished concurrently is known as concurrent activity. An activity can be predecessor or successor to an event or it may be concurrent with the one or more of the other activities.
4. d)Dummy activity:An activity which does not consume any kind of resources but merely depicts the technological dependence is called a dummy activity. Dummy activity is inserted in a network to classify the activity pattern in the following situations:
5. i)To make activities with common starting and finishing points distinguishable.
6. ii)To identify and maintain the proper precedence relationship between activities those are not connected by events.

Let�s consider a situation where A and B are concurrent activities and activity D is dependent on B and C is dependent on both A and B. Such a situation can be handled by use of dummy activity.

When two or more activities are exactly parallel such that they would start at the same node (event) and finish at the same node. A dummy would be inserted between the end of one of the activities and the common finishing node.

This is to ensure that each activity has a unique description when refer to by its start and finish node number. Dummy are often used to improve the layout of network. When they may not strictly necessary to represents the logic involved. This often happens at the start or finish of a network where a number of activities either start from a certain point or converge to particular point.

18.4.2  Event

The beginning and end points of an activity are called events or nodes or connector. This is usually represented by circle in a network.

 

Here, A is known as the activity.

The events can be further classified into three categories:

1. a)Merge Event: When two or more activities come from an event it is known as merge event.
2. b)Burst Event:When more than one activity leaves an event is known as burst event.
3. c)Merge & Burst Event:An activity may be merged and burst at the same time.

18.4.3  Difference between event and activity

An event is that particular instant of time at which some specific part of project is to be achieved while an activity is the actual performance of a task. An activity requires time and resources for its completion. Events are generally described by such words as complete, start, issue, approves, taste etc. while the word like design, process, test, develop, prepare etc. shows that a work is being accomplished and thus represent activity. While drawing networks, it is assumed that

1. a)The movement is from left to right and
2. b)Head event has a number higher than the tail event.

Thus the activity (i-j) always means that job which begins at event (i) is completed at event (j).

 

 

Network representation is based on the following two axioms.

1. a)  An event is not said to be complete until all the activities flowing into it are completed.
2. b)  No subsequent activities can begin until its tail event is reached or completed.

2.1 Introduction to CPM / PERT Techniques

 

CPM/PERT or Network Analysis as the technique is sometimes called, developed along two parallel streams, one industrial and the other military.

 

CPM (Critical Path Method) was the discovery of M.R.Walker of E.I.Du Pont de Nemours & Co. and J.E.Kelly of Remington Rand, circa 1957. The computation was designed for the UNIVAC-I computer. The first test was made in 1958, when CPM was applied to the construction of a new chemical plant. In March 1959, the method was applied to maintenance shut-down at the Du Pont works in Louisville, Kentucky. Unproductive time was reduced from 125 to 93 hours.

 

PERT (Project Evaluation and Review Technique) was devised in 1958 for the POLARIS missile program by the Program Evaluation Branch of the Special Projects office of the U.S.Navy, helped by the Lockheed Missile Systems division and the Consultant firm of Booz-Allen & Hamilton. The calculations were so arranged so that they could be carried out on the IBM Naval Ordinance Research Computer (NORC) at Dahlgren, Virginia.

 

 

The methods are essentially network-oriented techniques using the same principle. PERT and CPM are basically time-oriented methods in the sense that they both lead to determination of a time schedule for the project. The significant difference between two approaches is that the time estimates for the different activities in CPM were assumed to be deterministic while in PERT these are described probabilistically. These techniques are referred as project scheduling techniques.

 

 

In CPM activities are shown as a network of precedence relationships using activity-on- node network construction

• Single estimate of activity time

 

• Deterministic activity times

 

USED IN: Production management – for the jobs of repetitive in nature where the activity time estimates can be predicted with considerable certainty due to the existence of past experience.

In PERT activities are shown as a network of precedence relationships using activity-on- arrow network construction

• Multiple time estimates

 

• Probabilistic activity times

 

USED IN: Project management – for non-repetitive jobs (research and development work), where the time and cost estimates tend to be quite uncertain. This technique uses probabilistic time estimates.

Benefits of PERT/CPM

 

• Useful at many stages of project management

 

• Mathematically simple

 

 

• Give critical path and slack time

 

• Provide project documentation

 

• Useful in monitoring costs

 

Limitations of PERT/CPM

 

• Clearly defined, independent and stable activities

 

• Specified precedence relationships

 

• Over emphasis on critical paths

 

 

2.2   Applications of CPM / PERT

 

 

These methods have been applied to a wide variety of problems in industries and have found acceptance even in government organizations. These include

• Construction of a dam or a canal system in a region
• Construction of a building or highway
• Maintenance or overhaul of airplanes or oil refinery
• Space flight
• Cost control of a project using PERT / COST
• Designing a prototype of a machine
• Development of supersonic planes

 

2.3  Basic Steps in PERT / CPM

 

 

Project scheduling by PERT / CPM consists of four main steps

 

 

1.       Planning

 

• The planning phase is started by splitting the total project in to small projects. These smaller projects in turn are divided into activities and are analyzed by the department or
• The relationship of each activity with respect to other activities are defined and established and the corresponding responsibilities and the authority are also stated.
• Thus the possibility of overlooking any task necessary for the completion of the project is reduced

 

2.       Scheduling

• The ultimate objective of the scheduling phase is to prepare a time chart showing the start and finish times for each activity as well as its relationship to other activities of the
• Moreover the schedule must pinpoint the critical path activities which require special attention if the project is to be completed in
• For non-critical activities, the schedule must show the amount of slack or float times which can be used advantageously when such activities are delayed or when limited resources are to be utilized

 

3.       Allocation of resources

• Allocation of resources is performed to achieve the desired objective. A resource is a physical variable such as labour, finance, equipment and space which will impose a limitation on time for the
• When resources are limited and conflicting, demands are made for the same type of resources a systematic method for allocation of resources become
• Resource allocation usually incurs a compromise and the choice of this compromise depends on the judgment of

 

4.       Controlling

 

• The final phase in project management is controlling. Critical path methods facilitate the application of the principle of management by expectation to identify areas that are critical to the completion of the
• By having progress reports from time to time and updating the network continuously, a better financial as well as technical control over the project is exercised.
• Arrow diagrams and time charts are used for making periodic progress reports. If required, a new course of action is determined for the remaining portion of the project.

 

 

2.4   The Framework for PERT and CPM

 

Essentially, there are six steps which are common to both the techniques. The procedure is listed below:

 

1. Define the Project and all of its significant activities or tasks. The Project (made

up of several tasks) should have only a single start activity and a single finish activity.

 

1. Develop the relationships among the activities. Decide which activities must precede and which must follow

 

• Draw the “Network” connecting all the activities. Each Activity should have unique event numbers. Dummy arrows are used where required to avoid giving the same numbering to two

 

1. Assign time and/or cost estimates to each activity

 

1. Compute the longest time path through the network. This is called the critical path.

 

 

1. Use the Network to help plan, schedule, and monitor and control the

 

The Key Concept used by CPM/PERT is that a small set of activities, which make up the longest path through the activity network control the entire project. If these “critical” activities could be identified and assigned to responsible persons, management resources could be optimally used by concentrating on the few activities which determine the fate of the entire project.

 

Non-critical activities can be replanned, rescheduled and resources for them can be reallocated flexibly, without affecting the whole project.

 

Five useful questions to ask when preparing an activity network are:

 

• Is this a Start Activity?
• Is this a Finish Activity?
• What Activity Precedes this?
• What Activity Follows this?
• What Activity is Concurrent with this?

 

2.5  Network Diagram Representation

 

 

In a network representation of a project certain definitions are used

 

 

1.  Activity

Any individual operation which utilizes resources and has an end and a beginning is called activity. An arrow is commonly used to represent an activity with its head indicating the direction of progress in the project. These are classified into four categories

1. Predecessor activity – Activities that must be completed immediately prior to the start of another activity are called predecessor

 

 

2. Successor activity – Activities that cannot be started until one or more of other activities are completed but immediately succeed them are called successor activities.
3. Concurrent activity – Activities which can be accomplished concurrently are known as concurrent activities. It may be noted that an activity can be a predecessor or a successor to an event or it may be concurrent with one or more of other
4. Dummy activity – An activity which does not consume any kind of resource but merely depicts the technological dependence is called a dummy

 

The dummy activity is inserted in the network to clarify the activity pattern in the following two situations

• To make activities with common starting and finishing points distinguishable
• To identify and maintain the proper precedence relationship between activities that is not connected by

For example, consider a situation where A and B are concurrent activities. C is dependent on A and D is dependent on A and B both. Such a situation can be handled by using a dummy activity as shown in the figure.

2.  Event

An event represents a point in time signifying the completion of some activities and the beginning of new ones. This is usually represented by a circle in a network which is also called a node or connector.

The events are classified in to three categories

1. Merge event – When more than one activity comes and joins an event such an event is known as merge event.

 

 

2. Burst event – When more than one activity leaves an event such an event is known as burst
3. Merge and Burst event – An activity may be merge and burst event at the same time as with respect to some activities it can be a merge event and with respect to some other activities it may be a burst

 

 

3.  Sequencing

The first prerequisite in the development of network is to maintain the precedence relationships. In order to make a network, the following points should be taken into considerations

• What job or jobs precede it?
• What job or jobs could run concurrently?
• What job or jobs follow it?
• What controls the start and finish of a job?

Since all further calculations are based on the network, it is necessary that a network be drawn with full care.

2.6   Rules for Drawing Network Diagram

 

 

Rule 1

Each activity is represented by one and only one arrow in the network

 

 

Rule 2

No two activities can be identified by the same end events

 

 

Rule 3

In order to ensure the correct precedence relationship in the arrow diagram, following questions must be checked whenever any activity is added to the network

• What activity must be completed immediately before this activity can start?
• What activities must follow this activity?
• What activities must occur simultaneously with this activity?

 

In case of large network, it is essential that certain good habits be practiced to draw an easy to follow network

• Try to avoid arrows which cross each other
• Use straight arrows
• Do not attempt to represent duration of activity by its arrow length
• Use arrows from left to right. Avoid mixing two directions, vertical and standing arrows may be used if
• Use dummies freely in rough draft but final network should not have any redundant
• The network has only one entry point called start event and one point of emergence called the end event.

 

2.7   Common Errors in Drawing Networks

 

 

 

The three types of errors are most commonly observed in drawing network diagrams

 

 

1.  Dangling

To disconnect an activity before the completion of all activities in a network diagram is known as dangling. As shown in the figure activities (5 – 10) and (6 – 7) are not the last activities in the network. So the diagram is wrong and indicates the error of dangling

 

 

 

2.  Looping or Cycling

Looping error is also known as cycling error in a network diagram. Drawing an endless loop in a network is known as error of looping as shown in the following figure.

 

 

3.  Redundancy

 

 

Unnecessarily inserting the dummy activity in network logic is known as the error of redundancy as shown in the following diagram

 

 

 

2.8   Advantages and Disadvantages

 

PERT/CPM has the following advantages

 

• A PERT/CPM chart explicitly defines and makes visible dependencies (precedence relationships) between the elements,

 

• PERT/CPM facilitates identification of the critical path and makes this visible,

 

• PERT/CPM facilitates identification of early start, late start, and slack for each activity,

 

• PERT/CPM provides for potentially reduced project duration due to better understanding of dependencies leading to improved overlapping of activities and tasks where

 

 

PERT/CPM has the following disadvantages:

 

• There can be potentially hundreds or thousands of activities and individual dependency relationships,

 

• The network charts tend to be large and unwieldy requiring several pages to print and requiring special size paper,

 

• The lack of a timeframe on most PERT/CPM charts makes it harder to show status although colours can help (e.g., specific colour for completed nodes),

 

• When the PERT/CPM charts become unwieldy, they are no longer used to manage the

 

 

 

 

2.9   Critical Path in Network Analysis

 

 

Basic Scheduling Computations

 

 

The notations used are

(i, j) = Activity with tail event i and head event j E_i = Earliest occurrence time of event i

L_j = Latest allowable occurrence time of event j D_ij = Estimated completion time of activity (i, j) (Es)_ij = Earliest starting time of activity (i, j) (Ef)_ij = Earliest finishing time of activity (i, j) (Ls)_ij = Latest starting time of activity (i, j) (Lf)_ij = Latest finishing time of activity (i, j)

 

The procedure is as follows

 

 

1.       Determination of Earliest time (E_j): Forward Pass computation

 

• Step 1

The computation begins from the start node and move towards the end node. For easiness, the forward pass computation starts by assuming the earliest occurrence time of zero for the initial project event.

 

·         Step 2

1. Earliest starting time of activity (i, j) is the earliest event time of the tail end event i.e. (Es)_ij = E_i
2. Earliest finish time of activity (i, j) is the earliest starting time + the activity time i.e. (Ef)_ij = (Es)_ij + D_ij or (Ef)_ij = E_i + D_ij

 

 

• Earliest event time for event j is the maximum of the earliest finish times of all activities ending in to that event i.e. E_j = max [(Ef)_ij for all immediate predecessor of (i, j)] or E_j =max [E_i + D_ij]

 

2.       Backward Pass computation (for latest allowable time)

 

 

• Step 1

For ending event assume E = L. Remember that all E’s have been computed by forward pass computations.

 

·         Step 2

Latest finish time for activity (i, j) is equal to the latest event time of event j i.e. (Lf)_ij = L_j

 

·         Step 3

Latest starting time of activity (i, j) = the latest completion time of (i, j) – the activity time or (Ls)_ij =(Lf)_ij – D_ij or (Ls)_ij = L_j – D_ij

 

·         Step 4

Latest event time for event ‘i’ is the minimum of the latest start time of all activities originating from that event i.e. L_i = min [(Ls)_ij for all immediate successor of (i, j)] = min [(Lf)_ij – D_ij] = min [L_j – D_ij]

 

3.       Determination of floats and slack times

 

 

There are three kinds of floats

 

• Total float – The amount of time by which the completion of an activity could be delayed beyond the earliest expected completion time without affecting the overall project duration

Mathematically

(Tf)_ij = (Latest start – Earliest start) for activity ( i – j) (Tf)_ij = (Ls)_ij – (Es)_ij or (Tf)_ij = (L_j – D_ij) – E_i

 

• Free float – The time by which the completion of an activity can be delayed beyond the earliest finish time without affecting the earliest start of a subsequent activity.

Mathematically

(Ff)_ij = (Earliest time for event j – Earliest time for event i) – Activity time for ( i,

j)

(Ff)_ij = (E_j – E_i) – D_ij

 

• Independent float – The amount of time by which the start of an activity can be delayed without effecting the earliest start time of any immediately following activities, assuming that the preceding activity has finished at its latest finish

Mathematically

(If)_ij = (E_j – L_i) – D_ij

The negative independent float is always taken as zero.

 

 

• Event slack – It is defined as the difference between the latest event and earliest event

Mathematically

Head event slack = L_j – E_j, Tail event slack = L_i – E_i

 

4.       Determination of critical path

 

• Critical event – The events with zero slack times are called critical events. In other words the event i is said to be critical if E_i = L_i

 

• Critical activity – The activities with zero total float are known as critical activities. In other words an activity is said to be critical if a delay in its start will cause a further delay in the completion date of the entire

 

• Critical path – The sequence of critical activities in a network is called critical path. The critical path is the longest path in the network from the starting event to ending event and defines the minimum time required to complete the

Exercise

1. What is PERT and CPM?

 

2. What are the advantages of using PERT/CPM?

 

3. Mention the applications of PERT/CPM

 

4. Explain the following terms

 

1. Earliest time

 

1. Latest time

 

1. Total activity slack

 

1. Event slack

 

1. Critical path

 

5. Explain the CPM in network

 

6. What are the rules for drawing network diagram? Also mention the common errors that occur in drawing
7. What is the difference between PERT and CPM/

 

 

8. What are the uses of PERT and CPM?

 

9. Explain the basic steps in PERT/CPM

 

10. Write the framework of PERT/CPM.

 

 

 

 

 

 

 

 

 

 

 

Unit 3

• Worked Examples on CPM
• PERT
• Worked Examples

 

 

3.1  Worked Examples on CPM

 

 

Example 1

Determine the early start and late start in respect of all node points and identify critical path for the following network.

 

 

 

 

 

Solution

Calculation of E and L for each node is shown in the network

 

 

 

 

Activity(i, j)	Normal Time (Dij)	Earliest Time		Latest Time		Float Time (Li – Dij ) – Ei
		Start (Ei)	Finish (Ei + Dij )	Start (Li – Dij )	Finish (Li)
(1, 2)	10	0	10	0	10	0
(1, 3)	8	0	8	1	9	1
(1, 4)	9	0	9	1	10	1
(2, 5)	8	10	18	10	18	0
(4, 6)	7	9	16	10	17	1

 

 

(3, 7) (5, 7) (6, 7) (5, 8) (6, 9) (7, 10) (8, 10) (9, 10)

16 7 7 6 5 12 13 15

8 18 16 18 16 25 24 21

24 25 23 24 21 37 37 36

9 18 18 18 17 25 24 22

25 25 25 24 22 37 37 37

1 0 2 0 1 0 0 1

Network Analysis Table

 

 

From the table, the critical nodes are (1, 2), (2, 5), (5, 7), (5, 8), (7, 10) and (8, 10)

 

 

From the table, there are two possible critical paths i.       1 → 2 → 5 → 8 → 10

1. 1 → 2 → 5 → 7 → 10

 

 

Example 2

Find the critical path and calculate the slack time for the following network

 

 

 

 

Solution

 

 

The earliest time and the latest time are obtained below

 

 

Activity(i, j)	Normal Time (Dij)	Earliest Time		Latest Time		Float Time (Li – Dij ) – Ei
		Start (Ei)	Finish (Ei + Dij )	Start (Li – Dij )	Finish (Li)
(1, 2)	2	0	2	5	7	5
(1, 3)	2	0	2	0	2	0
(1, 4)	1	0	1	6	7	6
(2, 6)	4	2	6	7	11	5
(3, 7)	5	2	7	3	8	1
(3, 5)	8	2	10	2	10	0
(4, 5)	3	1	4	7	10	6
(5, 9)	5	10	15	10	15	0
(6, 8)	1	6	7	11	12	5
(7, 8)	4	7	11	8	12	1
(8, 9)	3	11	14	12	15	1

 

From the above table, the critical nodes are the activities (1, 3), (3, 5) and (5, 9)

 

 

 

 

The critical path is 1 → 3 → 5 → 9

 

 

Example 3

A project has the following times schedule

 

 

Activity	Times in weeks	Activity	Times in weeks
(1 – 2) (1 – 3) (2 – 4) (3 – 4) (3 – 5) (4 – 9) (5 – 6)	4 1 1 1 6 5 4	(5 – 7) (6 – 8) (7 – 8) (8 – 9) (8 – 10) (9 – 10)	8 1 2 1 8 7

 

Construct the network and compute

1. T_E and T_L for each event
2. Float for each activity
3. Critical path and its duration

 

 

Solution

 

 

The network is

 

 

 

 

Event No.:	1	2	3	4	5	6	7	8	9	10
TE:	0	4	1	5	7	11	15	17	18	25
TL:	0	12	1	13	7	16	15	17	18	25

 

 

Float = T_L (Head event) – T_E (Tail event) – Duration

 

 

Activity	Duration	TE (Tail event)	TL (Head event)	Float
(1 – 2) (1 – 3) (2 – 4) (3 – 4) (3 – 5) (4 – 9) (5 – 6) (5 – 7) (6 – 8) (7 – 8) (8 – 9) (8 – 10) (9 – 10)	4 1 1 1 6 5 4 8 1 2 1 8 7	0 0 4 1 1 5 7 7 11 15 17 17 18	12 1 13 13 7 18 16 15 17 17 18 25 25	8 0 8 11 0 8 5 0 5 0 0 0 0

 

The resultant network shows the critical path

 

 

 

The two critical paths are

1. 1 → 3 → 5 →7 → 8 → 9 →10
2. 1 → 3 → 5 → 7 → 8 →10

 

 

3.2   Project Evaluation and Review Technique (PERT)

 

 

The main objective in the analysis through PERT is to find out the completion for a particular event within specified date. The PERT approach takes into account the uncertainties. The three time values are associated with each activity

 

1. Optimistic time – It is the shortest possible time in which the activity can be finished. It assumes that every thing goes very well. This is denoted by t₀.
2. Most likely time – It is the estimate of the normal time the activity would take. This assumes normal delays. If a graph is plotted in the time of completion and the frequency of completion in that time period, then most likely time will represent the highest frequency of occurrence. This is denoted by t_m.
3. Pessimistic time – It represents the longest time the activity could take if everything goes As in optimistic estimate, this value may be such that

 

 

only one in hundred or one in twenty will take time longer than this value. This is denoted by t_p.

 

In PERT calculation, all values are used to obtain the percent expected value.

 

 

1. Expected time – It is the average time an activity will take if it were to be repeated on large number of times and is based on the assumption that the activity time follows Beta distribution, this is given by

t_e = ( t₀ + 4 t_m + t_p ) / 6

 

2. The variance for the activity is given by

σ² = [(t_p – t_o) / 6] ²

 

3.3  Worked Examples

Example 1

For the project

 

 

 

 

 

Task:	A	B	C	D	E	F	G	H	I	J	K
Least time:	4	5	8	2	4	6	8	5	3	5	6

 

 

Greatest time:	8	10	12	7	10	15	16	9	7	11	13
Most likely time:	5	7	11	3	7	9	12	6	5	8	9

 

 

 

Find the earliest and latest expected time to each event and also critical path in the network.

Solution

 

Task	Least time(t0)	Greatest time (tp)	Most likely time (tm)	Expected time (to + tp + 4tm)/6
A B C D E F G H I J K	4 5 8 2 4 6 8 5 3 5 6	8 10 12 7 10 15 16 9 7 11 13	5 7 11 3 7 9 12 6 5 8 9	5.33 7.17 10.67 3.5 7 9.5 12 6.33 5 8 9.17

 

 

Task	Expected time (te)	Start		Finish		Total float
		Earliest	Latest	Earliest	Latest
A B C D E	5.33 7.17 10.67 3.5 7	0 0 5.33 0 16	0 8.83 5.33 10 16	5.33 7.17 16 3.5 23	5.33 16 16 13.5 23	0 8.83 0 10 0

 

 

F G H I J K

9.5 12 6.33 5 8 9.17

3.5 3.5 23 23 28 29.33

13.5 18.5 23 25.5 30.5 29.33

13 15.5 29.33 28 36 31.5

23 30.5 29.33 30.5 38.5 38.5

10 15 0 2.5 2.5 0

 

The network is

 

 

 

The critical path is A →C →E → H → K

 

 

Example 2

A project has the following characteristics

 

Activity	Most optimistic time (a)	Most pessimistic time (b)	Most likely time (m)
(1 – 2) (2 – 3) (2 – 4)	1 1 1	5 3 5	1.5 2 3

 

 

(3 – 5) (4 – 5) (4 – 6) (5 – 7) (6 – 7) (7 – 8) (7 – 9) (8 – 10) (9 – 10)

3 2 3 4 6 2 5 1 3

5 4 7 6 8 6 8 3 7

4 3 5 5 7 4 6 2 5

Construct a PERT network. Find the critical path and variance for each event.

 

Solution

 

Activity	(a)	(b)	(m)	(4m)	te (a + b + 4m)/6	v [(b – a) / 6]2
(1 – 2) (2 – 3) (2 – 4) (3 – 5) (4 – 5) (4 – 6) (5 – 7) (6 – 7) (7 – 8) (7 – 9) (8 – 10) (9 – 10)	1 1 1 3 2 3 4 6 2 5 1 3	5 3 5 5 4 7 6 8 6 8 3 7	1.5 2 3 4 3 5 5 7 4 6 2 5	6 8 12 16 12 20 20 28 16 24 8 20	2 2 3 4 3 5 5 7 4 6.17 2 5	4/9 1/9 4/9 1/9 1/9 4/9 1/9 1/9 4/9 1/4 1/9 4/9

 

 

The network is constructed as shown below

 

 

 

 

 

The critical path = 1 → 2 → 4 → 6 → 7 →9 →10

 

Example 3

 

Calculate the variance and the expected time for each activity

 

 

Solution

 

Activity	(to)	(tm)	(tp)	te (to + tp + 4tm)/6	v [(tp – to) / 6]2
(1 – 2) (1 – 3) (1 – 4)	3 6 7	6 7 9	10 12 12	6.2 7.7 9.2	1.36 1.00 0.69

 

 

(2 – 3) (2 – 5) (3 – 6) (4 – 7) (5 – 8) (6 – 7) (6 – 9) (8 – 9) (7 – 10) (9 – 11) (10 – 11)

0 8 10 8 12 8 13 4 10 6 10

0 12 12 13 14 9 16 7 13 8 12

0 17 15 19 15 10 19 10 17 12 14

0.0 12.2 12.2 13.2 13.9 9.0 16.0 7.0 13.2 8.4 12.0

0.00 2.25 0.69 3.36 0.25 0.11 1.00 1.00 1.36 1.00 0.66

 

 

Example 4

 

A project is represented by the network as shown below and has the following data

 

 

 

Task:	A	B	C	D	E	F	G	H	I
Least time:	5	18	26	16	15	6	7	7	3

 

 

Greatest time:	10	22	40	20	25	12	12	9	5
Most likely time:	15	20	33	18	20	9	10	8	4

 

Determine the following

 

1. Expected task time and their variance

 

2. Earliest and latest time

 

 

 

Solution

 

 

 

 

 

 

 

 

 

1.

 

Activity	Least time (t0)	Greatest time (tp)	Most likely time (tm)	Expected time (to + tp + 4tm)/6	Variance (σ2)
(1-2) (1-3) (1-4) (2-5) (2-6) (3-6) (4-7) (5-7) (6-7)	5 18 26 16 15 6 7 7 3	10 22 40 20 25 12 12 9 5	8 20 33 18 20 9 10 8 4	7.8 20.0 33.0 18.0 20.0 9.0 9.8 8.0 4.0	0.69 0.44 5.43 0.44 2.78 1.00 0.69 0.11 0.11

 

 

 

 

2.

 

Earliest time

 

E₁ = 0

 

E₂ = 0 +7.8 = 7.8

 

E₃ = 0 +20 = 20

 

E₄ = 0 +33 = 33

 

E₅ = 7.8 + 18 = 25.8

 

E₆ = max [7.8 + 20, 20 + 9] = 29

 

E₇ = max [33 + 9.8, 25.8 + 8, 29 + 4] = 42.8

 

Latest time

 

L₇ = 42.8

 

L₆ = 42.8 – 4 = 38.8

 

L₅ = 42.8 – 8 = 34.3

 

L₄ = 42.8 – 9.8 = 33

 

L₃ = 38.8 – 9 = 29.8

 

L₂ = min [34.8 – 18, 38.8 – 20] = 16.8

 

L₁ = min [16.8 – 7.8, 29.8 – 20, 33 – 33] = 0

 

 

 

Exercise

 

 

1. What is PERT?

 

2. For the following data, draw network. Find the critical path, slack time after calculating the earliest expected time and the latest allowable time

 

 

 

Activity	Duration	Activity	Duration
(1 – 2) (1 – 3) (2 – 4) (2 – 5) (2 – 6) (3– 7) (3 – 8) (4 – 9)	5 8 6 4 4 5 3 1	(5 – 9) (6 – 10) (7 – 10) (8 – 11) (9 – 12) (10 – 12) (11 – 13) (12 – 13)	3 5 4 9 2 4 1 7

 

[Ans. Critical path: 1 → 3 → 7 → 10 → 12 →13]

 

3. A project schedule has the following characteristics

 

Activity	Most optimistic time	Most likely time	Most pessimistic time
(1 – 2) (2 – 3) (2 – 4) (3 – 5) (4 – 5) (4 – 6) (5 – 7) (6 – 7) (7 – 8)	1 1 1 3 2 3 4 6 2	2 2 3 4 5 5 5 7 4	3 3 5 5 4 7 6 8 6

 

 

(7 – 9) (8 – 10) (9 – 10)

4 1 3

6 2 5

8 3 7

 

 

Construct a PERT network and find out

1. The earliest possible time
2. Latest allowable time
3. Slack values
4. Critical path

4. Explain the following terms
   1. optimistic time
   2. Most likely time
   3. Pessimistic time
   4. Expected time
   5. Variance
5. Calculate the variance and the expected time for each activity

 

 

 

 

UNIT-IV

Replacement Model:

Replacement of Items that deteriorate whose maintenance costs increase with time without change in the money value.

Replacement of items that fail suddenly:

individual replacement policy,

group replacement policy.

Inventory Models:

Models with deterministic demand model

(a) demand rate uniform and production rate infinite, model

(b) demand rate non-uniform and production rate infinite, model

(c) demand rate uniform and production rate finite.

      REPLACEMENT  MODELS

INTRODUCTION

The problem of replacement is felt when the job performing units such as men, machines, equipments, parts etc. become less effective or useless due to either sudden or gradual deterioration in their efficiency, failure or breakdown. By replacing them with new ones at frequent intervals, maintenance and other overhead costs can be reduced. However, such replacements would increase the need of capital cost for new ones.

For example,

1. A vehicle tends to wear out with time due to constant use. More money needs to be spent on it on account of increased repair and operating cost. A stage comes when it becomes uneconomical to maintain the vehicle and it is better to replace it with a new one. Here the replacement decision may be taken to balance the increasing maintenance cost with the decreasing money value of the vehicle as time
2. In case of highway tubelights where time of failure is not predictable for individual tubes, replacement is done only after individual failure. However, it may be economical to replace such tubes on a schedule basis before their failure. Here the replacement decision may be taken to balance between the wasted life of a tube before failure and cost incurred when a tube fails completely during

Thus, the basic problem in such situations is to formulate a replacement policy to determine an age (or period) at which the replacement of the given machinery/equipment is most economical keeping in view all possible alternatives.

In this chapter, we shall discuss the replacement policies in the context of the following three types of replacement situations:

1. Items such as machines, vehicles, tyres etc. whose efficiency deteriorates with age due to constant use and which need increased operating and maintenance costs. In such cases deterioration level is predictable and is represented by a. Increased maintenance/operational cost, its waste or scrap value and damage to item and safety risk.
2. Items such as light bulbs and tubes, electric motors, radio, television parts etc. which do not give any indication of deteriorations with time but fail all of a sudden and become completely useless. Such cases require an anticipation of failures to specify the probability of failure for any future time With this probability distribution and the cost information, it is desired to formulate optimal, replacement policy to balance the wasted life of an item replaced before failure against the costs incurred when the item fail in service.
3. The existing working staff in an organisation gradually reduces due to retirement, death, retrenchment and other

 

TYPES OF FAILURE

The term ‘failure’ here will be discussed in the context of replacement decisions. There are two types of failures: 1. Gradual failure and 2. Sudden failure.

Gradual Failure

Gradual Failure is progressive in nature. That is, as the life of an item increases its  operational efficiency also deteriorates resulting in

• increased running (maintenance and operating)
• decrease in its

 

• decrease in the resale or salvage

Mechanical items like pistons, rings, bearings etc., and automobile types fall under this category.

Sudden Failure

This type of failure occurs in items after some period of giving desired service rather than deterioration while in service. The period of desired service is not constant but follows some frequency distribution which may be progressive, retrogressive or random in nature.

1. Progressive Failure: If the probability of failure of an item increases with the increase in its life, then such failure is called progressive failure. For example, light bulbs and tubes fail progressively.
2. Retrogressive Failure: If the probability of failure in the beginning of the life of an item is more but as time passes the chances of its failure becomes less, then such failure is said to be
3. Random Failure: In this type of failure, the constant probability of failure is associated with items that fail from random cases such as physical shocks, not related to age. For example, vacuum tubes in air-born equipment have been found to fail at a rate independent of the age of the

 

REPLACEMENT OF ITEMS WHOSE EFFICIENCY DETERIORATES WITH TIME

When operational efficiency of an item deteriorates with time (gradual failure), it is economical to replace the same with a new one. For example, the maintenance cost of a machine increases with time and a stage is reached when it may not be economical to allow machine to continue in the system. Besides, there could be a number of alternative choices and one may like to compare available alternatives on the basis of the running costs (average maintenance and operating costs) involved. In this section, we shall discuss various techniques for making such comparisons under different conditions. While making such comparisons it is assumed that suitable expressions for running costs are available.

 

Model 1 Replacement Policy for items Whose Running Cost Increases with Time and Value of Money Remains Constant During a Period

Theorem 1

The cost of maintenance of a machine is given as a function increasing with time and its scrap value is constant.

1. If time is measured continuously, then the average annual cost will be minimised by replacing the machine when the average cost to date becomes equal to the current maintenance cost.
2. If time is measured in discrete units, then the average annual cost will be minimised by replacing the machine when the next period’s maintenance cost becomes greater than the current average

PROOF: The aim here is to determine the optimal replacement age of an equipment whose running cost increases with time and the value of money remains constant (i.e. value is not counted) during that period.

Let C = capital or purchase cost of new equipment

S = Scrap (or salvage) value of the equipment at the end of t years

 

R(t) = running cost of equipment for the year t n = replacement age of the equipment.

1. When time ‘t’ is a continuous variable: If the equipment is used for t years, then the total cost incurred over this period is given by

TC = Capital (or purchase) cost – Scrap value at the end of t years + Running cost for t years.

 

= C – S +

∫𝑛 𝑅(𝑡)𝑑𝑡

 

0

0

Therefore, the average cost per unit time incurred over the period of n years is:

 

ATCn  = 1

𝑛

C – S +

∫𝑛 𝑅(𝑡)𝑑𝑡

———————— (1)

 

 

To obtain optimal value n for which ATCn is minimum, differentiate ATCn with respect to n, and set the first derivative equal to zero. That is, for minimum of ATCn.

 

^𝑑 {ATC } = – ¹

 

{C – S} + 𝑅 (𝑛) – 1

 

^𝑛 (𝑡)𝑑𝑡 = 0

 

0

𝑑𝑛

n           𝑛2

𝑛             𝑛2 ∫0

 

or R (n) = ¹

𝑛

R (n) = ATCn

C – S +

∫𝑛 𝑅(𝑡)𝑑𝑡

, n≠0—————- (2)

 

Hence, the following replacement policy can be derived with help of Eq. 2.

Policy

Replace the equipment when the average annual cost for n years becomes equal to the current

/annual running cost. That is,

 

 

R (n) =

C – S +

∫𝑛 𝑅(𝑡)𝑑𝑡

 

 

0

𝑡=0

1. When time ‘t’ is a discrete variable: The average cost incurred over the period n is given by

 

ATCn  = 1

𝑛

C – S + ∑^𝑛

𝑅 (𝑡)

—————————-(3)

 

 

 

𝑡=0

If C – S and ∑^𝑛

𝑅 (𝑡)

are assumed to be monotonically decreasing and increasing

 

respectively, then there will exist a value of n for which ATCn is minimum. Thus we shall have inequalities

ATCn – 1 > ATCn < ATCn+1 or ATCn – 1 – ATCn > 0

and ATCn+1 – ATCn > 0

𝑡=1

𝑡=1

Eq. (3) for period n + 1, we get

 

ATCn = 1

𝑛+1

C – S + ∑^𝑛=0 𝑅 (𝑡)     =

C – S + ∑^𝑛=0 𝑅 (𝑡) + R (n + 1)

 

 

 

𝑛 C − S + ∑𝑛 𝑅 (𝑡)

𝑅 (𝑛+1)                𝑛

𝑅 (𝑛+1)

 

=                    𝑡=0                +

=         . ATCn +

 

𝑛+1                          𝑛

Therefore,

𝑛+1

𝑛+1

𝑛+1

 

ATCn+1 – ATCn = 𝑛

ATCn + 𝐴 (𝑛+1) – ATCn = 𝑅 (𝑛+1) + ATCn [

– 1] = 𝑅 (𝑛+1) – ATCn

 

𝑛+1

𝑛+1

𝑛+1

𝑛+1

𝑛+1

𝑛+1

 

Since ATCn+1 – ATCn > 0, we get

𝑅 (𝑛+1) – ATCn > 0

𝑛+1               𝑛+1

 

R (n + 1) – ATCn  > 0 or R (n + 1) > ATCn—————————————- (4)

Similarly,

ATCn – 1 – ATCn > 0, implies that R (n + 1) < ATCn – 1. This provides the following replacement policy.

 

𝑡=0

Policy 1: If the next year, running cost R(n + 1) is more than average cost of nth year, ATCn, then it is economical to replace at the end of n years. That is

 

R (n + 1) >  1

𝑛

C – S + ∑^𝑛

𝑅 (𝑡)

 

 

Policy 2: If the present year’s running cost is less than the previous year’s average cost, ATCn

– 1, then do not replace. That is

𝑡=0

R (n) <          C – S + ∑^𝑛−1 𝑅 (𝑡)

 

EXAMPLE

A firm is considering replacement of a machine, whose cost price is Rs. 12, 200 and scrap value is Rs. 200. The running (maintenance and operating) costs are found from experience to be as follows:

Year	1	2	3	4	5	6	7	8
Running cost (Rs.)	200	500	800	1200	1800	2500	3200	4000

When should the machine be replaced?

 

Solution: We are given the running cost, R(n), the scrape value S – Rs. 200 and the cost of the machine, C = Rs. 12, 200. In order to determine the optimal time n when the machine should be replaced, first we calculate average cost per year during the life of the machine as shown in table below:

TABLE

Year of Service n	Running Cost (Rs.) R(n)	Cumulative Running Cost (Rs.) Ʃ R(n)	Depreciation Cost (Rs.) C – S	Total Cost (Rs.) TC	Average Cost (Rs.) ATCn
1	2	3	4	5 = 3 + 4	6 = 5/1
1 2 3 4 5 6 7 8	200 500 800 1200 1800 2500 3200 4000	200 700 1500 2700 4500 7000 10200 14200	12000 12000 12000 12000 12000 12000 12000 12000	12, 200 12, 700 13, 500 14, 700 16, 500 19, 000 22, 200 26, 200	12, 200 6350 4500 3675 3300 3167 3171 3275

From the table, it may be noted that the average cost per year, ATCn is minimum in the sixth year (Rs. 3, 167). Also the average cost in the seventh year (Rs. 3171) is more than the cost in the sixth year. Hence, the machine should be replaced after every six years.

 

• The data collected in running a machine, the cost of which is 60, 000 are given below:

 

Year	1	2	3	4	5
Resale Value (Rs.)	42, 000	30, 000	20, 400	14, 400	9, 650
Cost of Spares (Rs.)	4, 000	4, 270	4, 880	5, 700	6, 800
Cost of Labour (Rs.)	14, 000	16, 000	18, 000	21, 000	25, 000

Determine the optimum period for replacement of the machine.

 

Solution: The costs of spares and labour together determine running (operational or maintenance) cost. Thus, the running costs and the resale price of the machine in successive years are as follows:

Year:	1	2	3	4	5
Resale Value (Rs.)	42, 000	30, 000	20, 400	14, 400	9, 650
Running Cost (Rs.)	18, 000	20, 270	22, 880	26, 700	31, 800

The calculations of average running cost per year during the life of the machine are shown in table 1.

Year of Service n	Running Cost (Rs.) R(n)	Cumulative Running Cost (Rs.) Ʃ R(n)	Resale Value (Rs.) S	Depreciation Cost (Rs.) C – S	Total Cost (Rs.) TC	Average Cost (Rs.) ATCn
1	2	3	4	5 = 60, 000	6 = 3 + 5	7 = 6/1
1 2 3 4 5	18, 000 20, 270 22, 880 26, 700 31, 800	18, 000 38, 270 61, 150 87, 850 1, 19, 650	42, 000 30, 000 20, 400 14, 400 9, 650	18, 000 30, 000 39, 600 45, 600 50, 350	36, 000 68, 270 1, 00, 750 1, 33, 450 1, 70, 000	36, 000.00 34, 135.00 33, 583.00 33, 362.00 34, 000.00

The calculations in table 1 reveal that the average cost is lowest during the fourth year. Hence, the machine should be replaced after every fourth year, otherwise the average cost per year for running the machine would start increasing.

 

REPLACEMENT OF ITEMS THAT FAIL COMPLETELY

It is somehow difficult to predict that a particular equipment will fail at a particular time. This uncertainty can be avoided by deriving the probability distribution of failures. Here, it is assumed that the failures occur only at the end of the period, say t. Thus, the objective becomes to find the value of t which minimises the total cost involved for the replacement.

 

Mortality Tables: These tables are used to derive the probability distribution of life span of an equipment in question. Let

M (f)                = Number of survivors at any time t M(t – 1)                            = Number of survivors at any time t – 1 N         = Initial number of equipments

Then the probability of failure during time period t is given by

P (t) = (𝑡−1)− 𝑀(𝑡)

𝑁

The probability that an equipment has survived to an age (t – 1). and will fail during the interval (t – 1) to t can be defined as the conditional probability of failure. It is given by

Pc (t) = (𝑡−1)− 𝑀(𝑡)

(𝑡−1)

 

The probability of survival to an age t is given by

Ps(t) = 𝑀(𝑡)

𝑁

Mortality Theorem 1: A large population is subject to a given mortality law for a very long period of time. All deaths are immediately replaced by births and there are no other entries or exits. Show that the age distribution ultimately becomes stable and that the number of deaths per unit time becomes constant and is equal to the size of the total population divided by the mean age at death.

Proof: Without any loss of generality, it is assumed that death (or failure) occurs just before the age of (k + 1) years, where k is an integer. That is, life span of an item lies between t = 0 and t = k. Let us define f(t) = number of births (replacements) at time t, and

p(x) = probability of death (failure) just before the age x + 1, i.e. failure at time x.

 

and ∑

𝑘

𝑥=0

(𝑥) = 1

 

If f(t – x) represents the number of births at time t – x, t = k, k +1, k + 2,….then the age of newly borns attain the age x at time t illustrated in the figure below:

 

Age	0	x		x + 1
Time	t – x		t	t + 1

 

Hence the expected number of deaths of such newly borns before reaching the time t + 1 (i.e. at time t) will be

𝑥=0

Expected number of death =  ∑^𝑘    𝑝(𝑥)f(t – x), t = k, k + 1, …..

Since all deaths (failures) at time t are replaced immediately by births (replacements) at time t

+ 1, expected number of births are:

𝑥=0

f(t + 1) = ∑^𝑘    𝑝(𝑥)f(t – x), t = k, k + 1, …..                                                              (1)

The solution to the difference Eq. (9) in t can be obtained by putting the value f(t) = Aα^‘, where A is some constant. Then Eq. (9) becomes

𝑥=0

Aα^{t + 1} = A ∑^𝑘     (𝑥) α^{t – x}                                                                                            (2)

𝑥=0

Dividing both sides of Eq. (10) by Aα^{t – k}, we get

 

α          ∑=

k + 1         𝑘

𝑥=0

(𝑥) α^{k – x} = α^k ∑^𝑘

(𝑥) α^{– x}

 

= α^k {p (0) + p (1) α^-1 + p(2) α^-2 + }

or α^{k + 1} – {p (0) α^k + p (1) α^{k – 1} + p (2) α^{k – 2}} = 0                                                                     (3) Equation (3) is of degree (k + 1) and will, therefore, have exactly (k + 1) roots. Let us denote the roots of Eq. (3) by α0, α1, α2, , αk.

For α = 1, the L. H. S of equation (3), becomes

L.H.S = 1 – {p(0) + p (1) + p (2) + + p (w)}

 

= 1 – ∑

𝑤

𝑥=0

(𝑥) = 0 R. H.S

 

Hence, one root of Eq. (3) is α = 1. Let us denote this root by α0. The general solution of Eq.

• will then be of the form

f (t) = A0  α^t0  + A1 α^t1 +      + Ak α^tk

= A0  + A1 α^t1 +      + Ak α^tk

where A0, A1, A2, …. Ak  are constant whose values are to be calculated.                              (4)

 

Since one of the roots of Eq. (3), α0 = 1 is positive, according to the Descrae’s sign rule all other roots α1, α2, , αk will be negative and their absolute value is less than unity, i.e. |αi| <

1, i = 1, 2, 3, ….., k. It follows that the value of these roots tends to be zero as t   ∞. With the result that Eq. (4) becomes f(t) = A0. This indicates that the number of deaths (as well as births) becomes constant at any time.

Now the problem is to determine the value of the constant A0. For this we can proceed as follows:

Let us define

g (x) = Probability of survival for more than x years.

or g (x) = 1 – Prob (survivor will die before attaining the age x)

= 1 – {p(0) + p(1) +     p(x -1)}

Obviously, it can be assumed that g(0) = 1.

Since the number of births as well as deaths has become constant and equal to A0, expected number of survivors of age x is given by A0 . g(x).

As deaths are immediately replaced by births, size N of the population remains constant. That is,

 

𝑥=0

N = A0 ∑𝑘

Or

A0 =      𝑁

(𝑥) α1, α2,…….. , αk

 

…………     (4)

 

∑

𝑘

𝑥=0

𝑔(𝑥)

 

The denominator in Eq. (4) represents the average age at death. This can also be proved as follows:

From finite differences, we know that

∆(x) = (x + 1) – x = 1

 

∑

𝑏

𝑥=𝑎

(𝑥) ∆ℎ(x) = f (b + 1) h(b + 1) – f (a) h(a) – ∑^𝑏

(𝑥 + 1) ∆𝑔(x)

 

𝑥=𝑎

𝑥=0

= g (k + 1) (k + 1) – g (0) . 0 – ∑^𝑘     (𝑥 + 1) ∆𝑔(x)

𝑥=0

= g (k + 1) (k + 1) – ∑^𝑘    (𝑥 + 1) ∆𝑔(x)…………… (5)

But g (k + 1) = 1 – {p(0) + p(1) + p(2) +          + p(k)} = 0

since no one can survive for more than (k + 1) years of age and

∆𝑔(x) = g(x + 1) – g(x)

= {1 – p(0) – p(1) – …… – p(x)} – {1 – p(0) – p(1)       p(x – 1)} = – p(x)

Substituting the value of g(k + 1) and ∆𝑔(x) in Eq. (5), we get

 

∑

𝑘

𝑥=0

𝑔(𝑥) = ∑^𝑘

(𝑥 + 1)p (x) = Mean age at death

 

𝑥=0

Hence from Eq. (4), we get

A0 =               𝑁                             .

𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑎𝑔𝑒 𝑎𝑡 𝑑𝑒𝑎𝑡ℎ

 

 

STAFFING PROBLEM

The principles of replacement may be applied to formulate some useful recruitment and promotion policies for the staff working in the organisation. For this, we assume that life distribution for the services of staff in the organisation is already known.

Example 1:

 

An airline requires 200 assistant hostesses, 300 hostesses and 50 supervisors. Women are recruited at the age of 21, and if still in service retire at 60. Given the following life table, determine

• How many women should be recruited in each year?
• At what age should promotion take place?

Airline Hostesses’ Life Record

Age No.    in Servie	21 1000	22 600	23 480	24 384	25 307	26 261	27 228	28 206
Age No.    in Servie	29 190	30 181	31 173	32 167	33 161	34 155	35 150	36 146
Age No.    in Servie	37 141	38 136	39 131	40 125	41 119	42 113	43 106	44 99
Age No.    in Servie	45 93	46 87	47 80	48 73	49 66	50 59	51 53	52 46
Age No.    in Servie	53 39	54 33	55 27	56 22	57 18	58 14	59 11	—

Solution: If 1000 women had been recruited each year for the past 39 years, then the total number of them recruited at the age of 21 and those serving upto the age of 59 is 6, 480. Total number of women recruited in the airline are: 200 + 300 + 50 = 550.

• Number of women to be recruited every year in order to maintain a strength of 55 hostesses 550 x (1000/6840) = 85 approx.
• If the assistant hostesses are promoted at the age of x, then up to age (x – 1), 200 assistant hostesses will be Among 550 women, 200 are assistant hostesses. Therefore, out of a strength of 1, 000 there will be: 200 x (1000/550) = 364 assistant hostesses. But, from the life table given in the question, this number is available upto the age of 24 years. Thus, the promotion of assistant hostesses is due in the 25th year.

Since out of 550 recruitments only 300 hostesses are needed, if 1, 000 girls are recruited, then only 1000 x (300/550) = 545 approx will be hostesses. Hence, total number of hostesses and assistant hostesses in a recruitment will be: 545 + 364 = 909. This means, only 1000 – 909 = 91 supervisors are required. But from life table this number is available up to the age of 46 years. Thus promotion of hostesses to supervisors will be due in 47th year.

 

QUESTIONS

1. In the theory of replacement models construct an equation for the cost of maintaining a system as a function of the control variable t (the number of periods between group replacements).
2. State some of the simple replacement policies and give the average cost functions for the same explaining your
3. The cost of maintenance of a machine is given as a function that the average annual cost will be minimised by replacing the machine when the average cost to date becomes equal to the current maintenance
4. Discuss the importance of replacement
5. Explain how the theory of replacement is used in the following

• Replacement of items whose maintenance cost varies with
• Replacement of items that fail

6. Find the cost per period of individual replacement of an installation of 300 lighting bulbs, given the following

(a) cost of replacing individual bulb is Rs. 3

(b) Conditional probability of failure is given below:
Week Number                                                 :		0	1	2	3	4
Conditional Probability of Failure                   :		0	1/10	1/3	2/3	1
7. The following mortality rates have been observed for a special type of light bulbs.
Month                                                 :	1	2	3	4	5
% failing at the end of the month       :	10	25	50	80	100

In an industrial unit there are 1,000 special type of bulbs in use, and it costs Rs.10 to replace an individual bulb which has burnt out. If all bulbs were replaced simultaneously it would cost Rs. per bulb. It is proposed to replace all bulbs at fixed intervals, whether or not they have burnt out, and to continue replacing burnt out bulbs as they fail. At what intervals of time should the manager replace all the bulbs?

8. An airline, whose staff are subject to the same survival rates as in the previous problem, currently has a staff whose ages are distributed in the following table. It is estimated that for the next two years staff requirements will increase by 10% per If women are to be recruited at the age of 21, how many should be recruited for the next year and at what age will promotions take place? How many should be recruited for the following year and at what age will promotions take place?

 

Assistant Age Number	21 90	22 50	23 30	24 20	25 10		(Total 200)
Hostesses	26	27	28	29	30	31	32	33	34
Age	40	35	35	30	28	26	20	18	16
Number
Age	35	36	37	38	39	40	41
Number	12	10	8	—	8	8	6
							(Total
							300)
Supervisors
Age	42	43	44	45	46	47	48	49	50
Number	5	4	5	3	3	3	6	2	—
Age	51	52	53	54	55	56	57	58	59
Number	—	4	3	5	—	3	2	—	2
									(Total
									50)

 

 

 

 

 

INVENTORY MODELS

 

INTRODUCTION

Inventory is one of the most expensive and important assets of many companies, representing as much as 50% of total invested capital. Managers have long recognised that good inventory control is crucial. On one hand, a firm can try to reduce costs by reducing on-hand inventory levels. On the other hand, customers become dissatisfied when frequent inventory outages, called stock outs occur. Thus, companies must make the balance between low and high inventory levels. As you would expect, cost minimisation is the major factor in obtaining this delicate balance.

Inventory is any stored resource that is used to satisfy a current or future need. Raw materials, work-in-progress, and finished goods are examples of inventory. Inventory levels for finished goods, such as clothes dryers, are a direct function of market demand. By using this demand information, it is possible to determine how much raw materials (eg., sheet metal, paint, and electric motors in the case of clothes dryers) and work-in-processes are needed to produce the finished product.

Every organisation has some type of inventory planning and control system. A bank has methods to control its inventory of cash. A hospital has methods to control blood supplies and other important items. State and federal governments, schools, and virtually every manufacturing and production organisation are concerned with inventory planning and control. Studying how organisations control their inventory is equivalent to studying how they achieve their objectives by supplying goods and services to their customers. Inventory is the common thread that ties all the functions and departments of the organisation together.

Figure 4.1 illustrates the basic components of inventory planning and control system. The planning phase involves primarily what inventory is to be stocked and how it is to  be acquired (whether it is to be manufactured or purchased). This information is then used in forecasting the demand for the inventory and in controlling inventory levels. The feedback loop in figure 4.1 provides a way of revising the plan and forecast based on experiences and observation.

Through inventory planning, an organisation determines what goods and/or services are to be produced. In cases of physical products, the organisation must also determine whether to produce these goods or to purchase them from another manufacturer. When this has been determined, the next step is to forecast the demand. Many mathematical techniques can be used in forecasting demand for a particular product. The emphasis in this chapter is on inventory control – that is, how to maintain adequate inventory levels within an organisation to support a production or procurement plan that will satisfy the forecasted demand.

In this chapter, we discuss several different inventory control models that are commonly used in practice. For each model, we provide examples of how they are analysed. Although we show the equations needed to compute the relevant parameters for each model, we use EXCEL worksheets to actually calculate these values.

 

IMPORTANCE OF INVENTORY CONTROL

Inventory control serves several important functions and adds a great deal of flexibility to the operation of a firm. Five main uses of inventory are as follows:

1. Decoupling function
2. Storing resources

 

3. Irregular supply and demand
4. Quantity discounts
5. Avoiding stockouts and

Figure 4.1 Inventory Planning and Control

 

 

 

Planning on what inventory to Stock and how to acquire it.

Forecasting Parts/Product Demand

Controlling Inventory Levels

 

 

 

 

 

Feedback Measurements to revise Plans and Forecasts

 

 

1.  Decoupling Function

One of the major functions of the inventory is to decouple manufacturing processes within the organisation. If a company did not store inventory, there could be many delays and inefficiencies. For example, when one manufacturing activity has to be completed before a second activity can be started, it could stop the entire process. However, stored inventory between processes could act as a buffer.

2.  Storing Resources

Agricultural and seafood products often have definite seasons over which they can be harvested or caught, but the demand for these products is somewhat constant during the year. In these and similar cases, inventory could be used to store these resources.

In manufacturing process, raw materials can be stored by themselves, as work-in-process, or as finished products. Thus, if your company makes lawn movers, you may obtain  lawn mower tyres from another manufacturer. If you have 400 finished lawn movers and 300 tyres in inventory, you actually have 1, 900 tyres stored in inventory. 300 tyres are stored by themselves, and 1, 600 ( = 4 tyre per lawn mower X 400 lawn movers) tyres are stored on the finished lawn mowers. In the same sense, labour can be stored in inventory. If you have 500 subassemblies and it takes 50 hours of labour to produce each assembly, you actually have 25, 000 labour hours stored in inventory in the subassemblies. In general, any resource, physical or otherwise can be stored in inventory.

3.  Irregular supply and demand

When the supply and demand for the inventory item is irregular, storing certain amount as inventory can be important. If the greatest demand for Diet-Delight beverage is during the summer, the Diet-Delight company will have to make sure that there is enough supply to meet this irregular demand. This might require that the company produce more of the soft drink in the winter than is actually needed in order to meet the winter demand. The inventory levels of Diet-Delight will gradually build up over the winter, but this inventory will be needed in summer. The same is true for irregular supplies.

 

4.  Quantity Discounts

Another use of inventory is to take advantage of quantity discounts. Many suppliers offer discounts for larger orders. For example, an electric jigsaw might normally cost $10 per unit. If you order 300 or more saws at one time, your supplier may lower the cost to $8.75. Purchasing in larger quantities can substantially reduce the cost of products. There are, however, some disadvantages of buying in larger quantities. You will have higher storage costs and higher costs due to spoilage, damaged stock, theft, insurance, and so on. Furthermore, if you invest in more inventory, you will have less cash to invest elsewhere.

5.  Avoiding stockouts and shortages

Another important function in inventory is to avoid stockouts and shortages. If a company is repeatedly out of stock, customers are likely to go elsewhere to satisfy their needs. Lost goodwill can be an expensive price to pay for not having the right item at the right time.

 

INVENTORY CONTROL DECISIONS

Even though there are literally millions of different types of products manufactured in our society, there are only two fundamental decisions that you have to make when controlling inventory:

1. How much to order
2. When to order

Table 4.1 Inventory Cost Factors

Operating Cost Factors	Carrying Cost Factors
Developing and sending purchase orders Processing and inspecting incoming inventory Bill Paying Inventory Inquiries Utilities, phone bills, and so on for the purchasing department Salaries and wages for purchasing department employees Supplies such as forms and paper for the purchasing department	Cost of Capital Taxes Insurance Spoilage Theft Obsolescence Salaries and wages for warehouse employees Utilities and building costs for the warehouse Supplies such as forms and papers for the warehouse

The purpose of all inventory models is to determine  how much to order and when to order. As you know, inventory fulfils many important functions in an organisation. But as the inventory levels go up to provide these functions, the cost of holding and storing inventories also increases. Thus, we must reach a fine balance in establishing inventory levels. A major objective in controlling inventory is to minimise total inventory costs. Some of the most significant inventory costs are as follows:

1. Cost of the items
2. Cost of ordering
3. Cost of carrying or holding inventory
4. Cost of stockouts
5. Cost of safety stock, the additional inventory that may be held to help avoid

 

The inventory models discussed in the first part of this chapter assume that demand and the time it takes to receive an order are known and constant, and that no quantity discounts are given. When this is the case, the most significant costs are the cost of placing an order and the cost of holding inventory items over a period of time. Table 4.1 provides a list of important factors that make up these costs.

 

ECONOMIC ORDER QUANTITY: DETERMINING HOW MUCH TO ORDER

The Economic Order Quantity (EOQ) model is one of the oldest and most commonly known inventory control techniques. Research on its use dates back to a 1915 publication by Ford

1. Harris. This model is still used by a large number of organisations today. This technique is relatively easy to use, but it makes a number of assumptions. Some of the more important assumptions are as follows:

 

ASSUMPTIONS OF EOQ

1. Demand is known and
2. The lead time – that is, the time between the placement of the order and the receipt of the order – is known and
3. The receipt of inventory is In other words, the inventory from an order arrives in one batch, at one point in time.
4. Quantity discounts are not
5. The only variable costs are the cost of placing an order, ordering cost, and the cost of holding or storing inventory over time, carrying or holding
6. If orders are placed at the right time, stockouts and shortages can be completely avoided. With these assumptions, inventory usage has a sawtooth shape, as in Figure 4.2. Here, Q represents the amount that is If this amount is 500 units, all 500 units are arrived at one time when an order is received. Thus, the inventory level jumps from 0 to 500 units. In general, the inventory level increases from 0 to Q units when an order arrives.

Because demand is constant over time, inventory drops at a uniform rate over time. Another order is placed such that when the inventory level reaches 0, the new order is received and the inventory level again jumps to Q units, represented by the vertical lines. This process continues indefinitely over time.

 

 

 

ORDERING AND INVENTORY COSTS

The objective of most inventory models is to minimise the total cost. With the assumptions just given, the significant costs are the ordering costs and inventory carrying cost. All other costs, such as the cost of the inventory itself, are constant. Thus, if we minimise the sum of the ordering and carrying costs, we also minimise the total cost.

To help visualise this, Figure 4.3 graphs total cost as a function of the order quantity, Q. As the value of Q increases, the total number of orders placed per year decreases. Hence, the total ordering cost decreases. However as the value of Q increases, the carrying cost increases because the firm has to maintain larger average inventories.

The optimal order size, Q^*, is the quantity that minimises the total cost. Note in figure 12.3 that Q^* occurs at the point where the ordering cost curve and the carrying cost curve intersect. This is not by chance. With this particular type of cost function, the optimal quantity always occurs at a point where the ordering cost is equal to the carrying cost.

Figure 12.2 Inventory Usage Over time

 

 

Inventory Level

Q

Maximum

 

 

 

 

 

 

 

 

 

 

 

 

 

Time

 

Figure 4.3 Total Cost as a Function of Order Quantity

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Optimal Order Quantity (Q^*)                        Order Quantity in Units

Now that we have a better understanding of inventory costs, let us see how we can determine the value of Q^* that minimises the total cost. In determining the annual carrying cost, it is convenient to use the average inventory. Referring to figure 4.2, we see that the on-hand inventory ranges from a high of Q units to a low of zero units, with a uniform rate of decrease between these levels. Thus, the average inventory can be calculated as the average of the minimum and maximum inventory levels. That is,

Average Inventory = (0 +Q)/2 = Q/2————————— (1)

We multiply this average inventory by a factor called the annual inventory carrying cost per unit to determine the annual inventory cost.

 

FINDING THE ECONOMIC ORDER QUANTITY

We pointed out that the optimal order quantity, Q^*, is the point that minimises the total cost, where total cost is the sum of ordering cost and carrying cost. We also indicated graphically that the optimal order quantity was at the point where the ordering cost was equal to the carrying cost. Let us now define the following parameters:

Q^* = Optimal Order Quantity (i.e EOQ)

D = Annual Demand, in units, for the inventory item Co = Ordering cost per order

Ch = Carrying or holding cost per unit per year  P = Purchasing cost per unit of the inventory item

The unit carrying cost, Ch, is usually expressed in one of two ways, as follows:

1. As a fixed cost, for example, Ch is $0.50 per unit per

 

2. As a percentage (typically denoted by l) of the item’s unit purchase cost or price. For example, Ch is 20% of the item’s unit In general

Ch  = I X P                               (2)

For a given order quantity, Q, the ordering, holding and total costs can be computed using the following formulae:

Total Ordering Cost = (D/Q) x Co                                          (3)

Total Carrying Cost = (Q/2) x Ch                                            (4)

Total Cost = Total Ordering Cost + Total Carrying Cost + Purchase Cost

= (D/Q) x Co  + (Q/2) x Ch  + P x D                             (5)

Observe that the total purchase cost (i.e. P x D) does not depend on the value of Q. This is so because regardless of how many orders we place each year, or how many units we order each time, we will still incur the same annual total purchase cost.

The presence of Q in the denominator for the first term makes equation (5) a non-linear equation with respect to Q. Nevertheless, because the total ordering cost is equal to the total carrying cost at the optimal value of Q, we can set the terms in equation (3) and (4) equal to each other and calculate EOQ as

Q^* = √2𝐷 Co/ Ch                                                                       (6)

 

Inventory Control with Deterministic Models

Examples 1

1. The production department for a company requires 3, 600 kg of raw material for manufacturing a particular item per year. It has been estimated that the cost of placing an order is Rs. 36 and the cost of carrying inventory is 25% of the investment in the inventories. The price is Rs. 10/kg. The purchase manager wishes to determine an ordering policy for raw

Solution

From the data of the problem we know that

D = 3600 kg per year;   Co  = Rs. 36 per order;    Ch = 25% of the investment in inventories

= 10 X 0.25 = Rs. 2.50 per kg per year.

 

• The optimal lot size is given by

Q^* = √2𝐷 Co/ Ch = √2 𝑋 3600 𝑋 36 / 250 = 321.99 kg per order.

 

1. Optimal order cycle time

t^* = ^𝑄∗ = 321.99/3600 = 0.894 year

𝐷

 

• The minimum yearly variable inventory cost

TVC = √2𝐷 CoCh = √2𝑋 3600 𝑋 36 𝑋 2.5 = Rs. 804.98 per year

 

1. The minimum yearly total inventory cost

TC^* = TVC^* + DC = Rs. 804-98 + (3600 kg) (Rs. 10/kg) = Rs. 36, 804.98 per year.

 

2. A company operating 50 weeks in a year is concerned about its stocks of copper This costs Rs. 240/- a meter and there is a demand for 8, 000 meters a week. Each replenishment costs Rs. 1, 050 for administration and Rs. 1, 650 for delivery, while holding

 

costs are estimated at 25% of value held a year. Assuming no shortages are allowed, what is the optimal inventory policy for the company?

How would this analysis differ if the company wanted to maximise profit rather than minimise cost? What is the gross profit if the company sell cable for Rs. 360 a meter?

Solution

From the data of the problem, we have

Demand rate (D) = 8, 000 x 50 = 4, 00, 000 metres a year

Purchase Cost (C) = Rs. 240 a unit; Ordering cost (Co) = 1, 050 + 1, 650 = Rs. 2, 700 Holding Cost = 0.25 x 240 = Rs. 60 a meter a year

1. Optimal order quantity Q^* = √2𝐷 Co/ Ch = √2 𝑋 40,000 𝑋 2,700 = 6, 000 meters

60

 

1. Total variable inventory cost, TVC = Q^*. Ch = 6, 000 x 60 = Rs. 3, 60, 000 a year

 

1. Total inventory cost, TC = D.C + TVC = 4, 00, 000 x 240 + 3, 60, 000 = Rs. 9, 63, 60, 000

With a turnover in excess of 96 million rupees a year inventory costs are only Rs. 3, 60, 000 or 0.36%. This figure is usually low but any well run organisation should try to make all the waivings it can, however, small.

If the company wanted to maximise profit rather than minimise cost, the analysis used would remain exactly the same. This can be demonstrated by defining selling price (SP) per unit so that gross profit per unit becomes,

Profit = Revenue – Cost

= D x SP –

DC + 𝐷 Co + 𝑄 Ch

𝑄                    2

 

When this equation is solved to maximise profit with respect to Q as discussed earlier, we get the same result by applying usual method.

If company sells the cable for Rs. 360 a meter, its revenue is Rs. 360 x 4, 00, 000 = Rs. 14, 40, 00, 000 a year. Direct cost of Rs. 9, 63, 60, 000 is subtracted from this to get a gross profit of Rs. 4, 76,  40, 000 a year.

3. A chemical company is considering the optimal batch size for reorder of concentrated sulphuric acid. The management accountant has supplied the following information:

• The purchase price of H2SO4 is Rs. 150 per
• The clerical and data processing costs are 500 per order.

All the transport is done by rail. A charge of Rs. 2, 000 is made each time the special line to the factory is opened. A charge of Rs. 20 gallon is also made. The company uses 40, 000 gallons per year. Maintenance costs of stock are Rs. 400 per gallon per year.

Each gallon requires 0.5 sq ft of storage space. If warehouse space is not used, it can be rented out to another company at Rs. 200 per sq ft per annum. Available warehouse space is 1, 000 sq ft, the overhead costs being Rs. 5, 000 p.a. Assume that all free warehouse space can be rented out.

• Calculate the economic reorder size
• Calculate the minimum total annual cost of holding and reordering

Solution

Based on the data of the problem, the relevant cost components which will vary over the time period due to change in lot size quantity (Q) and which will remain fixed is summarised as follows:

 

	Relevant     Cost     for     EOQ Calculation	Irrelevant    Cost     for     EOQ Calculation
Ordering Cost         Carrying cost	·         Clerical       and                   data processing, Rs. 500; ·         Rail transport, Rs. 2000     ·         Maintenance   cost,   Rs. 200; ·         Rented cost, Rs. 200/2 = Rs. 100	·         Rail transport, Rs. 20 per gallon because a fixed money of Rs. 40, 000 x 20 = Rs. 8, 00, 000 will incur irrespective of size of Q.   ·         Overhead cost, Rs. 5, 000

Thus the relevant costs needed for calculating EOQ are: Co = Rs. 2, 500; Ch = Rs. 300.

 

Q^* (EOQ) =

2𝐷Co

√

Ch

2 𝑥 40,000 𝑥 2,500

=

√

300

= Rs. 817 (approx.) gallons.

 

 

Hence, the minimum total annual costs are:

 

 

Ordering: ^𝐷

Q∗

Co = 40,000 x 2, 500 = Rs. 1, 22, 399.02

817

 

Carrying: Q∗  Ch  = 817  x 300 =         Rs. 1, 22, 250.00

2                      2

Total                      = Rs. 2, 44, 949.02

Rail transport: 40, 000 x 2 = Rs. 8, 00, 000 Storage Overhead cost:                      = Rs. 5, 000 Purchase Cost: 40, 000 x 150 = Rs. 60, 00, 000

Total                                        = Rs. 70, 49, 949.02

4. A contractor has to supply 10, 000 bearings per day to an automobile manufacturer. He finds that when he starts production run, he can produce 25, 000 bearings per day. The cost of holding a bearing in stock for a year is Rs. 2 and the set-up cost of a production run is Rs. 180. How frequently should production run be made?

Solution

From the data of the problem in usual notation, we have

Co  = Rs. 1, 800 per production run;                 Ch = Rs. 2 per year

p = Rs. 25, 000 bearings per day                     d = 10, 000 bearings per day

D = 10, 000 x 300 = 30, 00, 000 units/year (assuming 300 working days in the year).

1. Economic batch quantity for each production run is given by

 

 

Q* = √2𝐷𝐶𝑜 (

) = √2 𝑥 30,00,000 𝑥 1,800 (         25,000

) = 1, 04, 446 bearings

 

𝐶ℎ        𝑝−𝑑

2                             25,000−10,000

 

1. Frequency of production cycles

t^* = ^𝑄∗ = 1, 04, 446/10, 000 = 10.44 days.

𝑑

5. A commodity is to be supplied at a constant rate of 25 units per A penalty cost is being charged at the rate of Rs. 10 per unit per day late for missing the scheduled delivery date. The cost of carrying the commodity in inventory is Rs. 16 per unit per month. The production process is such that each month (30 days) a batch of items is started and are available for delivery any time after the end of the month. Find the optimal level of inventory at the beginning of each month.

Solution:

From the data in usual notations, we have

D = 25 units / day;       Ch  = 16/30 = 0.53 per unit per day;      Co = Rs. 10 per unit per day; t = 30 days

Thus optimal inventory level is given by

 

 

M^* = [   ¹⁰ 0.53+10

] (25) (30) = 712 units.

 

 

SELECTIVE INVENTORY CONTROL TECHNIQUES

In practice when a firm maintained large number of items in its inventory, obviously all items cannot, and need not be controlled (i.e. keeping record of time interval between successive reviews of demand; order frequencies; expected demand rate; order quantities etc.) with equal attention.  All items are not of equal importance to the firm in such terms as sales, profits, availability etc. One way of exercising proper degree of control overall and various types of items held in stocks is to classify them into groups (or classes) on the basis of the degree of control or intensity of management effort that they require.

By selectively applying inventory control policies to these different groups, inventory objectives can be achieved with lower inventory levels than with a single policy applied to all items. These techniques are also known as selective multi-item inventory control techniques.

In this section, we shall consider certain group classifications such as: ABC, VED, FSN, HML, XYZ etc.

Classification	Basis of Classification	Purpose
ABC {Always, Better, Control}	Value of consumption	To     control     raw         material, components         and         work-in- progress    inventories   in    the normal course of business.
HML {High, Medium, Low}	Unit price of the material	Mainly to control purchases
XYZ	Value of items in storage	To review the inventories and their uses at scheduled intervals.
VED {Vital, Essential, Desirable}	Criticality of the component	To    determine   the    stocking levels of spare parts.
FSN {Fast, Slow, Non-moving}	Consumption  pattern   of   the component	To control obsolescence

 

ABC ANALYSIS

The ABC analysis consists of separating the inventory items into three groups: A, B and C according to their annual cost volume consumption (unit cost x annual consumption). Although the break points between these groups vary according to individual business conditions, a common break down might be as follows:

Category or Group	Percentage of the item	% of the Total Annual Value of the inventories (Rs.)
A	10 – 20	70 – 85
B	20 – 30	10 – 25
C	60 – 70	5 – 15

 

This type of classification is also known as the principle of law of Vital Few and Trivial Many. The ABC analysis facilitates analysis of yearly consumption value of items in the store to identify the vital few items which are generally referred to as A category items. Generally, these items accounting for about 70% of the total money value of consumption. Items accounting for about 25% of the total money value of consumption are called B category items and the remaining ones accounting for about 5% consumption value as C category items.

Carrying on the ABC analysis of the store items helps identifying the few items that are vital from financial point of view and require careful watch, scrutiny and follow-up. The application of ABC

 

analysis extends overall of the aspects of materials management like purchasing, inventory control, value analysis etc.

After the items are so classified, the inventory control policies are made on the basis of the classification ‘A’ category items require special managerial attention, therefore, fixed-interval inventory control system might be used for these items. ‘C’ category items can be managed in a little casual manner. For these items, a fixed-order quantity system might be used. The order quantities can be relatively large without incurring excessive costs. A large reserve stock can also be maintained. ‘B’ items are not so costly as to require special managerial attention, but these are not so cheap as to ignore overstocking, therefore (s, S) inventory control system might be used for these items.

The procedure of ABC analysis is summarised in the following steps:

Step 1

Obtain data on the annual usage (or consumption) in units and unit cost of each inventory unit. Multiple the annual usage in units and the value of each item to get annual value for each of these items.

Annual Value = Unit Cost x Annual Consumption

Step 2

Arrange these inventory items in a decreasing order of their value computed in step 1.

Step 3

Express the annual value of each item as percentage of the total value of all items. Also compute the cumulative percentage of annual consumption rupees spent.

Step 4

Obtain the percentage value for each of the items. That is, if there are 50 items involved in classification, then each item would represent 100/50 = 2 percent of the total items. Also cumulate these percentage values.

Step 5

Draw a graph between cumulative percentage of items (on x-axis) and cumulative annual percentage of usage value (on y-axis), and mark cut-off points where the graph changes slope as shown in figure.

Example 1

A company produces a mix of high technology products for use in hospitals. The annual sales data are as follows:

Product Type	Number      of Units	Unit Price (Rs.)	Product Type	Number      of Units	Unit Price (Rs.)
1	1, 000	2.50	10	600	1.62
2	250	0.55	11	25	33.00
3	150	6.50	12	4	15.50

 

4	300	1.00	13	1, 000	5.00
5	100	1.50	14	2, 850	2.50
6	700	1.43	15	10	0.83
7	500	7.00	16	355	0.98
8	15	4.98	17	50	1.37
9	1, 000	0.75	18	393	1.85

For inventory control reasons, the company wants to classify these items into three groups A, B and C on the basis of annual sales value of each item. You please help the company.

Solution

The annual sales volume (in Rs.) for each product and the item ranking on the basis of this volume is shown in Table.

Product ranking as per sales volume

Product Type	Number          of Units	Unit Price (Rs.)	Annual      Sales Volume (Rs.)	Ranking
1	1000	2.50	2, 500.00	4
2	250	0.55	137.50	14
3	150	6.50	975.00	6
4	300	1.00	300.00	12
5	100	1.50	150.00	13
6	700	1.43	1001.00	5
7	500	7.00	3500.00	3
8	15	4.98	74.70	16
9	1000	0.75	750.00	9
10	600	1.62	972.00	7
11	25	33.00	825.00	8
12	4	15.50	77.50	15
13	1000	5.00	5000.00	2
14	2850	2.50	7125.00	1
15	10	0.83	8.30	18
16	355	0.98	347.90	11
17	40	1.37	54.80	17
18	393	1.85	727.05	10

The cumulative percentage of products and cumulative percentage of sales for each product is given in table for the purpose of ABC classification:

ABC Classification

Rank	Product	Product Cumulative % of products	Annual Sales Volume (Rs.)	Cumulative Annual Sales Volume (Rs.)	Cumulative % Product Class of Sales
1	14	5.56	7, 125.00	7,125.00	29.05 A product 11.11%
2	13	11.11	5, 000.00	12,125.00	49.43 products and 49.43 Rs.
3	7	16.67	3, 500.00	15,625.00	63.70 B products: 38.89%

 

4	1	22.22	2, 500.00	18,125.00	73.90 Products and 42.91 Rs.
5	6	27.78	1, 001.00	19,125.00	77.97
6	3	33.33	975.00	20,101.00	81.95
7	10	38.89	825.00	21,073.00	85.92
8	11	44.44	750.00	21,898.00	89.28
9	9	50.00	727.05	22,648.00	92.34
10	18	55.56	347.90	23,375.00	95.30 C Products 44.44%
11	16	61.11	300.00	23,722.00	96.72 products and 7.66 Rs.
12	4	66.67	150.00	24,022.00	97.94
13	5	72.22	137.50	24,172.95	98.56
14	2	77.78	27.50	24,310.45	99.12
15	12	83.33	24.70	24,387.95	99.43
16	8	88.89	54.80	24,462.65	99.74
17	17	94.44	8.30	24,517.45	99.96
18	15	100.00		24,525.75	100.00

The percentage of products and percentage of annual sales volume can also be plotted on the graph.

VED Analysis

This analysis helps in separating the inventory items into three groups according to their criticality, usually called V, E, and D items in that order, VED classification calls for classification of items as Vital, Essential and Desirable.

V items are considered vital for smooth running of the system and without these items the whole system becomes inoperative. Thus adequate stock is required all the time.

 

E items are considered essential to the efficient running of the system and non-availability of these items reduces the efficiency of the system.

 

D items neither stop the system nor reduce its efficiency, but availability of such items will lead to increase in efficiency and reduction of failure.

 

This classification is largely useful in controlling inventory of spare parts. It can also be used in case of such raw materials whose availability is rare.

ABC analysis and VED analysis can also be combined to control the stocking of spare parts based on the desired customer service level as shown in the table.

ABC Classification	VED Classification
	V	E	D
A	Constant        control, Regular follow-up Low      stocks      and ordering             more frequently	Average    stock;    No risk of stock outs.	No stock
B	Average stocks	Average stock; some	Very     low     stocks;

 

	No risk of stock outs	risk can be taken	Some    risk    can    be taken.
C	High Stocks Restricted orders; No risk	Average Stock; some risk can be taken.	Low    stocks;    some risk can be taken.

HML Analysis

Based on the unit price of items, the HML classification separates inventory items, as High price, Medium price and Low price. This analysis is helpful to control purchase of various items for inventory.

FSN Analysis

The consumption pattern or inventory items forms the basis for FSN analysis. Items are classified as Fast-moving, Slow-moving and Non-moving. Sometimes items are also classified as FSND: Fast-moving; Slow-moving; Normal-moving and Dead (or Non-moving). This classification is based on the movement (or consumption pattern) and therefore helps to controlling obsolescence of various items by determining the distribution and handling patterns. Cut-off points of the three classes are usually in terms of number of issues in the previous few years.

 

XYZ Analysis

This classification is based on the closing value of items in storage. Items whose inventory values are high and moderate are classified as X-items and Y-items respectively, while items with low inventory value are termed as Z-items.

This analysis is usually undertaken once a year during the annual stock taking exercise. This helps in identifying the items which are being stocked extensively.

This classification can also be combined with ABC classification of items to control inventory of items as shown in the table below:

ABC Classification	XYZ Classification
	X	Y			Z
A	Attempt    to    reduce stocks	Attempt Z-items	to	convert	Items control	are	within
B	Stock                    and consumption            is reviewed more often	Items control	are	within	Review stock at least twice a year
C	Dispose      off      the surplus items	Check and maintain the control			Review annually		stock

XYZ-FSN classification exercise helps in the timely prevention of obsolescence.

XYZ Classification	FSN Classification
	F	S	N
X	Light inventory control	Reduce stock to very low level	Quick     disposal    of items     at     optimum price
Y	Normal inventory control	Low level of stocks	Should be disposed as early as possible.
Z	Can reduce clerical work	Low level of stocks	Can afford to dispose

 

by increasing stocks.

at lower prices.

Exercises Questions

1. Why is inventory an important consideration for managers?
2. State the purpose of inventory
3. Why would not a company all the time store large quantities of inventory to avoid shortages and stockouts?
4. Describe the major decisions that must be made in inventory
5. State some of the assumptions made in
6. Discuss in detail the major inventory costs that are used in
7. Classify the following 14 items in ABC

Code Number	Monthly Consumption (Rs.)	Code Number	Monthly Consumption (Rs.)
D-179-0	451	D-196	214
D-195-0	1,052	D-198-0	188
D-186-0	205	D-199	172
D-191	893	D-200	170
D-192	843	D-204	5,056
D-193	727	D-205	159
D-195	412	D-212	3,424

How the policies with regard to safety stocks, order quantity, material control and inventory system will be different for the items classified as A, B and C?

8. The following information is provided for an item:

Annual demand: 12, 000 units;                       Ordering Cost: Rs. 60/order

Carrying Cost: 10%;                                       Unit cost of item: Rs. 10 and Lead Time: 10 days.

There are 300 working days in a year. Determine EOQ and number of orders per year. In the past two years the demand rate has gone as high as 70 units/day. For a reordering system based on the inventory level, what should be the buffer stock? What should be the reorder level at this buffer stock? What would be the carrying costs for a year?

9. The demand for an item in a company is 18,000 units per year, and the company can produce the item at a rate of 3,000 per month. The cost of one set-up is 500 and the holding cost of one unit per month is 15 paise. The shortage cost of one unit is Rs. 240 per year. Determine the optimum manufacturing quantity and the number of shortages. Also determine the manufacturing time and the time between set-ups.
10. A product is sold at the rate of 50 pieces per day and is manufactured at a rate of 250 pieces per day. The set-up cost of the machines is 1, 000 and the storage cost is found to be Re 0.0015 per piece per day. With labour charges of Rs. 3.20 per piece, material cost at Rs.2.10 per piece and overhead cost of Rs.4.10 per piece, find the minimum cost batch size if the interest charges are 8% (assume 300 working days in a year). Compute the optimal number of cycles required in a year for the manufacture of this product.

 

 

REFERENCE: http://mu.ac.in/wp-content/uploads/2017/10/dormsem1optimizationmodel1.pdf

 

 Click here to download the pdf

Click here to download the pdf