Operations Research 5th Module

GAME THEORY

Game is defined as an activity between two or more persons (players) involving activities according to a set of rules.
Theory of games is a decision theory concerned with the study of decision-making, in situations where two or more players are involved under conditions of competition and conflicting interests.
Theory of games can be used in pricing, marketing, servicing of a product, by a firm to it's customers in the competitive environment.
A competitive situation is called game in this context, competitors are referred as players

BASIC TERMS

Player: A competitor in the game is known as a player. A player may be individual or group of individuals or organizations.
Strategy: A set of alternative courses of action (choices) available to a player based on advanced knowledge is known as strategy.
Pure Strategy: If the player selects / uses the same strategy each time, then it is referred as pure strategy. In this case the situation is deterministic and the objective is to maximise the gain (or) minimize the loss.
(Using only one type of technique / strategy while playing in the game.)
Mixed Strategy: If the player selects / uses his course of action in accordance with some fixed probability, then it is referred to as mixed strategy. It is probabilistic situation where the player uses a combination of strategies.
(Using the blend of strategies while playing in the game.)
Optimum Strategy: A course of action (choice) which puts the player in the most preferred position, irrespective of the strategy of his competitors, is referred as an optimum strategy.

Two Person Zero - Sum Game: When only two players are involved in the game and if the gain made by the one player is equal to the loss of the other, then it is called two persons zero - sum game.
Example
Assuming that there are only two types of beverages, tea and coffee, any market share gained by the tea will be equal to the loss of market share of coffee.
Sum of gains and losses is zero, hence the situation is referred as zero sum game.

Pay off Matrix: The representation of gains and losses resulting from different actions of the competitors and is represented in the form of a matrix is pay off matrix.
Value of Game : It is the expected payoff of the player when all the players of the game follow their optimum strategies.
Fair Game: If the value of the game is zero, it is referred as a fair game.
Note: Pay-off is also referred as outcome and in solving the problems payoff matrix and value of game is with reference to the row player. That is, a positive sign indicates the gain to row player, a negative sign indicates loss to him and for column player it is converse

TYPES OF GAME

The Types (classification) of games are given below:
(i) Based on the number of players
a) Two person games (number of players is two)
b) Multi person game (number of players is more than two)
(ii) Based on value of game
a) Fair game (value of game is zero)
b) Un fair game (game with a value other than zero)
(iii) Based on certainty / nature
a) Deterministic game (Pure strategy game)
b) Probabilistic game(Mixed strategy game)

PROPERTIES (CHARACTERISTICS) OF A GAME

• There are a finite number of competitors called players.
• Each player has a finite number of possible courses of action called strategies.
• The gain or loss is shown as the outcome of strategies in a matrix form called pay off matrix.
• The game is said to be a fair game if its value is zero, There must be some interest of conflicting nature that calls for competition between some persons.

Each competitor will act so as to maximize his minimum gain or minimize his maximum loss

Maxi Mini Principle

A row player (say A) will select the maximum out of the minimum gains (Maxi min). A minimum value in each row represents the least gain (payoff) to him, if he selects this particular strategy. These values are written in the matrix by row minima. He will then select the strategy that maximises his minimum gains.

This choice of the player is called Maxi Min principle

Example-

Row minima indicates his worst gains
Maxi min is the maximum benefit out of these worst gains

Mini Max Principle
A column player will always try to minimise his maximum losses (Mini max). For column player the maximum value in each column represents the maximum loses to him if he choses his particular strategy. These are written in the matrix by column maxima. He will then select the strategy that minimizes his maximum losses.

This choice of player ‘B’ is called the Mini Max principle

Example –

Column maxima indicates his minimum losses for his different strategies. Mini max is the maximum loss out of the maximum losses

Saddle point: If the Maxi min value is equal to the Mini Max value, then the game is said to have saddle point

Sequencing

Sequencing problems are used to determine the order or sequence of jobs in which they should be processed. This helps in minimizing the total cost or time involved in the operation.

Sequence is the order in which different activities are to be performed. Every organization wants to utilize its productive systems effectively and efficiently and maximize its profits by meeting the delivery deadlines. It is necessary that the available facilities are to be optimally utilized and they are loaded, scheduled and sequenced properly.

Sequencing problems have been most commonly encountered in production shops where different products are to be processed over various combination of machines.

However, sequencing problems can arise even where only one service facility is involved, for example, a number of programs waiting to get on a computer or a number of patients waiting for a doctor.

TERMINOLOGY

The terminology used in the problems of sequencing and scheduling are,

Jobs: Group of tasks or activities to be performed. These have to be sequenced; hence there should be a particular number of jobs say n to be processed.

Machine: It is a facility which has some processing capably. Jobs have to be performed or processed on machines.

Loading: Assigning of jobs to facilities and committing of facilities to jobs without specifying the time sequence

Sequencing: Sequencing of operations refers to a systematic procedure of determining the ode in which a series of jobs will be processed in a definite number, say k, facilities or machines.

