# Dispatching-Rule Variants Algorithms for Used Spaces of Storage Supports

Authors: Hani Alquhayz; Mahdi Jemmali; Mohammad Mahmood Otoom
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

The paper is regarding the fair distribution of several files having different sizes to several storage supports. With the existence of several storage supports and different files, we search for a method that makes an appropriate backup. The appropriate backup guarantees a fair distribution of the big data (files). Fairness is related to the used spaces of storage support distribution. The problem is how to find a fair method that stores all files on the available storage supports, where each file is characterized by its size. We propose in this paper some fairness methods that seek to minimize the gap between used spaces of all storage supports. In this paper, several algorithms are developed to solve the proposed problem, and the experimental study shows the performance of these developed algorithms.


---

## Body

## 1. Introduction

The manner that ensures the storage process is a primordial issue. Indeed, facing big data and few storage supports, it is important to seek a method that stores all given files in these storage supports. These methods must guarantee an equity distribution of the files in the available storage supports. We mention that the equity distribution can be called file size balancing. The file size balancing depends on some scheduling algorithms to guarantee a minimum gap between the used spaces of the storage supports. In the nonbalancing case, we face a problem where some storage supports have high used space, and at the same time, some storage supports probably have low used space. To avoid these cases, appropriate scheduling algorithms can be applied. In this paper, we proposed some balancing algorithms to obtain an equity distribution of the files to the storage supports, as far as we know this problem is never studied in the literature review. Some research works related to the balancing process can be cited. Singh et al. [1] proposed a dynamic load balancing algorithm of strongly connected servers, which takes into account these servers capability of parallel processing and their request queuing capacity in order to classify the overloaded servers and the least loaded servers, and once a server gets overloaded, its load is migrated to the least loaded one. In [2], Hung et al. introduced an enhancement of the max-min scheduling algorithm by decreasing the completion time of the clients’ requests; this algorithm uses a “supervised machine learning” that clusters utilization percent of virtual machines and clusters size of requests, and then the virtual machine which has the least utilization percent is appointed to the largest cluster requests. However, another work innovated new strategy increases the utilization of virtual machines in an efficient way. This strategy is a heuristic based on a load balancing algorithm which is applied on infrastructure as a service cloud [3]. Besides, Ragmani et al. [4] devised another new strategy of load balancing to increase cloud performance. On the contrary, another work integrated a load balancing algorithm to resource scheduling to provide a higher quality of cloud service [5]. In [6], Hung et al. proposed a load balancing algorithm called max-min and max algorithm that computes the average completion time for every task in all nodes, and then the task with the maximum average completion time is dispatched to the unassigned node with the minimum completion time which is less than the task maximum average completion time. The work in [7] focuses on maintaining information about every virtual machine efficiency in an allocation table that resides in a data center, by increasing the allocation count for an efficient virtual machine which has been allocated by a request and decreasing its allocation count after completing that request. Some other works apply balancing algorithms to solve real-life problems. Indeed, Jemmali et al. [8, 9] treated the problem of gas turbine aircraft engines. However, Jemmali [10] focused on the equity distribution of projects revenues assignment. In the latter work, authors proposed several approximate solutions to solve the problem. Several other works treated the problem of balancing in different applications. Hasan et al. [11] applied balancing algorithm on small-cell networks to adjust handover parameters of the overloaded cells with adjacent cells. However, the balancing algorithm was applied on voltage loads of capacitors in a modular multilevel converter [12].Xu et al. [13] introduced a technique that rewrites data blocks and defragments the backups of VM images as well as the authors proposed a technique for restoration of VM image backups by caching these data blocks. However, in [14], Xu et al. proposed a method based on enhanced k-means clustering that finds VM images of duplicated segments to be selected, and then these VM images can be loaded into memory.Jain and You and Koseki and Ogawa [15, 16] proposed a method of load balancing of a set of nodes within the cluster storage system. This method identifies a source node and target node based on a threshold value of the load as well as a proximity between the source and target nodes. This method chooses the data objects to be moved from the source node to the target node without exceeding the threshold value of load in the target node after moving these data objects.Besides, Gulati et al. [17] introduced a software system which handles the placement of virtual machines and implement load balancing between several devices automatically by applying migrations of data between devices and without the need to the storage arrays.In [18], Hu et al. introduced a load balancing strategy of VM resources using genetic algorithm and the system previous data and its current state. This strategy selects the best load balancing and alleviates or gets rid of dynamic migration.However, Aerts et al. [19] proposed models of load balancing that can be done based on NP-hard retrieval time as well as blocks basis.In this paper, our study focused on distributed load balancing algorithms, due to using the centralized algorithms limit the scalability in the future as well as they make the system less fault tolerable. Besides, our algorithms deal with a batch of files that need to be stored in temporary storage, and depending on the system planned backup timeT, the load balancer is triggered. Therefore, number of files is not a matter.This paper is organized as follows. In Section2, we present the studied problem and we give some details about the problem in general. Section 3 presents six proposed algorithms for the studied problem, and the experimental results are presented in Section 4.


