ZeePedia Add to Favourites   |   Contact us


Operations Research

<<< Previous Miscellaneous:SEQUENCING, PROCESSING n JOBS THROUGH TWO MACHINES Next >>>
 
img
Operations Research (MTH601)
270
10000
10
20
10
20000
10
20
20
30000
30
20
20
40000
40
30
30
50000
40
30
40
Segment X: Miscellaneous
Lectures 44-45
270
Operations Research (MTH601)
271
SEQUENCING
INTRODUCTION
A series, in which a few jobs or tasks are to be performed following an order, is called
sequencing. In such a situation, the effectiveness measure (time, cost, distance etc.,) is a function of
the order or sequence of performing a series of jobs. Problems of sequencing can be classified into
two major groups.
In the first type of problem, we have n jobs to perform each of which requires processing on
some or all m different machines. If we analyze the number of sequences, it runs to (n!)m possible
sequences and only a few of them are technologically feasible, i.e., those which satisfy the constraints
on the order in which each task has to be processed through m machines.
In the second type of problem, we have a situation with a number of machines and a series
jobs to perform. Once a job is finished, we have to take a decision on the next job to be started.
Practically both types of problems seem to be intrinsically difficult and now we know solutions
only for some special cases of the first type of problem. For the second type of problems, it appears
that a few empirical rules have been obtained to arrive at the solution and mathematical theory has to
be explored.
PROCESSING n JOBS THROUGH TWO MACHINES
The sequencing problem with n jobs through two machines can be solved easily. S.M.
Johnson has developed solution procedure. The problem can be stated as follows.
Only two machines are involved, A and B.
1.
Each job is processed in the order AB.
2.
The exact or expected processing times A1, A2, ..., An, B1, B2, ..., Bn are known.
3.
A decision has to be arrived to find the minimum elapsed time from the start of the first job to
the completion of the last job. It has been established that the sequence that minimizes the elapsed
time are the same for both machines. The algorithm for solving the problem is as follows and due to
S.M. Johnson.
Select the smallest processing time occurring in the list, A1, ..., An, B1, ... , Bn. If there
1.
is a tie, break the tie arbitrarily.
If the minimum processing time is Ai, do the ith job first. If it is Bj do the j-th job last.
2.
This decision is applicable to both machines A and B.
Having selected a job to be ordered, there are now n-1, jobs left to be ordered. Apply
3.
the steps 1 and 2 to the reduced set of processing times obtained by deleting the two
machine processing times corresponding to the job that is already assigned.
Continue in this manner until all jobs have been ordered. The resulting ordering will
4.
minimize the elapsed time, T.
THE TRAVELLING SALESMAN PROMLEM
In this type of problem, we have to select a route by a salesman that will minimize the total
distance traveled in visiting n cities and returning to the starting point. Another example is that if n
271
img
Operations Research (MTH601)
272
products are to be made in some order on a continuing basis, and the set up cost for each
depends on the preceding product made, we want to find cost for each depends on the preceding
products that will minimize the total set up cost when the product Ai is followed by Aj. The set up costs
are represented in square matrix, while the leading diagonal blank, indicating no set up cost when
changing a product to itself. In traveling salesman problem, we cannot choose the element along the
diagonal and this can be avoided by filling the diagonal with infinitely large elements. Another
constraint we have to work with is that having started from a station Ai say, we do not want to go to
the same station again until we have moved to all other stations.
INTEGER PROGRAMMING
INTRODUCTION
In linear programming problem, the decision variables represent men, machines, vehicles,
number of items to be produced etc. These variables make sense only if they have integer values in
the final solution to the linear programming problem. This is the problem faced in real life practice. For
example, if we get a solution to a problem when we decide on the number of chairs and tables
produced per day in a furniture industry. As 2.53 chairs and 3.82 tables, it is meaningless because of
non-integer solution. Hence a new procedure has been developed in this direction for the case of
linear programming problems subjected to the additional restriction that the decision variables must
have integer values.
For solving this type of integer linear programming problems, the usual technique is to apply
the simplex method ignoring the integer restriction and then rounding off the non-integer values to
integers in the resulting solution. There are some pitfalls in this approach. One is that it is difficult to
see in which way the rounding off should is rounded off successfully, there is no guarantee that this
rounded-off solution will be the optimal integer solution. In fact it may be far from optimal in terms of
the value of the objective function.
This can be illustrated by the following problem.
Maximize
Z = 2x + 10y
x + 10y < 20
Subject to
<2
x
and x and y are non-negative integers.
Since this problem involves only two variables, a graphical solution can be easily obtained which is
given below.
The graphical solution is used to find the optimal integer solution or optimal non-integer
solution. The optimal non-integer solution should be x = 2 and y = 9/5 with Z* = 22. If the simple
procedure is adopted, then the variable with the non-integer value y = 9/5 in rounded off in the
feasible direction to y = 1. Then the resulting integer solution is x = 2, y = 1 and Z* = 14. But this is far
from the optimal solution,
(x, y) = (0, 2) where Z* = 20
Therefore an efficient solution procedure for obtaining an optimal solution to integer
programming problems is necessary. Some progress has been made in recent years in developing
algorithms (solution procedures) for integer programming problems.
272
Table of Contents:
  1. Introduction:OR APPROACH TO PROBLEM SOLVING, Observation
  2. Introduction:Model Solution, Implementation of Results
  3. Introduction:USES OF OPERATIONS RESEARCH, Marketing, Personnel
  4. PERT / CPM:CONCEPT OF NETWORK, RULES FOR CONSTRUCTION OF NETWORK
  5. PERT / CPM:DUMMY ACTIVITIES, TO FIND THE CRITICAL PATH
  6. PERT / CPM:ALGORITHM FOR CRITICAL PATH, Free Slack
  7. PERT / CPM:Expected length of a critical path, Expected time and Critical path
  8. PERT / CPM:Expected time and Critical path
  9. PERT / CPM:RESOURCE SCHEDULING IN NETWORK
  10. PERT / CPM:Exercises
  11. Inventory Control:INVENTORY COSTS, INVENTORY MODELS (E.O.Q. MODELS)
  12. Inventory Control:Purchasing model with shortages
  13. Inventory Control:Manufacturing model with no shortages
  14. Inventory Control:Manufacturing model with shortages
  15. Inventory Control:ORDER QUANTITY WITH PRICE-BREAK
  16. Inventory Control:SOME DEFINITIONS, Computation of Safety Stock
  17. Linear Programming:Formulation of the Linear Programming Problem
  18. Linear Programming:Formulation of the Linear Programming Problem, Decision Variables
  19. Linear Programming:Model Constraints, Ingredients Mixing
  20. Linear Programming:VITAMIN CONTRIBUTION, Decision Variables
  21. Linear Programming:LINEAR PROGRAMMING PROBLEM
  22. Linear Programming:LIMITATIONS OF LINEAR PROGRAMMING
  23. Linear Programming:SOLUTION TO LINEAR PROGRAMMING PROBLEMS
  24. Linear Programming:SIMPLEX METHOD, Simplex Procedure
  25. Linear Programming:PRESENTATION IN TABULAR FORM - (SIMPLEX TABLE)
  26. Linear Programming:ARTIFICIAL VARIABLE TECHNIQUE
  27. Linear Programming:The Two Phase Method, First Iteration
  28. Linear Programming:VARIANTS OF THE SIMPLEX METHOD
  29. Linear Programming:Tie for the Leaving Basic Variable (Degeneracy)
  30. Linear Programming:Multiple or Alternative optimal Solutions
  31. Transportation Problems:TRANSPORTATION MODEL, Distribution centers
  32. Transportation Problems:FINDING AN INITIAL BASIC FEASIBLE SOLUTION
  33. Transportation Problems:MOVING TOWARDS OPTIMALITY
  34. Transportation Problems:DEGENERACY, Destination
  35. Transportation Problems:REVIEW QUESTIONS
  36. Assignment Problems:MATHEMATICAL FORMULATION OF THE PROBLEM
  37. Assignment Problems:SOLUTION OF AN ASSIGNMENT PROBLEM
  38. Queuing Theory:DEFINITION OF TERMS IN QUEUEING MODEL
  39. Queuing Theory:SINGLE-CHANNEL INFINITE-POPULATION MODEL
  40. Replacement Models:REPLACEMENT OF ITEMS WITH GRADUAL DETERIORATION
  41. Replacement Models:ITEMS DETERIORATING WITH TIME VALUE OF MONEY
  42. Dynamic Programming:FEATURES CHARECTERIZING DYNAMIC PROGRAMMING PROBLEMS
  43. Dynamic Programming:Analysis of the Result, One Stage Problem
  44. Miscellaneous:SEQUENCING, PROCESSING n JOBS THROUGH TWO MACHINES
  45. Miscellaneous:METHODS OF INTEGER PROGRAMMING SOLUTION