Year: 2020

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

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

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

Consider the following example:

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

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

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

So the solution is degenerate.

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

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

1. Initial basic feasible solution is given below

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

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

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

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

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

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

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

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

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

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

Assignment Model:

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

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

Mathematical Formulation:

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

Suppose x_jj is a variable which is defined as

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

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

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

The total assignment cost will be given by

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

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

Subjected to constraints

and x_ij is either zero or one.

Method to solve Problem (Hungarian Technique):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Maximization Problem

Maximization assignment problem is transformed into minimization problem by

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

Conversion to Minimization Problem

Reduce the matrix row-wise

Matrix Reduced Row-wise

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

Matrix Reduced Column-wise and Zeros Covered

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

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

Added & Subtracted the least Uncovered Element

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

Two Alternative Assignments

Therefore,

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

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

Unbalanced Maximization Assignment problem example

Assignment Problem

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

Dummy Row D5 Added

Row-wise Reduction of the Matrix

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

All Zeros in the Matrix Covered

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

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

Subtracted or Added to Elements

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

Again Added or Subtracted 1 from Elements

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

Assigning Jobs to Machines

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

Assignment Problem

Find the optimal assignment plan.

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

Dummy Row D5 Added

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

Matrix Reduced Row-wise

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

Lines Drawn to Cover all Zeros

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

Added or Subtracted 1 from Elements

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

Optimal Assignment

Hence, the optimal solution is:

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

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

Objectives of Network Analysis:

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

A network analysis has following objectives:

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

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

Applications of Network Technique:

(i) Planning,

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

(iii) Assembly line scheduling,

(iv) Development and launching of new products,

(v) Strategic and tactical military planning,

(vi) Research and development,

(vii) Market penetration programmes,

(viii) Planning of political campaigns,

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

(x) organising big conferences etc.

Advantages of Network Technique:

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

(i) To over-come delays,

(ii) To crashing programme,

(iii) Optimising resources, and

(iv) On other corrective actions.

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

Limitations of Network Techniques:

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

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

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

Program Evaluation and Review Technique (PERT) is a method used to examine the tasked that are in a schedule and determine a variation of the Critical Path Method (CPM). It analyzes the time required to complete each task and its associated dependencies to determine the minimum time to complete a project. It estimates the shortest possible time each activity will take, the most likely length of time, and the longest time that might be taken if the activity takes longer than expected.  

The method was developed by the US Navy in 1957 on the Polaris nuclear submarine project.
To conduct PERT Analysis, three time estimates are obtained (optimistic, pessimistic, and most likely) for every activity along the Critical Path. Then use those estimates in the formula below to calculate how much time for each project stage:

Formula: (P+4M+O)/6

• Optimistic Time (O): The minimum possible time required to accomplish a task, assuming everything proceeds better than is normally expected.
• Pessimistic Time (P): The maximum possible time required to accomplish a task, assuming everything goes wrong (excluding major catastrophes).
• Most likely Time (M): The best estimate of the time required to accomplish a task, assuming everything proceeds as normal.

Example of the three time estimates

Example of a Critical Path Nodal Diagram

PERT Analysis can be conducted using Microsoft Project.

The Critical Path is the longest path of scheduled activities that must be met in order to execute a project.  This is important for Program Managers (PM) to know since any problems that occur on the critical path can prevent a project from moving forward and be delayed.  Earned Value Management (EVM) analysis focuses on the critical path and near critical paths to identify cost and schedule risks. Other schedule paths might have slack time in them to avoid delaying the entire project unlike the critical path. There might be multiple critical paths on a project.

The Critical Path is determined when analyze a projects schedule or network logic diagram and uses the Critical Path Method (CPM).  The CPM provides a graphical view of the project, predicts the time required for the project, and shows which activities are critical to maintain the schedule.

The seven (7) steps in the CPM are:

1. List of all activities required to complete the project (see Work Breakdown Structure (WBS)),
2. Determine the sequence of activities
3. Draw a network diagram
4. Determine the time that each activity will take to completion
5. Determine the dependencies between the activities
6. Determine the critical path
7. Update the network diagram as the project progresses

The CPM calculates the longest path of planned activities to the end of the project, and the earliest and latest that each activity can start and finish without making the project longer. This process determines which activities are “critical” (i.e., on the longest path) and which have “total float” (i.e., can be delayed without making the project longer).

The CPM is a project modeling technique developed in the late 1950s by Morgan R. Walker of DuPont and James E. Kelley, Jr. of Remington Rand.

The two important components of any activity are the cost and time. Cost is directly proportional to time and vice versa. For example, in constructing a shopping complex, the expected time of completion can be calculated using be time estimates of various activities. But if the construction has to the finished earlier, it requires additional cost to complete the project. We need to arrive at a time / cost trade-off between total cost of project and total time required to complete it.

Normal time: Normal time is the time required to complete the activity at normal conditions and cost.

Crash time: Crash time is the shortest possible activity time; crashing more than the normal time will increase the direct cost.

Cost Slope in Network Analysis

Cost Slope
Cost slope is the increase in cost per unit of time saved by crashing. A linear cost curve is shown in Figure.

Linear Cost Curve

Cost slope=Crash cost C_c– Normal cost N_c/Normal time Ntt

Example : An activity takes 4 days to complete at a normal cost of Rs. 500.00. If it is possible to complete the activity in 2 days with an additional cost of Rs. 700.00, what is the incremental cost of the activity?

Solution:
Incremental Cost or Cost Slope = C_c– N_c / Ntt
= 700-500/4-2 = Rs. 100.00
It means if one day is reduced we have to spend Rs. 100/- extra per day.

Project Crashing

Procedure for crashing

Step1: Draw the network diagram and mark the Normal time and Crash time.

Step2: Calculate TE and TL for all the activities.

Step3: Find the critical path and other paths.

Step 4: Find the slope for all activities and rank them in ascending order.

Step 5: Establish a tabular column with required field.

Step 6: Select the lowest ranked activity; check whether it is a critical activity. If so, crash the activity, else go to the next highest ranked activity.

Note: The critical path must remain critical while crashing.

Step 7: Calculate the total cost of project for each crashing.

Step 8: Repeat Step 6 until all the activities in the critical path are fully crashed.

Example: The following Table 8.13 gives the activities of a construction project and other data.

Construction Project Data

If the indirect cost is Rs. 20 per day, crash the activities to find the minimum duration of the project and the project cost associated.

Solution: From the data provided in the table, draw the network diagram and find the critical path.

Network Diagram

From the diagram, we observe that the critical path is 1-2-5 with project duration of 14 days The cost slope for all activities and their rank is calculated as shown in table below

Cost slope=Crash cost C_c– Normal cost N_c/Normal time Ntt

Cost Slope for activity 1– 2 = 80 – 50/6 – 4 = 30/2 = 15.

Cost Slope and Rank Calculated

The available paths of the network are listed down in Table indicating the sequence of crashing.

Sequence of Crashing

Network Diagram Indicating Sequence of Crashing

The sequence of crashing and the total cost involved is given in the following table

Initial direct cost = sum of all normal costs given
= Rs. 490.00

Sequence of Crashing & Total Cost

It is not possible to crash more than 10 days, as all the activities in the critical path are fully crashed. Hence the minimum project duration is 10 days with the total cost of Rs. 970.00.