## 2. Problem Definition

The problem studied in this paper is the proposition of the fairness method that guarantees the fair distribution of several files to the storage supports. The problem can be presented as follows. LetF be the set of given files that must be stored on a fixed number of storage supports. The number of files is denoted by nf and the number of storage supports is denoted by ns. The set of storage supports is denoted by ST=st1,⋯,stns. Each file fj with j=1,⋯,nf is characterized by its size sj. When the file fj is stored, the cumulative file size is denoted by csj. The total used space for the storage support sti when all files are stored is denoted by Usi with i=1,⋯,ns. The minimum (maximum) used space after the termination of the backup procedure is denoted by Usmin (Usmax). Example 1 can illustrate the studied problem.Example 1.
Letnf=7 and ns=2. Table 1 represents the sizes for each file fj.
We seek to store the seven files on the two given storage supports. Applying an algorithm rule, the result is given in Figure1.
The results given by the scheduling shown in Figure1 are as follows. We store the files {2, 6, 3, 7} in storage support 1 and files {4, 5, 1} will be stored in storage support 2. Based on the latter schedule, the used space for storage support 1 is 33. However, storage support 2 has a used space of 24. The gap between storage support 1 and storage support 2 is Us1−Us2=9. Seeking to reduce the latter gap is our primordial objective in this research work. Thus, we must search for a schedule that reduces the gap with a more efficient value less than 9.Table 1
Size files values.
fjf1f2f3f4f5f6f7sj8310511713Figure 1
Size file-storages scheduling.


## 3. Approximate Solutions

Our objective in this paper is to minimize the gap between storage supports. To do that, we must, in the first step, define the gap in a general case. The gap can be calculated using different methods. We propose the indicator that can calculate the gap as follows: for each storage support, we subtract the minimum value of all used spaces from the used space of the corresponding storage support. Therefore, considering thens storage supports, the total capacity gap (TCg) is given by the following equation:(1)TCg=∑i=1nsUsi−Usmin.Our objective is to minimizeTCg given in equation (1).Based on the standard three-field notation in [20], the studied problem is denoted by PTCg.Proposition 1.
ThePTCg is an NP-hard problem.Proof.
SincePUsmin is NP-hard problem [21] the studied problem is NP-hard problem because TCg = ∑i=1nsUsi−Usmin.
To achieve the goal of the work, we propose several algorithms to give approximate solutions.
The proposed algorithms in this paper are based on three methods to solve the studied problems: the first method used the dispatching rules (nonincreasing sizes order algorithm (NISA) and nondecreasing sizes order algorithm (NDSA)), the second method is based on swapping approach (swapping nonincreasing-decreasing sizes order algorithm SIDA, swapping nondecreasing-increasing sizes order algorithm SDIA), the third type of method is more complicated and is based on a mixed approach between the largest files and smallest ones (swapping nonincreasing-decreasing sizes with order algorithm SIDAr, r-Swapping nondecreasing-increasing sizes with order algorithm SDIAr).


### 3.1. Nonincreasing Sizes Order Algorithm (NISA)

This algorithm is applied since all files are ordered by the nonincreasing order of its sizes. After that, we store the files which have the greatest size in the storage support that has the minimum used space.


### 3.2. Nondecreasing Sizes Order Algorithm (NDSA)

This algorithm is applied since all files are ordered by the nondecreasing order of its sizes. After that, we store the files which have the smallest size in the storage support that has the minimum used space.


### 3.3. Swapping Nonincreasing-Decreasing Sizes with Order AlgorithmSIDA

Instead to apply just one order (nonincreasing or nondecreasing), we adopt a mixture one by one. This means that for a first selection, we pick the file which has the largest size and for the second selection, we take the file which has the smallest size and so on until all the files are stored. This algorithm works in fact on swapping between two algorithms. The function that call the algorithmNISA, is denoted by NIS, and the function that call the algorithm NDSA is denoted by NDS. These two functions return the file index that satisfies the applied algorithm. The function Storej is responsible to store the file fj in the most available storage supports. The most available storage supports are the storage supports which have the minimum used space. The algorithm of SIDA is given in Algorithm 1.Algorithm 1: Swapping nonincreasing-decreasing algorithm: SIDA.
(1)
Setj=1, P=F(2)
whilej≤nfdo(3)
ifModj/2=1then(4)
k=NISP(5)
else(6)
k=NDSP(7)
end if(8)
Storek(9)
P=P\k(10)
j++(11)
end while


