Chapter 9.6, Problem 2P

Explanation of Solution

Determining the order in which the gasolines are produced each day:

It is given that, Sunco each day manufactures four types of gasoline, such as, Lead Free Premium (LFP), Lead-Free Regular (LFR), Leaded Premium (LP), and Leaded Regular (LR).

It is also mentioned that the time needed to produce a batch of gasoline depends on the type of gasoline last produced because of cleaning and resetting of the machinery. This is because the time taken to switch between the two types of gasoline is different for all the types.

The time (in minutes) required to manufacture each day's gasoline requirement are shown in table given below:

Last Produced Gasoline	Gas to be Next Produced
	LFR	LFP	LR	LP
LFR	-	50	120	140
LFP	60	-	140	110
LR	90	130	-	60
LP	130	120	80	-

Now the order in which the gasoline must be produced to minimize the switch time is determined using branch and bound method.

The given problem is to determine the order in which the gasoline must be produced with the aim of minimizing the total time required for the whole manufacturing process. This is simply the case of Travelling Salesperson Problem (TSP) which will ensure the manufacturing of all the four types of gasoline in consecutive order without repetition.

Now, consider that TSP observed here consists of the four types of gasoline LFR, LFP, LR, and LP referred as 1, 2, 3 and 4 respectively.

Let,

$C_{ij}=Timerequiredtoswitchbetweenanytwotype\text{ of }gasolines$

And,

$Cij=M$

Here, “M” is a very large number to ensure that the machinery cannot switch to manufacturing type “i” immediately after manufacturing of type “i” itself.

The decision variable for the given problem can be defined as follows:

$x_i{}_j=\left\{\begin{array}{l}1\text{ if the types of gasoline are manufactured in the order i to j}\\ 0\text{ otherwise}\end{array}\right.$

provided, $i\ne j$ for all assumptions.

The given problem can be considered as subproblem 1 as given problem:

Subproblem 1:

Last Produced Gasoline	LFR	LFP	LR	LP
	1	2	3	4
LFR	1	M	50	120	140
LFP	2	60	M	140	110
LR	3	90	130	M	60
LP	4	130	120	80	M

The subproblems of TSP are considered as assignment problems and the assignment problem are solved using Hungarian method in the following manner.

First, subtract minimum $C_{ij}$ from each row of subproblem 1 and then subtract the minimum $C_{ij}$ from each column. Thus, the reduced table of subproblem 1 will be as follows:

Last Produced Gasoline	LFR	LFP	LR	LP
	1	2	3	4
LFR	1	M	0	70	90
LFP	2	0	M	80	50
LR	3	30	70	M	0
LP	4	50	40	0	M

The minimum value to each variable is assigned by selecting single zero in a row, eliminating the zero lying in the column of chosen zero row. Apply the same for column as well if any single zero columns are left in the matrix after row wise selection of single zero.

Since here each row and column consists of single zero, therefore, we can easily complete the assignment of each decision variable. It is concluded that each of the decision variable will be assigned a value 1 in the cell where $C_{ij}$is minimum, that is zero, in the above table