Optimal Storage on Tapes – Solving using Greedy Approach

Optimal Storage on Tapes Problem: Given n programs P₁, P₂, …, P_n of length L₁, L₂, …, L_n respectively, store them on a tap of length L such that Mean Retrieval Time (MRT) is a minimum. The retrieval time of the jth program is a summation of the length of first j programs on tap. Let Tj be the time to retrieve program Pj. The retrieval time of P_j is computed as,

Mean retrieval time of n programs is the average time required to retrieve any program. It is required to store programs in an order such that their Mean Retrieval Time is minimum. MRT is computed as,

Optimal storage on tape is minimization problem which,

Storage on Single Tape

• In this case, we have to find the permutation of the program order which minimizes the MRT after storing all programs on single tape only.
• There are many permutations of programs. Each gives a different MRT. Consider three programs (P1, P2, P3) with a length of (L1, L2, L3) = (5, 10, 2).
• Let’s find the MRT for different permutations. 6 permutations are possible for 3 items. The Mean Retrieval Time for each permutation is listed in the following table.

Ordering	Mean Retrieval Time (MRT)
P1, P2, P3	( (5) + (5 + 10) + (5 + 10 + 2) ) / 3 = 37 / 3
P1, P3, P2	( (5) + (5 + 2) + (5 + 2 + 10) ) = 29 / 3
P2, P1, P3	( (10) + (10 + 5) + (10 + 5 + 2) ) = 42 / 3
P2, P3, P1	( (10) + (10 + 2) + (10 + 2 + 5) ) = 39 / 3
P3, P1, P2	( (2) + (2 + 5) + (2 + 5 + 10) ) = 26 / 3
P3, P2, P1	( (2) + (2 + 10) + (2 + 10 + 5) ) = 31 / 3

• It should be observed from the above table that the MRT is 26/3, which is achieved by storing the programs in ascending order of their length.
• Thus, greedy algorithm stores the programs on tape in non-decreasing order of their length, which ensures the minimum MRT.

Algorithm for Optimal Storage on Tapes

Let L be the array of program length in ascending order. The greedy algorithm finds the MRT as following:

Algorithm Algorithm MRT_SINGLE_TAPE(L)
// Description : Find storage order of n programs to such that mean retrieval time is minimum
// Input : L is array of program length sorted in ascending order
// Output : Minimum Mean Retrieval Time

Tj ← 0
for i ← 1 to n do
    for j ← 1 to i do
        Tj ← Tj + L[j]
    end
end
MRT ← Tj/ n

Complexity analysis of Optimal Storage on Tapes

Primitive operation in above algorithm is the addition of program length, which is enclosed within two loops. The running time of algorithm is given by,

T(n) = O(n²)

This algorithm runs in O(n²) time.

Storage on Multiple Tapes

• This is the problem of minimizing MRT on retrieval of the program from multiple tapes.
• Instead of a single tape, programs are to be stored on multiple tapes. Greedy algorithm solves this problem in a similar way. It sorts the programs according to increasing length of program and stores the program in one by one in each tape.
• The working of this approach is explained in the following example.

Example

Example: Given the program lengths L = {12, 34, 56, 73, 24, 11, 34, 56, 78, 91, 34, 91, 45}. Store them on three taps and minimize MRT

Solution:

Given data :

Pi	P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12	P13
Li	12	34	56	73	24	11	34	56	78	91	34	91	45

First sort the programs in increasing order of their size.

Sorted data:

Pi	P6	P1	P5	P2	P7	P11	P13	P3	P8	P4	P9	P10	P12
Li	11	12	24	34	34	34	45	56	56	73	78	91	91

Now distribute the files among all three tapes.

Tape 1	P6	P2	P13	P4	P12
Tape 2	P1	P7	P3	P9
Tape 3	P5	P11	P8	P10

MRT_Tape1 = ((11) + (11 + 34) + (11 + 34 + 45) + ((11 + 34 + 45 + 73)) + (11 + 34 + 45 + 73 + 91) ) / 4

= 563 / 5

= 112.6

MRT_Tape2 = ((12) + (12 + 34) + (12 + 34 + 56) + (12 + 34 + 56 + 78) ) / 4

= 340 / 4

= 85

MRT_Tape3 = ((24) + (24 + 34) + (24 + 34 + 56) + (24 + 34 + 56 + 91) ) / 4

= 353 / 4

= 88.25

MRT = (MRT_Tape3+ MRT_Tape3+ MRT_Tape3) / 3

= (112.6 + 85 + 88.25) / 3

= 95.28

Some Popular Problems Solved by Greddy Algorithm

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :

• Binary Knapsack Problem
• Fractional Knapsack Problem
• Job Scheduling Problem
• Activity Selection Problem
• Huffman Coding
• Optimal Storage on Tapes
• Optimal Merge Pattern
• Prim’s Algorithm
• Kruskal’s Algorithm
• Dijkstra’s Algorithm

---

Additional Reading: Read on Ques10