### 3.4. Swapping Nondecreasing-Increasing Sizes with Order AlgorithmSDIA

This algorithm is based on the same idea ofSIDA. The difference here is instead of beginning with the file that has the largest size, we inverse it and begin with the file that has the smallest size. The second file will be the one that has the largest size and so on.The algorithm ofSDIA is given in Algorithm 2.Algorithm 2: Swapping nondecreasing-increasing algorithm: SDIA.
(1)
Setj=1, P=F(2)
whilej≤nfdo(3)
ifModj/2=1then(4)
k=NDSP(5)
else(6)
k=NISP(7)
end if(8)
Storek(9)
P=P\k(10)
j++(11)
end while


### 3.5. Swapping Nonincreasing-Decreasing Sizes with Order AlgorithmSIDAr

This algorithm is based on the following idea. Instead of swapping files by files applied inSIDA, we select once the largest file and once the smallest file. The question is how the algorithm becomes if we go ahead for the swapping by two files or three files or r files.If we choose the 2-swapping, this means we select the two files having the largest sizes and we store it. After that, we select the two files having the smallest sizes and so on two by two.The algorithm of 2-swapping, which means thatr=2, is given in Algorithm 3.Algorithm 3:2-swapping algorithm: SIDA2.
(1)
Setj=1, P=F(2)
whilej≤nfdo(3)
fort=1tot=2do(4)
k=NISP(5)
Storek(6)
P=P\k(7)
j++(8)
ifj>nfthen(9)
Break;(10)
end if(11)
end for(12)
ifj<nfthen(13)
fort=1tot=2do(14)
k=NDSP(15)
Storek(16)
P=P\k(17)
j++(18)
ifj>nfthen(19)
Break;(20)
end if(21)
end for(22)
end if(23)
end whileAlgorithm3 can give the solution just for 2-swapping files. We can generalize Algorithm 3 by searching the solution when r>2. The algorithm for a predetermined r=t is given in Algorithm 4.Algorithm 4:t-swapping algorithm: SIDAt.
(1)
Setj=1, P=F(2)
whilej≤nfdo(3)
forit=1toit=tdo(4)
k=NISP(5)
Storek(6)
P=P\k(7)
j++(8)
ifj>nfthen(9)
Break;(10)
end if(11)
end for(12)
ifj≤nfthen(13)
forit=1toit=tdo(14)
k=NDSP(15)
Storek(16)
P=P\k(17)
j++(18)
ifj>nfthen(19)
Break;(20)
end if(21)
end for(22)
end if(23)
end whileThe performance and generalization of the abovementioned algorithm are based on the iteration of Algorithm4 several times, and then we select the best solution. This generalization will be given as Algorithm 5.Algorithm 5: Swapping nondecreasing-increasing algorithm: SIDAr.
(1)
fort=2tot=rdo(2)
gapt=SIDAtF(3)
end for(4)
gap=min2≤t≤rgapt(5)
Returngap


### 3.6.r-Swapping Nondecreasing-Increasing Sizes with Order Algorithm SDIAr

This algorithm has the same idea as the abovementioned algorithm. The difference here is instead of starting with the largest files, we start with the smallest files.In Algorithm5, we replace NISP by NDSP in instruction 4 and we replace NDSP by NISP in instruction 14. This modification will give the new algorithm SDIAt. In Algorithm 5, we modify SIDAtF by SDIAt in instruction 2, and then the new algorithm SDIAr will be obtained.


## 3.1. Nonincreasing Sizes Order Algorithm (NISA)

This algorithm is applied since all files are ordered by the nonincreasing order of its sizes. After that, we store the files which have the greatest size in the storage support that has the minimum used space.


## 3.2. Nondecreasing Sizes Order Algorithm (NDSA)

This algorithm is applied since all files are ordered by the nondecreasing order of its sizes. After that, we store the files which have the smallest size in the storage support that has the minimum used space.


## 3.3. Swapping Nonincreasing-Decreasing Sizes with Order AlgorithmSIDA

Instead to apply just one order (nonincreasing or nondecreasing), we adopt a mixture one by one. This means that for a first selection, we pick the file which has the largest size and for the second selection, we take the file which has the smallest size and so on until all the files are stored. This algorithm works in fact on swapping between two algorithms. The function that call the algorithmNISA, is denoted by NIS, and the function that call the algorithm NDSA is denoted by NDS. These two functions return the file index that satisfies the applied algorithm. The function Storej is responsible to store the file fj in the most available storage supports. The most available storage supports are the storage supports which have the minimum used space. The algorithm of SIDA is given in Algorithm 1.Algorithm 1: Swapping nonincreasing-decreasing algorithm: SIDA.
(1)
Setj=1, P=F(2)
whilej≤nfdo(3)
ifModj/2=1then(4)
k=NISP(5)
else(6)
k=NDSP(7)
end if(8)
Storek(9)
P=P\k(10)
j++(11)
end while


