0
52kviews
Explain Optimal storage on tape example.
4
1.3kviews

Optimal storage problem:

Input: We are given ‘n’ problem that are to be stored on computer tape of length L and the length of program i is Li

Such that 1 ≤i≤ n and Σ 1≤k≤j Li≤ 1

Output: A permutation from all n! For the n programs so that when they are stored on tape in the order the MRT is minimized.

Example:

Let n = 3, (l1, l2, l3) = (8, 12, 2). As n = 3, there are 3! =6 possible ordering.

All these orderings and their respective d value are given below:

Ordering d (i) Value
1, 2, 3 8 + (8+12) + (8+12+2) 50
1, 3, 2 8 + 8 + 2 + 8 + 2 + 12 40
2, 1, 3 12 + 12 + 8 +12 + 8 + 2 54
2, 3, 1 12 + 12 +2 +12 + 2 + 8 48
3, 1, 2 2 + 2 + 8 + 2 + 8+ 12 34
3, 2, 1 2 + 2 +12 + 2 + 12 + 8 38

The optimal ordering is 3, 1, 2.

The greedy method is now applied to solve this problem. It requires that the programs are stored in non-decreasing order which can be done in O (nlogn) time.

Greedy solution:

i. Make tape empty

ii. Fori = 1 to n do;

iii. Grab the next shortest path

iv. Put it on next tape.

The algorithm takes the best shortest term choice without checking to see whether it is a big long term decision.

Algorithm:

For example, find an optimal placement for 13 programs on 3 tapes T0, T1 & T2 where the program are of lengths 12, 5, 8, 32, 7, 5, 18, 26, 4, 3, 11, 10 and 6.

Given problem:

Length 12 5 8 32 7 5 18 26 4 3 11 10 6
Program [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

We organize the program as:

Length 3 4 5 6 7 8 9 10 11 12 18 26 32
Program [8] [9] [1] [5] [12] [4] [2] [11] [10] [0] [6] [7] [3]
2

You can also watch this on youtube to understand this problem better.