Operations Research :- Unit V Integer Programming Problem and Project Management

Unit V Integer Programming Problem and Project Management

Syllabus:

Integer Programming Algorithms – B&B Algorithms, cutting plane algorithm, Gomory’s All-IPP Method, Project Management: Rules for drawing the network diagram, Application of CPM and PERT techniques in project planning and control; Crashing and resource leveling of operations Simulation and its uses in Queuing theory & Materials Management.

5.1 Integer Programming Algorithms –

The ILP algorithms are based on exploiting the tremendous computational success of LP. The strategy of these algorithms involves three steps.

5.1.1 B&B Algorithms

The first B&B algorithm was developed in 1960 by A. Land and G. Doig for the general mixed and pure ILP problem. Later, in 1965, E. Balas developed the additive algorithm for solving ILP problems with pure binary (zero or one) variables . The additive algorithm's computations were so simple (mainly addition and subtraction) that it was hailed as a possible breakthrough in the solution of general ILP. Unfortunately, it failed to produce the desired computational advantages. Moreover, the algorithm, which initially appeared unrelated to the B&B technique, was shown to be but a special case of the general Land and Doig algorithm. This section will present the general Land-Doig B&B algorithm only. A numeric example is used to explain the details.

5.1.2 Cutting plane algorithm

As in the B&B algorithm, the cutting-plane algorithm also starts at the continuous optimum LP solution. Special constraints (called cuts) are added to the solution space in a manner that renders an integer optimum extreme point. In Example 9.2-2, we first demonstrate graphically how cuts are used to produce an integer solution and then implement the idea algebraically.

5.2 Gomory’s All-IPP Method

Unit V\Gomory's.pdf

This is the most probable assignment question of Operation Research for MB0032 SMU MBA. The question is “What do you understand by the Integer Programming Problem? Describe the Gomory’s All-I.P.P. method for solving the I.P.P. problem.” You already have taken many solved assignments from SMU MBA MB002 such as - classification of Operations Research models, Matrix Minimum Method and Penalty Cost Method or Big-M Method for Solving LPP.

Gomory’s All – IPP Method:

An optimum solution to an I. P. P. is first obtained by using simplex method ignoring the restriction of integral values. In the optimum solution if all the variables have integer values, the current solution will be the desired optimum integer solution. Otherwise the given IPP is modified by inserting a new constraint called Gomory’s or secondary constraint which represents necessary condition for integrability and eliminates some non integer solution without losing any integral solution.

After adding the secondary constraint, the problem is then solved by dual simplex method to get an optimum integral solution. If all the values of the variables in this solution are integers, an optimum inter-solution is obtained, otherwise another new constrained is added to the modified L P P and the procedure is repeated.

An optimum integer solution will be reached eventually after introducing enough new constraints to eliminate all the superior non integer solutions. The construction of additional constraints, called secondary or Gomory’s constraints is so very important that it needs special attention.

5.3 Project Management: Rules for drawing the network diagram

Project management is concerned with the overall planning and co-ordination of a project from conception to completion aimed at meeting the stated requirements and ensuring completion on time, within cost and to required quality standards. Project management is normally reserved for focused, non-repetitive, time-limited activities with some degree of risk and that are beyond the usual scope of operational activities for which the organization is responsible.

Steps in Project Management

The various steps in a project management are:

1. Project Definition and Scope

2. Technical Design

3. Financing

 4. Contracting

5. Implementation

6. Performance Monitoring

The Network Diagram In a project, an activity is a task that must be performed and an event is a milestone marking the completion of one or more activities. Before an activity can begin, all of its predecessor activities must be completed. Project network models represent activities and milestones by arcs and nodes. PERT is typically represented as an activity on arc network, in which the activities are represented on the lines and milestones on the nodes. The Figure 7.4 shows a simple example of a PERT diagram.

         

The milestones generally are numbered so that the ending node of an activity has a higher number than the beginning node. Incrementing the numbers by 10 allows for new ones to be inserted without modifying the numbering of the entire diagram. The activities in the above diagram are labeled with letters along with the expected time required to complete the activity.

RULES IN CONSTRUCTING A NETWORK

Some conventions of network diagram are shown in Figure 8.10 (a), (b), (c), (d) below:

Figure 8.10 (a), (b), (c), (d): Some Conventions followed in making Network Diagrams

Unit V\network-problem-cpm-pert-9-728.jpg

5.4 Application of CPM and PERT techniques in project planning and control

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

5.5 Crashing and resource leveling of operations Simulation and its uses in Queuing theory & Materials Management.

Resource Levelling:

Projects will often be confronted by time and organizational constraints that limit their ability to obtain human resources. Sometimes staff can be supplemented through temporary help from technical service agencies. When staffing requirements are identified and constraints are understood, work plans can sometimes be adjusted to fit requirements to available resources.

Resource scheduling is one of the greatest challenges for projects without access to large organizational or job-market resource pools. Project planning should address such issues as redundancy of critical resources, resource capacity, bench strength in vital areas, and contingency plans to handle departures of key personnel.

Most of the popular project management software packages enable the project resource planner to assign staff to project tasks, display resource requirements profiles, and adjust the schedule of slack tasks so resource requirements more closely fit those available in the organization. Some packages can display multiple project resource requirements to facilitate organization-wide resource management, optimization, and leveling. Individual project requirements may be adjusted by manipulating schedule slack in tasks not on the critical path. This can facilitate allocation and leveling of staff throughout the organization.

Unless one person is working on each task full time, the schedule duration on the Gantt chart will not be the same as the effort required. Effort requirements will drive project cost, but durations will drive the schedule. These distinctions are helpful when reconciling project and resource schedules.

"Crashing" the Schedule:

Efforts to accelerate a project schedule are commonly grouped under the term "crashing" the schedule. Maybe this term was coined to suggest that there is always some price for driving a project to completion sooner than normal. There are a number of ways to improve the schedule when your boss says, I need it sooner!

1.     1. Add people to the schedule. Additional staff must be added early in a project or they will slow it down while learning the ropes. If you add people, you may also need to add staff for supervision and coordination, so staff are fully applied.

2.     2. Improve productivity and work longer hours. A good team atmosphere with management support can help make this happen. Without positive nourishment of this process, you could lose your team to attrition.

3.     3. Review schedule dependencies and look for opportunities to overlap tasks or make serial tasks concurrent or parallel activities. This requires greater coordination and sometimes involves increased risks which need to be managed carefully.

4.     4. Review the project scope and remove or delay features or functionality from the project critical path.

5.     5. Consider innovative approaches such as a different development methodology, alternative technologies, or out-sourcing options.