## 3.4. Swapping Nondecreasing-Increasing Sizes with Order AlgorithmSDIA

This algorithm is based on the same idea ofSIDA. The difference here is instead of beginning with the file that has the largest size, we inverse it and begin with the file that has the smallest size. The second file will be the one that has the largest size and so on.The algorithm ofSDIA is given in Algorithm 2.Algorithm 2: Swapping nondecreasing-increasing algorithm: SDIA.
(1)
Setj=1, P=F(2)
whilej≤nfdo(3)
ifModj/2=1then(4)
k=NDSP(5)
else(6)
k=NISP(7)
end if(8)
Storek(9)
P=P\k(10)
j++(11)
end while


## 3.5. Swapping Nonincreasing-Decreasing Sizes with Order AlgorithmSIDAr

This algorithm is based on the following idea. Instead of swapping files by files applied inSIDA, we select once the largest file and once the smallest file. The question is how the algorithm becomes if we go ahead for the swapping by two files or three files or r files.If we choose the 2-swapping, this means we select the two files having the largest sizes and we store it. After that, we select the two files having the smallest sizes and so on two by two.The algorithm of 2-swapping, which means thatr=2, is given in Algorithm 3.Algorithm 3:2-swapping algorithm: SIDA2.
(1)
Setj=1, P=F(2)
whilej≤nfdo(3)
fort=1tot=2do(4)
k=NISP(5)
Storek(6)
P=P\k(7)
j++(8)
ifj>nfthen(9)
Break;(10)
end if(11)
end for(12)
ifj<nfthen(13)
fort=1tot=2do(14)
k=NDSP(15)
Storek(16)
P=P\k(17)
j++(18)
ifj>nfthen(19)
Break;(20)
end if(21)
end for(22)
end if(23)
end whileAlgorithm3 can give the solution just for 2-swapping files. We can generalize Algorithm 3 by searching the solution when r>2. The algorithm for a predetermined r=t is given in Algorithm 4.Algorithm 4:t-swapping algorithm: SIDAt.
(1)
Setj=1, P=F(2)
whilej≤nfdo(3)
forit=1toit=tdo(4)
k=NISP(5)
Storek(6)
P=P\k(7)
j++(8)
ifj>nfthen(9)
Break;(10)
end if(11)
end for(12)
ifj≤nfthen(13)
forit=1toit=tdo(14)
k=NDSP(15)
Storek(16)
P=P\k(17)
j++(18)
ifj>nfthen(19)
Break;(20)
end if(21)
end for(22)
end if(23)
end whileThe performance and generalization of the abovementioned algorithm are based on the iteration of Algorithm4 several times, and then we select the best solution. This generalization will be given as Algorithm 5.Algorithm 5: Swapping nondecreasing-increasing algorithm: SIDAr.
(1)
fort=2tot=rdo(2)
gapt=SIDAtF(3)
end for(4)
gap=min2≤t≤rgapt(5)
Returngap


## 3.6.r-Swapping Nondecreasing-Increasing Sizes with Order Algorithm SDIAr

This algorithm has the same idea as the abovementioned algorithm. The difference here is instead of starting with the largest files, we start with the smallest files.In Algorithm5, we replace NISP by NDSP in instruction 4 and we replace NDSP by NISP in instruction 14. This modification will give the new algorithm SDIAt. In Algorithm 5, we modify SIDAtF by SDIAt in instruction 2, and then the new algorithm SDIAr will be obtained.


## 4. Case Study

In this case study, we give the comparison betweenNISA and all other heuristics expected NDSA because for 100% of cases, NISA is better. So, we show a case study of instances that our proposed algorithms are better than NISA.


### 4.1. Comparison ofNISA and SIDAr

