Miscellaneous – SEQUENCING
Operations ResearchMiscellaneous
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.
- Each job is processed in the order AB.
- The exact or expected processing times A1, A2, …, An, B1, B2, …, Bn are known.
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 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. 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 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 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 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.
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.
METHODS OF INTEGER PROGRAMMING SOLUTION
The two methods employed to solve the integer programming problems are:
(i)Cutting Methods
(ii)Search Methods
Cutting methods, which are developed, for integer linear problem, start with continuous optimum. Here the principle is systematically adding special constraints namely ‘secondary constraints’ which provide the necessary conditions for integrality.
The continuous solution space is gradually changed until its continuous optimum extreme point satisfies the integer conditions. The added secondary constraints effectively eliminate certain parts of the solution space that do not contain feasible integer points. R.E. Gomory has developed the cutting methods. They include the “fractional algorithm” which applies to the pure integer problem and the “mixed algorithm” for mixed integer problem.
Search method is an enumeration technique in which all feasible integer points are enumerated. The most prominent search method is the “branch and bound” technique. It also starts with the continuous optimum, but systematically partitions the solution space into sub problems that eliminate parts that contain no feasible integer points. A.H. Land A.G. Doig originally developed the branch and bound algorithm. But R.J. Dakin’s modification provides the computational case. The third algorithm is due to E.Balas, which is known, as ‘additive algorithm’, which is applied to pure zero-one problem.
GAME THEORY
Many conflicting situations are found in everyday life, in economic, social, political, military, battles, advertising and marketing campaign by competing business firms. In these situations two or more individuals have to take decisions that involve conflicting interests.
A basic feature in many of these situations is that the final result depends primarily on the combination of strategies selected by the persons involved, called adversaries. Game theory
handles such situations. Von Neumann, originally developed the Game Theory.
The following properties hold good for a competitive game.
- There are finite number of competitors
- Each of the competitors has a finite list of of possible courses of actions known as strategy. The number of strategies need not be the same for each competitor.
- A play of the game results when each of the competitors chooses a single course of action from the list of strategies available to him. The choices are 273 assumed to be made simultaneously so that no competitor knows his opponent’s choices until he is already committed to his own.
4. The outcome of a play depends on the strategies undertaken by the competitors. Each outcome determines the set of payments to be made to each competitor.
An objective of the game theory is to develop a rational criterion for selecting a strategy. This is done under the assumption that both players are rational and each will uncompromisingly attempt to do as well as possible, relative to his opponent. Game theory assumes that both players are actively trying to improve their own welfare in opposition to that of opponent.
There are different types of games and they may be classified indifferent ways.
Some of them are,
- Two-Person Zero-sum game
- Games with mixed strategies
- Games with Dominance, and so on.
SIMULATION
Simulation deals with the study of (dynamic) systems over time. There are three types of simulations
- Analogue
- Continuous
- Discrete
In analogue models, the physical (original) system is replaced by a model using analogy, which is easier for manipulation.
Continuous models represent the system undergoing smooth changes in the characteristic over a certain time period.
If the system is simulated with a model and observed it only at selected points in time, we have discrete model. These time points coincide with the occurrence of certain events, which play an important role to effect the changes in the performance of a system
Monte Carlo Simulation is the code name given by Von Neumann to the technique of solving problems too expensive for experimental solutions and too complicated for analytical treatment. If the model involves random sampling from a known probability distribution, the procedure is called Monte Carlo Simulation.
MARKOV CHAIN
A Markov process is mathematical model that describes, in probabilistic terms, the dynamic behavior of certain type of systems over time. A Markov chain is a type of Markov process.
A stochastic process is said to have the Markovian property that the conditional probability of any future event, given any past event and the present state, is independent of the past event and depends only on the present state of the process. This is called first-order Markov chain. If the outcome depends on other than the prior results it is called a higher order chain. For example a second order chain describes a process in which an outcome depends on the two previous outcomes.
DECISION ANALYSIS
In recent years, statisticians, engineers, economists and students of management have placed increasing emphasis on decision-making under conditions of uncertainty. Much of life, of course, involves making choices under uncertainty, which is, choosing from some set of alternative courses of action in situations where we are uncertain about the actual consequences that will occur for each course of action being considered.
In today’s fast-moving technological world, the need for sound, rational decision making by business, industry and government is vividly apparent. Consider, for example, the area of design and development of new improved products and equipment. Typically, development from invention to commercialization is expensive and filled with uncertainty regarding both technical and commercial success. In R&D, for example, decision makers might be faced with the problem of choosing whether to pursue a parallel versus a sequential strategy ( i.e. pursuing two or more designs simultaneously versus developing the most promising design, and if it fails, going to next most promising design, etc). In production, they may have to decide on a production method or process of manufacture; or choose whether to lease, 275 decide whether to invest in a new plant, equipment, research programs, marketing facilities, and even risky orders. In marketing, they may have to determine the pricing scheme, whether to do market research and what type and what type of it, the type of advertising campaign, and so on.
Each of these decision problems is characteristically complex and can have a significant impact on the health of a firm. It is almost impossible for any decision maker to intuitively take full account of all the factors impinging on a decision simultaneously. It thus becomes useful to find some method of separating such decision problems into parts in a way that would allow a decision maker to think through the implications of each set of factors one at a time in a rational, consistent manner. Decision analysis provides a rich set of concepts and techniques to aid the decision maker in dealing with complex decision problems under uncertainty.
Decision-making can be broadly classified into three broad categories;
- Decision making under certainty
- Decision making under risk
- Decision making under uncertainty
Most of the decisions are made on the basis of some criterion. When there is certainty or the outcome is sure, decision-making is simpler. When the outcome is not sure, then different criteria are used.
For decision making under risk
- Expected value criterion
- Combined expected value and variance criterion
- Known aspiration level criterion
- Most likely occurrence criterion
For decision making under uncertainty
- Laplace criterion
- Minimax (Maximin) criterion
- Savage criterion
- Hurcwiz criterion
Recent Comments