Processing time: Every operation required to be performed requires definite amount of time at each facility or machine. When processing time is definite and certain, scheduling is easier-as compared to the situation in where it is unknown.

Total elapsed time: It is the time that lapses between starting of first job and the completion of the last one. This includes idle time, if exists.

Idle time: The time for which the facilities or machine is not utilized during the total elapsed time.

Technological order: It is the order which must be followed for completing a job. The requirement of the job dictates in which order various operations have to be performed.

Static arrival pattern: The pattern in where jobs done are received at the facilities simultaneously

Dynamic arrival pattern: The pattern in where the jobs keep arriving continuously.

No Passing Rule: This means that if 'n' jobs have to be processed through 'm' machines in a particular order of  M1, M2, M3 then job will go to machine M1, first and then to M2, and finally M3,. This order cannot be passed.

BASIC ASSUMPTIONS IN SEQUENCING

In dealing with sequencing problems the following principal assumptions are usually made

i. No machine can process more than one operation at a time.

ii. The time required to transfer the jobs between the machines is negligible.

iii. Processing time of job on a machine has no relation with the order, in which the jobs at processed.

iv. All machines have different capability and capacity.

v. All jobs are ready for processing.

vi. Each job when put on the machine is completed.

vii. All jobs are processed in specified order as soon as possible.

viii. There is only one of each type of machines.

TYPES OF SEQUENCING PROBLEMS

The following type of sequencing problems are

i. n Jobs on a Single Machine using Priority Sequencing
ii. n jobs on two machines
iii. n jobs on three machines
iv. n jobs on m machines
v. 'Two jobs through 'm' machines.

n JOBS ON A SINGLE MACHINE USING PRIORITY SEQUENCING

When several jobs compete for the capacity of a single machine or a work centre, the question of sequencing of jobs arises. This question is answered by determining the priority for all the jobs waiting in the queue by applying priority sequencing rules.

The priority indicates the sequence of in which the jobs will be processed on the machine or in the work centre. When the machine or work centre becomes free, job with the highest priority is assigned.

Following are some of the important single criterion priority sequence rules

First - Come - First - Served (FCFS) sequencing :
'In this, incoming jobs or customers are processed in their order of arrival. It is a priority rule that gives top priority to the waiting job that arrived earliest in the production system.
Examples of FFS are seen in the service industries like banks, supermarkets, hospitals, railway booking etc.
I

Shortest Processing Time (SPT):
In this rule, top priority is given to the waiting job whose operation time at a work centre is shortest. It ignores the due dates and order of arrival.
E.g. if 15, 10, 25 are the processing times in minutes of three jobs, the job with 10 min will be processed first.

Weighted SPT Rule (WSPT):
The SPT rule simply chooses the sequence as per the increasing order of the processing time without considering any other factor. In such cases, they should be given first priority. This can be achieved by assigning weights to such jobs.

Find tj/wj, in-case of tie of weights where t, w, are processing time and weight.

Earliest Due Date (EDD): In this, top priority is assigned to the waiting job whose due date is earliest. It ignores the job arrival time, and the processing time.
The due dates will be arranged in the increasing order and then they are sequenced,
E.g. If the due dates of three jobs (J1, J2, J3,)are 20, 26, 24 then the sequence is J1, - J3, - J2,
(after arranging in ascending order)

Key Terms:

Ready time (R) :
It represents the duration for which a particular job has waited, before the first job in the sequence has started processing.

Usually it is assumed as 0 for all jobs which means that all jobs have just arrived together and are waiting for their turn.

Average job flow time (F) :
It is the total flow time of all the jobs divided by the number of jobs

Flow time is the total time spent by a job (F).

Max Flow time: It is the largest flow time that any job has.

Due date (Dj) : It is the time at which a job is due to be completed.

Completion time (Cj):  It is the time required to actually complete the job since its arrival
Cj = Fj+ Rj
if Rj = 0 Cj = Fj

Lateness (Lj) : It is the duration by which a job 'j' differs from its due date.
Lj = Cj – Dj

Number of Tardy jobs: It is the number of jobs which are completed after the due date.

N Jobs of Two Machines

his sequencing algorithm was developed by Johnson and called Johnson's algorithm. In this problem n jobs must be processed through machines M, and M, The processing time of all the n jobs on M1 and M2 is known and it is required to find the sequence, which minimizes the time to complete all the jobs.

Steps in Johnson's algorithm

i. List the operation time for each job on machines M1 and M2
ii. Select the least processing time in the list.
iii. If the minimum processing time is on M1, place the corresponding job first in the sequence. If it is on M2 place the corresponding job last in the sequence. In case of tie in the processing .. time, it can be resolved arbitrarily.
iv. Eliminate the jobs which have already been sequenced as a result of step 3.
v. Repeat the steps 2 and 3 until all the jobs are sequenced.

Tags

• Operations Research
• mechatronics