Let the instance with 10 files be assigned to 2 storage supports. The sizes of the 10 files are given in Table2.Table 2
Size files values for the case study.
fjf1f2f3f4f5f6f7f8f9f10sj2512582801772491251268120207This case study is given for the first execution of the algorithmNISA. This means the used space is zero for both storage 1 and storage 2.The first step of theNISA algorithm is ordering the files in a nonincreasing way. This gives the following order of a batch of files f3,f8,f2,f1,f7,f10,f4,f9,f6,f5.The steps ofNISA algorithm are as follows: the largest file f3 will be placed in the storage support with minimum used space. Storage 1 is selected. Then, the second largest file f8 is placed in storage 2 which is the one with minimum used space at this point. After that, the third file f2 will be assigned to storage 2 because it has the minimum used space at this point (storage 1 : 280, storage 2 : 268). Now, the used space in storage 2 is 526 and so on.Therefore, the schedule given by applying the algorithmNISA is as follows: in storage 1, NISA assigned the files f3,f1,f10,f4,f5. So, the total size assigned to this storage support is 939. However, in storage 2, the algorithm assigned the files f8,f2,f7,f9,f6. So, the total size assigned to storage support 2 is 988. Therefore, the gap between storages is(2)TCgNISA=∑i=12Usi−Usmin=939−939+988−939=49.On the contrary, applying the algorithmSIDAr, the schedule is given as follows: in storage 1, SIDAr assigned the files f3,f5,f6,f7,f9,f10. So, the total size assigned to this storage support is 973. However, in storage 2, the algorithm assigned the files f1,f2,f4,f8. So, the total size assigned to storage support 2 is 954. Therefore, the gap between storages is(3)TCgSIDAr=∑i=12Usi−Usmin=973−954+954−954=19.It is clear to observe thatgSIDAr is less than gNISA. Therefore, by comparing the results given by the algorithms NISA and SIDAr, the difference is 30. Thus, SIDAr gives the minimum gap.


### 4.2. Comparison ofNISA and SIDA

Let the instances with 10 files be assigned to 2 storage supports. The sizes of the 10 files are given in Table3.Table 3
Size files values for the case study.
fjf1f2f3f4f5f6f7f8f9f10sj6468228629296432837The schedule given by applying the algorithmNISA is as follows: in storage 1, NISA assigned the files f7,f5,f2,f10,f4. So, the total size assigned to this storage support is 269. However, in storage 2, the algorithm assigned the files f6,f3,f8,f9,f1. So, the total size assigned to storage support 2 is 251. Therefore, the gap between storages is(4)TCgNISA=∑i=12Usi−Usmin=269−251+251−251=18.On the contrary, applying the algorithmSIDA, the schedule is given as follows: in storage 1, SIDA assigned the files f7,f4,f9,f5,f2. So, the total size assigned to this storage support is 260. However, in storage 2, the algorithm assigned the files f1,f6,f3,f10,f8. So, the total size assigned to storage support 2 is 260. Therefore, the gap between storages is(5)TCgSIDA=∑i=12Usi−Usmin=260−260+260−260=0.It is clear to observe thatTCgSIDA is less than TCgNISA. Therefore, by comparing the results given by the algorithms NISA and SIDA, the difference is 18. Thus, SIDA gives the minimum and optimal gap because TCgSIDA=0.


### 4.3. Comparison ofNISA and SDIA

Let the instance with 10 files be assigned to 3 storage supports. The sizes of the 10 files are given in Table4.Table 4
Size files values for the case study.
fjf1f2f3f4f5f6f7f8f9f10sj45402724383919833042The schedule given by applying the algorithmNISA is as follows: in storage 1, NISA assigned the files f8,f9,f7. So, the total size assigned to this storage support is 132. However, in storage 2, the algorithm assigned the files f1,f6,f3,f4 and the total size assigned to this storage support is 135. For the third storage, the assigned files will be f10,f2,f5 and the total size assigned to the latter storage support is 120. Therefore, the gap between storages is(6)TCgNISA=∑i=13Usi−Usmin=132−120+135−120+120−120=27.On the contrary, applying the algorithmSDIA, the schedule is given as follows: in storage 1, SDIA assigned the files f7,f1,f9,f6. So, the total size assigned to this storage support is 131. However, in storage 2, the algorithm assigned the files f8,f2. So, the total size assigned to storage support 2 is 123. In storage 3, SDIA assigned the files f4,f3,f10,f5. So, the total size assigned to this storage support is 131. Therefore, the gap between storages is(7)TCgSDIA=∑i=13Usi−Usmin=133−123+123−123+131−123=18.It is clear to observe thatTCgSDIA is better than TCgNISA. Therefore, by comparing the results given by the algorithms NISA and SDIA, the difference is 9. Thus, SDIA gives the minimum gap.


### 4.4. Comparison ofNISA and SDIAr

