3.1. Prerequisites

The first action to be taken by the scheduler in scheduling the tasks of the distributed systems is to identify the appropriate set of resources that perform the tasks. The resources that can be used to execute tasks as well as gain capabilities are identified based on some of the features gained through distributed systems intelligence. Therefore, in order to improve the situation and to reduce the impact of the above problem in the process of allocating tasks on resources to execute, we have used neural network capability in predicting the execution time of tasks and aiming to find a suitable solution based on the prediction of runtime as the key to achieve optimal scheduling in distributed systems. In order to realize the performance of the neural network are considered these parameters as reasons of impact on runtime, being independent of each other in measurement and control, simplicity of estimation or measurement and simplicity of calculation, the characteristics of the resources in the computing environment to predict the execution time in tasks. These parameters are considered as inputs of the artificial neural network, and by determining the weight in the middle layer of the neural network, the output will be the predicted completion time for the computing environment resources of the distributed systems. Quadratic properties of distributed computing environment sources derived from standard CPU-performance-dataset in the standard UCI data repository.

It should be noted, however, that with respect to the properties of computational resources, artificial neural networks can somewhat predict the execution time of tasks. This prediction value from the neural network output as a parameter of similarity, together with the cost required for each source, contributes to cluster the computing environment resources of the distributed systems. The resources within the clusters will have approximately similar features, and the user will be aware of the completion time (waiting time for their task) and the cost of each resource. The new task that comes up is assigned to a resource with the least expected completion time. The genetic algorithm is then implemented to optimize resource allocation tasks and reduce work completion time, and a resource queue with the least job completion time is anticipated for the newly assigned task and a resource queue that assigned for the completion time of the predicted task received the second rank as the primary population. The genetic algorithm, by jumping between these two queues, determines the most appropriate place where a new task can be added. The architecture of the proposed method is shown in Figure 1.

3.2. Proposed Scheduling Algorithm

The proposed method combines the strengths of the two genetic algorithms and the neural network in order to achieve a more optimal algorithm. These methods are combined in such a way that they cover each other's weaknesses so that they result in an integrated and optimized algorithm. Scheduling operations start by the neural network capability to predict the completion time of the tasks in terms of the four mentioned parameters in the previous sections. The structural features of the used neural network are as follows: (a) formation of 12 hidden layers, (b) application of the back-propagation algorithm, and (c) and application of evaluation function. This neural network is used in CPU-performance-dataset standard data of the standard UCI data repository, using MATLAB simulator based on learned resource attribute values and its suitable outputs in the task scheduling process to optimize the task mapping process.

3.2.2. Scheduling Tasks Based on Genetic Algorithms

As mentioned, in this research, genetic algorithm has been used to schedule the ranked tasks of the distributed system. Genetic algorithm is one of the effective optimization algorithms used in complex problems that are inspired by genetic and evolutionary mechanisms in natural systems. Genetic algorithm as a population-based meta-heuristic approach has different operators that generate optimized chromosomes from a primary random population. Genetic algorithm operators are essential for the convergence of population chromosomes toward optimal points. The genetic algorithm in the basic form has three main genetic operations of selection, crossover, and mutation. Some solutions are selected as chromosomes by the population selector operator as the parent and combine the appropriate parent operator to create offspring. Parents combine to replace several genes on the first chromosome with the second chromosome. The mutant operator also modifies the offspring according to the laws of mutation by changing the amount of one or more genes in the direction of the optimal solution.

Initial Population Creation: the first step in using a genetic algorithm is to encode and generate a random primary population. Coding refers to how genes are determined on chromosomes, where the arrangement of genes together leads to a solution to a scheduling problem. Therefore, each chromosome carries genes that are equal to the number of virtual machines. The index of each gene represents the virtual machine index, and the value inside the gene represents the task index. Figure 2 shows an example of the chromosomes presented in the proposed method. In this type of encoding, tasks are assigned to virtual machines.

In the proposed method, this type of coding is used in which the value of each gene represents the virtual task index. In the proposed method, since the tasks are ranked in the first step, but the distribution of values ​​within the genes is random, the processing power of the virtual machine is also considered as one of the parameters of the fit function of the genetic algorithm. Therefore, in chromosomes where high-ranking tasks are assigned to powerful resources to be processed faster, the value of the fit function will be more optimal.

Crossover and mutation algorithm in the proposed method: given that in the proposed method, input tasks are prioritized, and naturally, there should be a slight change in the fitting and jump operators so that the priority of performing tasks in cloud resources is not disturbed. Given that in optimal chromosomes, high-ranking tasks are allocated to powerful resources, fitting and mutation should be in line with improved scheduling. Therefore, in this method, the fitting point and the adaptive jump will be used. Thus, if one fitting point and mutation cause the value of the fit function to deteriorate, another fitting point and mutation will be selected for the chromosomes. This operation is repeated until the optimal fitting and jumping points are selected. In this case, we will be sure that the generation of chromosomes will evolve and converge towards the optimal points.

