**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] |

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

written 2.2 years ago by | modified 5 months ago by |