Let the instances with 10 files be assigned to 2 storage supports. The sizes of the 10 files are given in Table5.Table 5
Size files values for the case study.
fjf1f2f3f4f5f6f7f8f9f10sj9909929491034937101399510099891022The schedule given by applying the algorithmNISA is as follows: in storage 1, NISA assigned the files f4,f8,f2,f9,f5. So, the total size assigned to this storage support is 4961. However, in storage 2, the algorithm assigned the files f10,f6,f7,f1,f3. So, the total size assigned to storage support 2 is 4969. Therefore, the gap between storages is(8)TCgNISA=∑i=12Usi−Usmin=4961−4961+4969−4961=8.On the contrary, applying the algorithmSDIAr, the schedule is given as follows: in storage 1, SDIAr assigned the files f5,f9,f2,f4,f6. So, the total size assigned to this storage support is 4965. However, in storage 2, the algorithm assigned the files f3,f1,f7,f10,f8. So, the total size assigned to storage support 2 is 4965. Therefore, the gap between storages is(9)TCgSDIAr=∑i=12Usi−Usmin=4965−4965+4965−4965=0.It is clear to observe thatTCgSDIAr is better than TCgNISA. Therefore, by comparing the results given by the algorithms NISA and SDIAr, the difference is 8. Thus, SDIAr gives the minimum and optimal gap because TCgSDIAr=0.Inspired from this case study, we proposed to apply our algorithms on a cloud computing domain by adding a new component called “scheduler” in the architecture of the cloud computing. This component will be responsible for applying the proposed algorithms and it gives the optimal schedule.


## 4.1. Comparison ofNISA and SIDAr

Let the instance with 10 files be assigned to 2 storage supports. The sizes of the 10 files are given in Table2.Table 2
Size files values for the case study.
fjf1f2f3f4f5f6f7f8f9f10sj2512582801772491251268120207This case study is given for the first execution of the algorithmNISA. This means the used space is zero for both storage 1 and storage 2.The first step of theNISA algorithm is ordering the files in a nonincreasing way. This gives the following order of a batch of files f3,f8,f2,f1,f7,f10,f4,f9,f6,f5.The steps ofNISA algorithm are as follows: the largest file f3 will be placed in the storage support with minimum used space. Storage 1 is selected. Then, the second largest file f8 is placed in storage 2 which is the one with minimum used space at this point. After that, the third file f2 will be assigned to storage 2 because it has the minimum used space at this point (storage 1 : 280, storage 2 : 268). Now, the used space in storage 2 is 526 and so on.Therefore, the schedule given by applying the algorithmNISA is as follows: in storage 1, NISA assigned the files f3,f1,f10,f4,f5. So, the total size assigned to this storage support is 939. However, in storage 2, the algorithm assigned the files f8,f2,f7,f9,f6. So, the total size assigned to storage support 2 is 988. Therefore, the gap between storages is(2)TCgNISA=∑i=12Usi−Usmin=939−939+988−939=49.On the contrary, applying the algorithmSIDAr, the schedule is given as follows: in storage 1, SIDAr assigned the files f3,f5,f6,f7,f9,f10. So, the total size assigned to this storage support is 973. However, in storage 2, the algorithm assigned the files f1,f2,f4,f8. So, the total size assigned to storage support 2 is 954. Therefore, the gap between storages is(3)TCgSIDAr=∑i=12Usi−Usmin=973−954+954−954=19.It is clear to observe thatgSIDAr is less than gNISA. Therefore, by comparing the results given by the algorithms NISA and SIDAr, the difference is 30. Thus, SIDAr gives the minimum gap.


## 4.2. Comparison ofNISA and SIDA

Let the instances with 10 files be assigned to 2 storage supports. The sizes of the 10 files are given in Table3.Table 3
Size files values for the case study.
fjf1f2f3f4f5f6f7f8f9f10sj6468228629296432837The schedule given by applying the algorithmNISA is as follows: in storage 1, NISA assigned the files f7,f5,f2,f10,f4. So, the total size assigned to this storage support is 269. However, in storage 2, the algorithm assigned the files f6,f3,f8,f9,f1. So, the total size assigned to storage support 2 is 251. Therefore, the gap between storages is(4)TCgNISA=∑i=12Usi−Usmin=269−251+251−251=18.On the contrary, applying the algorithmSIDA, the schedule is given as follows: in storage 1, SIDA assigned the files f7,f4,f9,f5,f2. So, the total size assigned to this storage support is 260. However, in storage 2, the algorithm assigned the files f1,f6,f3,f10,f8. So, the total size assigned to storage support 2 is 260. Therefore, the gap between storages is(5)TCgSIDA=∑i=12Usi−Usmin=260−260+260−260=0.It is clear to observe thatTCgSIDA is less than TCgNISA. Therefore, by comparing the results given by the algorithms NISA and SIDA, the difference is 18. Thus, SIDA gives the minimum and optimal gap because TCgSIDA=0.


## 4.3. Comparison ofNISA and SDIA