Proposed fitness function: as mentioned in the proposed method, we will use the multicriteria fit function. Criteria for use in the fit function will include task completion time, task length, and source processing power. The main purpose of the proportionality function is to reduce the completion time of all tasks in resources, also called Makespan. The most important purpose of the task scheduling is to minimize Makespan. Makespan equals the total required time to complete all input tasks. Each scheduler uses a performance-matching function to perform the scheduling. And by using time and cost parameters, it determines the suitability of different resources to perform a task. Relation (2) shows the fitness function considered for the proposed algorithm.

$$ (2)

where w_ti is the time required to complete task i in resource j,  w_ci is the cost required to complete task i in resource j, w_ri  is the estimated time based on the processing power of source j to perform task i, and  α is the cost threshold for performing tasks. In this function, the weight of the completion time and the performing cost of the task (wt and wc) are taken into account by the user. Time and cost are not of the same scale, and they are not in the same range; to solve this problem, we have to normalize them and mapped them in the range of zero to one. It should be noted that the weighting coefficients are specified by the user in introducing the task. W_t and W_c give more freedom to user in presenting his work to distributed systems. The purpose of the scheduler is to find a source j for each task i so that EF (t_i, r_j) be minimum.

The above objective function determines the source fitting of j to execute task i. As can be seen in the above function, the normalization of time and cost is multiplied by their weight. In the above function, t_max and t_min are the maximum and minimum completion times of tasks on the appropriate resources (in the previous sections are described the appropriate resource indicators). c_max and c_min are the maximum and minimum cost of executing tasks on appropriate resources. t_i,j and c_i,j are the time and cost of executing i task on j source. The execution time of tasks assigned to a resource is obtained by the relation as follows:

$$ (3)

$$ (4)

where the $$ parameter represents the length (number of instructions) of task i, JobCycle_j/Processorspeed_j determines the speed of resource processor j, and w_wi is the waiting time to access the resource $$ and number of tasks within the source queue. Running time is considered to be a 1  ^∗ M matrix where M is the number of resources. The value of the j-element of this matrix indicates the execution time of the tasks assigned to the source of the number j. Figure 3 shows an example of this matrix, in which the execution time of the assigned tasks to the second source is 250.

In each iteration, the updated population evaluated the produced solutions. This evaluation is based on the fitness function. To evaluate a member of the population (a solution to the problem), each of the independent input tasks is allocated to resources based on the strategy of the scheduling algorithm. After allocating tasks to resources, to determine what tasks are assigned to each resource and for each resource j, a 1 ∗ N matrix is called Job-CPUj (N is the number of independent input tasks). The values within the Job-CPUj matrix are the number of tasks assigned to the source j. Figure 4 shows an example of this matrix in which the first, second, and seventh tasks are assigned to source j.

The total execution time of tasks assigned to source j (tasks within the Job-CPUj matrix) is calculated by relation (3), and finally, the execution time of the tasks is calculated in each resource and placed in the running time matrix. Then, the maximum runtime in the running time matrix is considered as Makespan. The proposed method algorithm is shown in Table 1.

Table 1. Proposed method algorithm.

Proposed method algorithm
Input data:
F: similarity criteria features of processors;
C: similarity criteria features of clusters’ center;
N: number of processors;
T: the task with different process time;
Begin
For i = 1 to N
P = predict the end time of task in each processor's queue using neural network
D =  $$ ;//Clustering processors in different clusters, j = 1, 2, 3//End
For i = 1 to size of max cluster members (≈N/3).
G = GA(P,T)
Makespan = sum (G,P)
End

4.1. Performance Evaluation of Neural Networks

This paper assumes that a task has been handed over to users of distributed systems or other applications. The timing of these tasks is considered at random. A number of resident tasks are also randomly distributed in the queue of processors in the distributed systems where new tasks will be assigned to the processor upon completion of these tasks (waiting time of the processor to be assigned to the new task or the time that tasks are completed on the processor). As mentioned, the neural network has been used to predict the time of tasks completed in the queue of a processor consisting of three layers: input, midst (middle), and output. The input data contain CPU-related features to apply in the neural network input layer as shown in Figure 4. The neural network in the middle layer performs the process necessary to train the model on the received input data from the input layer and presents the results to the output layer. As mentioned in the previous chapter, the applied neural network structure uses the evaluation function, which is a function of error back-propagation to correct weights. Figure 5 shows the accuracy of the evaluation function.

As shown in Figure 5, the performance of the neural network using the evaluation function after 40 iterations is better both in model training and validation and in the test stage of trained samples (lines shown by dot).

