Optimal Storage on Tapes – Solving using Greedy Approach

Optimal Storage on Tapes Problem: Given n programs P1, P2, …, Pn of length L1, L2, …, Ln 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 Pj is computed as,

Optimal Storage on Tapes

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 Tapes

Optimal storage on tape is minimization problem which,

Optimal Storage on Tapes

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.
OrderingMean 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(n2)

This algorithm runs in O(n2) 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 :

PiP1P2P3P4P5P6P7P8P9P10P11P12P13
Li12345673241134567891349145

First sort the programs in increasing order of their size.

Sorted data:

PiP6P1P5P2P7P11P13P3P8P4P9P10P12
Li11122434343445565673789191

Now distribute the files among all three tapes.

Tape 1P6P2P13P4P12
Tape 2P1P7P3P9 
Tape 3P5P11P8P10 

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

= 563 / 5

= 112.6

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

= 340 / 4

= 85

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

= 353 / 4

= 88.25

MRT = (MRTTape3+ MRTTape3+ MRTTape3) / 3

= (112.6 + 85 + 88.25) / 3

= 95.28

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


Additional Reading: Read on Ques10

You may also like...

Leave a Reply

Your email address will not be published.