Let the instance with 10 files be assigned to 3 storage supports. The sizes of the 10 files are given in Table4.Table 4
Size files values for the case study.
fjf1f2f3f4f5f6f7f8f9f10sj45402724383919833042The schedule given by applying the algorithmNISA is as follows: in storage 1, NISA assigned the files f8,f9,f7. So, the total size assigned to this storage support is 132. However, in storage 2, the algorithm assigned the files f1,f6,f3,f4 and the total size assigned to this storage support is 135. For the third storage, the assigned files will be f10,f2,f5 and the total size assigned to the latter storage support is 120. Therefore, the gap between storages is(6)TCgNISA=∑i=13Usi−Usmin=132−120+135−120+120−120=27.On the contrary, applying the algorithmSDIA, the schedule is given as follows: in storage 1, SDIA assigned the files f7,f1,f9,f6. So, the total size assigned to this storage support is 131. However, in storage 2, the algorithm assigned the files f8,f2. So, the total size assigned to storage support 2 is 123. In storage 3, SDIA assigned the files f4,f3,f10,f5. So, the total size assigned to this storage support is 131. Therefore, the gap between storages is(7)TCgSDIA=∑i=13Usi−Usmin=133−123+123−123+131−123=18.It is clear to observe thatTCgSDIA is better than TCgNISA. Therefore, by comparing the results given by the algorithms NISA and SDIA, the difference is 9. Thus, SDIA gives the minimum gap.


## 4.4. Comparison ofNISA and SDIAr

Let the instances with 10 files be assigned to 2 storage supports. The sizes of the 10 files are given in Table5.Table 5
Size files values for the case study.
fjf1f2f3f4f5f6f7f8f9f10sj9909929491034937101399510099891022The schedule given by applying the algorithmNISA is as follows: in storage 1, NISA assigned the files f4,f8,f2,f9,f5. So, the total size assigned to this storage support is 4961. However, in storage 2, the algorithm assigned the files f10,f6,f7,f1,f3. So, the total size assigned to storage support 2 is 4969. Therefore, the gap between storages is(8)TCgNISA=∑i=12Usi−Usmin=4961−4961+4969−4961=8.On the contrary, applying the algorithmSDIAr, the schedule is given as follows: in storage 1, SDIAr assigned the files f5,f9,f2,f4,f6. So, the total size assigned to this storage support is 4965. However, in storage 2, the algorithm assigned the files f3,f1,f7,f10,f8. So, the total size assigned to storage support 2 is 4965. Therefore, the gap between storages is(9)TCgSDIAr=∑i=12Usi−Usmin=4965−4965+4965−4965=0.It is clear to observe thatTCgSDIAr is better than TCgNISA. Therefore, by comparing the results given by the algorithms NISA and SDIAr, the difference is 8. Thus, SDIAr gives the minimum and optimal gap because TCgSDIAr=0.Inspired from this case study, we proposed to apply our algorithms on a cloud computing domain by adding a new component called “scheduler” in the architecture of the cloud computing. This component will be responsible for applying the proposed algorithms and it gives the optimal schedule.


## 5. Experimental Results