In this study, another criterion used to evaluate the accuracy of the proposed model is the correct prediction rate of the samples in the model training stages: validation and experimental data of the model replication stages. For this purpose, a graph is drawn as confusion, which specifies the number of correctly classified data against the incorrect data classified in the training, validation, and testing stages of the data. Figure 6 shows the confusion diagram of the proposed model in steps.

As shown in Figure 6, the proposed neural network model in this study has correctly predicted 100% of training samples in the training phase, 87.5% of training samples in the validation stage, and 75% of experimental samples in the testing phase. Therefore, the average accuracy of the whole proposed neural network model to predict the completion time of tasks residing on the CPU is 94%.

4.2. Implementation of the Clustering Method

As mentioned, the K-means clustering method is one of the most popular unsupervised learning algorithms that solve the problem of well-structured clustering. This method looks for a simple and easy way to classify data according to a set of predetermined number of clusters (K cluster). The basic idea behind this method is to define the k as the central focal point, one for each cluster. This focal point should be chosen wisely because different situations give different results. Therefore, it can be concluded that the best choice is to keep them as far apart as possible. In this study, K is equal to 3, at which the focal point of the first cluster has the lowest value, the focal point of the second cluster has the midst data, and the focal point of the third cluster has the highest value. The clusters are divided into three clusters: cheap, medium, and economically expensive, based on the amount of time and cost of completing their tasks. The next step is to capture each point in the dataset and connect it to the nearest central point. When no point is waiting, the first stage is over, and the initial groups are formed. At this point, it is necessary to calculate the points at K of the new central point as the centerline of clusters delivered from the previous step. After obtaining this new K focal point, a new connection must be established between the same set of data points and the nearest new focal point. Hence, a loop is generated, and as a result of this loop, we may find that the central points of K in each time shift their position until a step is completed without any change. In other words, the focal point has no further movement. Table 2 shows resources allocated to clusters based on resource characteristics.

As shown in Table 2, the processors belong to a cluster that is less distant than the focal point of that cluster. Processors within identical clusters are very similar. If the CPUs in different clusters are more cost-effective and time-consuming, tasks delivered to the distributed system environment are driven to one of these clusters that are more in line with their preference, depending on user or application concerns about the cost and deadline of the tasks.

4.3. Performance Evaluation of Genetic Algorithm

As mentioned, the genetic algorithm is used to map the task in the appropriate processor to reduce the total execution time of a task. Therefore, it is expected that the total waiting time and task processing time before applying the genetic algorithm will be different compared to the same amount after applying the genetic algorithm and allocating tasks on the most appropriate processor to reduce runtime. Due to the evolution of solutions, the genetic algorithm converges to the optimal solution during the iteration steps. Figure 7 shows the convergence of the genetic algorithm towards the optimal solution.

As shown in Figure 7, the genetic algorithm achieves the optimal solution after the iteration steps. Based on the optimal solution in Gantt's proposed genetic algorithm, the assignment of tasks to resources is shown in Figure 8.

As shown in Figure 8, the computational tasks are assigned to the appropriate virtual machines based on the proposed method. Then, in Figure 9, the completion time of the tasks is compared based on the proposed method and the neural networks without using a genetic algorithm.

As shown in Figure 9, the time to complete tasks in each resource in the proposed method is less than the neural network without genetic algorithm for finding optimal resources. Therefore, resource selection is not optimal on the basis of resource processing power and the provision of server services and estimated time to complete tasks in resources, and the combination of time and cost in task allocation can make this approach more optimal. Figure 10 also shows the total execution time of all tasks under all sources in the neural network-based method and the proposed method.

As shown in Figure 10, the total execution time of all tasks under all sources plus the waiting time to release all resources in the neural-network-based approach without the use of genetic algorithm is greater than the sum of the same time in the proposed method. The graph of the proposed method is linearly increasing with a slope lower than the previous graph, with respect to the tasks in the queue and the allocation of tasks to the most appropriate resource using the genetic algorithm proportional function. As shown in Figure 9, the neural network combinatorial method and genetic algorithm improve the Makespan criterion better than the neural-network-based scheduling method. In other words, the total execution time of the assigned tasks in the proposed method is about 24% less than the neural-network-based scheduling method.

We also compare it with previous methods to evaluate the validity of the proposed method. As shown in Figure 9, the accuracy of the proposed method in distributed systems is optimized by allocating tasks to resources and combining the parameters in the form of a proportional function. The proposed method can now be compared with previous methods based on the same criteria with equal conditions. Therefore, Figure 11 shows the comparison of previous methods with the proposed method in this study based on the Makespan criterion.

As shown in Figure 11, the performance of the proposed method was better than other methods available in the journals in allocating tasks to resources and reducing the time required to perform the whole task. Therefore, the proposed method has a lower value for the Makespan criterion than previous methods and can adhere to the principles of service quality.