Books in black and white
 Main menu Share a book About us Home
 Books Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

# Combinatorial Optimization - Cristofides N.

Cristofides N. Combinatorial Optimization - Wiley publishing , 2012. - 212 p.
Download (direct link): čüombinatorialoptimi2012.pdf Previous << 1 .. 122 123 124 125 126 127 < 128 > 129 130 131 132 133 134 .. 156 >> Next In most such practical problems, however, there are many types of liquids :o be loaded/unloaded, each liquid being of a certain type, with the equirement that liquids of different types must not be mixed. The following ixample illustrates such a problem.
Let there be four tanks available, with capacities 20, 40, 60, and 70 units, wo types of liquids, A and B, and three operations to be performed, i.e.
(1) Load 90 units of A
(2) Unload 50 units of A
(3) Load 150 units of B.
Figure 12.1 Example of dynamic loading and unloading problem. V///A Liquid A;
ES3 Liquid B
Loading Problems
341
1 40
m
20 40 40 60 70
1

20
40
60
50
70
20
20
40
40
60
60
70
70
Figure 12.2 Example of dynamic loading and unloading problem. V//A Liquid A;
ES3 Liquid B
We will assume that none of these operations overlap in real time and that the tanks are initially empty.
Figure 12.1(1) shows a possible way to load 90 (which would result from an attempt to utilize tanks as much as possible). Figure 12.1(2) shows the state of the tanks after 50 units of A are unloaded (20 from tank 1 and 30 from tank 4). We have now arrived at a state from which it is impossible to continue. In contrast, Figure 12.2 shows a feasible way of performing the operations.
In Part 1 of this chapter we deal with the static problem of loading many types of liquid into tanks of different capacities and with a separate problem of unloading liquids from partially filled tanks. In both cases the objective is to minimize the value of tanks containing liquids at the end of the operations.
In Part 2 of the chapter we deal with the dynamic problem. The objective considered is a general integral criterion and includes a criterion based only on the terminal state of the tanks as a special case. For the dynamic problem the following assumptions are made:
(i) In the case of an oil tank farm, transfer of oil from one half-filled tank to another is considered as generally undesirable and to be avoided, firstly because the transfer operation itself is costly in terms of the energy required, and secondly because after every loading or unloading operation from a tank, some time (of the order of 2 hours) must elapse before another operation is performed on the same tank. Hence, any transfer operation leads to an under-utilization of available resources. Thus, in Part 2 of this
342
Nicos Christofides, Aristide Mingozzi, and Paolo Toth
chapterŚdealing with this type of problemŚwe have excluded the possibility of transfers between tanks.
(ii) Depending on the physical layout of the pipeline system used for the loading and unloading of oil, it may or may not be possible for operations to overlap in time. In Part 2 we consider the case where overlaps of different types of crude are possible (in both the loading and unloading modes), but overlaps of operations involving the same type of crude are not. This situation corresponds to a physical system with æby-passesÆ.
(iii) If I is a loading operation, we will assume that the tanks to be used in this operation are decided on at the beginning of the operation and are from that time assumed to be unavailable until they are fully unloaded in some future operation.
(iv) Similarly, if I is an unloading operation the tanks to be unloaded from are decided on at the beginning of the operation but are unavailable until the end of the operation. This assumption corresponds to the practical requirements of the real oil tank farm system.
This assumption can be removed at the expense of increasing the number of operations in the problem by dividing any unloading operation during which one or more other loading operations start (as shown in Figure 12.3a) into a number of unloading operations in series so that loading operations start only when unloading operations finish (as shown in Figure 12.3b).
( a )
Unload
( b )
Unload
Load
Unload
Load
Figure 12.3
Loading Problems
PART 1
343
STATIC LOADING AND STATIC UNLOADING PROBLEMS
12.1.1 General: Static Loading
We consider the problem of loading quantities q2,..., qN of N different types of liquid (which cannot be mixed) into M tanks of capacities Q,, Q21 Ģ ? ? > Qm-
The objectives considered are:
(i) Maximize the number of storage tanks left totally empty after the loading operations; or
(ii) Maximize the net capacity of storage tanks left totally empty.
The tanks that are filled or only partly filled are not considered in the evaluation of the objective functions.
Let E0 be the set of tanks that are initially empty, V, be the set of tanks already containing liquid i, and a, be the amount of liquid contained in tank j (a, = 0 if / ? E0).
Let c, be the ævalueÆ of tank j. Depending on whether we take v, = I or Vj = Qj, maximizing the sum of the ævaluesÆ of the tanks remaining empty corresponds to objectives (i) and (ii) respectively.
The loading problem stated above is related to the multiple-knapsack or æloadingÆ problem (Eilon and Christofides, 1971; Johnson, 1974; Lev, 1972). The following simple observation reduces and simplifies the problem to be considered: Previous << 1 .. 122 123 124 125 126 127 < 128 > 129 130 131 132 133 134 .. 156 >> Next 