In this section, we propose different classes of instances to compare the performance of proposed algorithms. The main comparison in this paper is that we compare the developed algorithms with theNISA algorithm. The NISA algorithm is used in the literature review as LPT algorithm which has several applications in the industry.The proposed algorithms in this paper were coded and executed by Microsoft Visual C++ (Version 2013). The computer that is utilized to run all programs coded in C++ has the characteristics as follows:(i)
Processor: Intel® Core™ i5-3337U CPU @ 1.8 GHz.(ii)
Operating system: Windows 10.We adopt the choice that the classes used to discuss the results obtained by the developed algorithms are inspired by the classes proposed in [21].The generation of the file sizessj will be through two kinds of distributions. The unit of the size is proposed as Mo. The studied classes are given as follows:(i)
Class A:sj is in U1,100(ii)
Class B:sj is in U10,300(iii)
Class C:sj is in U500,1500(iv)
Class D:sj is in U50,250(v)
Class E:sj is in U25,1000U is the uniform distribution and N is the normal distribution. The total number of generated instances depends on the choice of nf, ns, and class. The pair (nf, ns) can have different permutation values. The determination of the (nf, ns) values is given in Table 6.Table 6
Size files and storage supports pair choice.
nfns10,20,25,502,3,5100,150,250,300,5002,3,5,10,15,20,25,301000,1500,2000,2500,3000,35002,3,5,10,15,20,25,30,50From Table6, we can deduce that there are 5300 instances in total. To show the performance of the developed algorithms compared to the oldest LPT one, we can use several indicators. Thus, we propose the following indicators for this paper:(i)
H is the best algorithm returned value after running all heuristics.(ii)
Hd is the discussed heuristic.(iii)
GH = Hd−H/Hd, if Hd=0, we have GAP=0.(iv)
Time is the average running time. This time will be in seconds. The symbol “−” means that the time is less than 0.001 s.(v)
Per is the percentage among the total instances (5300) that the constraint Hd=H is obtained.Several statistics can be presented in this work. We start by the overall Table7 that shows the percentage of each heuristic when the studied heuristic equals to the best one. The corresponding average time is calculated for each heuristic in Table 7. The algorithm SIDAr is the best one among all algorithms with percentage 75.2% and average time 0.115s. However, the algorithm NISA has 45.2% and NDSA has 0%. The algorithm that consumes more running time compared with others is SIDAr.Table 7
Overall view of algorithm results.
NISANDSASIDASDIASIDArSDIArPer (%)45.20.010.60.875.241.0Time————0.1150.108Table8 presents the behavior of GH and time when the number of files is changed. For all algorithms, when the number of files increases, the Time increases. The worst GH value which is equal to 0.99 is obtained for the algorithm NDSA when nf=3000. However, the best gap 0.09 is obtained for algorithm SIDAr when nf=2500 (Table 9).Table 8
The behavior ofGH and time when the number of files is changed.
nfNISANDSASIDASDIASIDArSDIArGHTimeGHTimeGHTimeGHTimeGHTimeGHTime100.15—0.73—0.49—0.67—0.10—0.33—200.40—0.85—0.60—0.80—0.22—0.34—250.36—0.82—0.79—0.58—0.24—0.44—500.40—0.90—0.69—0.86—0.20—0.41—1000.35—0.85—0.75—0.82—0.150.0010.340.0011500.43—0.94—0.84—0.92—0.250.0010.310.0012500.36—0.88—0.75—0.85—0.160.0030.330.0023000.36—0.97—0.86—0.96—0.200.0040.360.0035000.35—0.91—0.78—0.89—0.120.0100.390.00810000.34—0.91—0.79—0.89—0.090.0420.360.03915000.36—0.98—0.88—0.98—0.140.0910.440.09220000.38—0.93—0.80—0.91—0.120.1590.380.14425000.31—0.92—0.79—0.90—0.090.2500.390.22430000.350.0010.990.0010.87—0.980.0010.140.3400.400.31935000.360.0010.930.0010.800.0010.910.0010.100.4610.390.444Table 9
The behavior ofGH and time when the number of storage supports is changed.
nsNISANDSASIDASDIASIDArSDIArGHTimeGHTimeGHTimeGHTimeGHTimeGHTime20.41—0.98—0.24—0.94—0.130.0130.460.01230.31—0.81—0.75—0.75—0.100.0160.370.01550.26—0.93—0.93—0.92—0.230.0230.280.021100.42—0.99—0.98—0.98—0.060.0670.500.059150.30—0.84—0.80—0.80—0.140.1010.310.091200.42—0.95—0.94—0.94—0.110.1580.470.161250.38—0.95—0.95—0.95—0.330.1910.210.179300.33—0.85—0.82—0.82—0.080.2190.360.206500.460.0010.990.0010.980.0010.980.0010.110.5570.430.517Table10 represents the behavior of GH and Time when the number of classes is changed. It is noticed that the worst gap is 0.98 when the NDSA algorithm is applied to class A. On the contrary, the SIDAr algorithm achieved the best gap in the same class which equals 0.02. The table also shows that the best execution time is less than 0.001s for the algorithms NISA, NDSA, SIDA, and SDIA. However, the algorithms SIDAr and SDIAr have the worse execution times which are larger than 0.1s, and the highest execution time is 0.125 s for SIDAr algorithm when it is applied to class C.Table 10
The behavior ofGH and time when the number of classes is changed.
ClassNISANDSASIDASDIASIDArSDIArGHTimeGHTimeGHTimeGHTimeGHTimeGHTimeA0.05—0.98—0.85—0.95—0.020.1100.530.107B0.17—0.97—0.85—0.94—0.060.1160.430.108C0.29—0.95—0.85—0.92—0.080.1250.440.110D0.68—0.92—0.77—0.87—0.310.1140.260.109E0.59—0.77—0.65—0.77—0.250.1110.220.107For the algorithmSIDAr, we can observe that the gap is 0.31 and 0.25 for classes D and E, respectively. However, these values are higher than the gap values of classes A, B, and C which are less than 0.1.


## 6. Conclusion

In this paper, we focused our study on the resolution of the NP-hard problem of assignment of several files to different storage supports. We developed six algorithms to solve the latter problem; these algorithms are essentially based on the dispatching rules with variant methods. These methods are categorized into the nonincreasing (decreasing) order rule and the mixture method that uses both the nonincreasing and decreasing order rules. In addition, we proposed ther-swapping methods which are based on storing the first r files using the nonincreasing rule and then storing the next r files by applying the nondecreasing rule and so on until storing all files. In this paper, we chose the number r which equals nf−1. The experimental results show that the best algorithm is SIDAr, which outperforms the old algorithms in the literature review. The proposed algorithms can be enhanced to develop more performed new algorithms.



---

*Source: 1072485-2020-06-13.xml*