Algorithm Development Tips For Developing Hill Climbing Algorithm For Cloud-Based Task Scheduling

Dissertation Algorithm Development Ideas from Existing Recent Research Gaps in Computer Science Engineering Domain

In Brief

• You will find the best dissertation research areas / topics for future researchers enrolled in Engineering .
• In order to identify the future research topics, we have reviewed the Engineering literature (recent peer-reviewed studies) on the AI in optimization problems
• Cloud Computing included various tasks executed by the available resources to provide high performance and reduce the task completion time, etc.
• The task scheduling is an NP-hard (Nondeterministic Polynomial) problem in cloud computing.
• Task scheduling is a process of allocating tasks to available resources so that the performance metrics are improved.
• A dynamic scheduling algorithm that uses a hill-climbing algorithm to reduce the completion time of tasks while maximization of throughput and utilization of resources.
• Hill Climbing Algorithm for cloud-based task scheduling allocation of independent tasks to available resources in order to achieve the load balance.

Cloud computing is a platform of resource provisions and allowing consumers to utilize computing resources based on multiple service providers. The Cloud has basically involved a wide variety of resources and services that subsumed memory, storage, processing, and virtual machines. In Cloud Computing, task scheduling is an NP-hard problem and the metaheuristic technique was used to solve the issue of task scheduling. In recent times, evolutionary algorithms have been proposed such as hill climbing to optimize the solutions based on PSO and local search operators.

Hill-Climbing Algorithm

Hill-Climbing Algorithm is come under the category of meta-heuristic techniques and is a perfect approach to solve the NP-hard problems faced in the cloud-based task scheduling. Hill-Climbing Algorithm is an optimization technique to obtain a better solution and the advantage of using a technique is to utilize the resources based on a favourable feedback mechanism.

Proposed Hill-Climbing Algorithm Based Load Balancing and Reliability

If a user submits the tasks to the broker, it collects the tasks into a set and queries into the Cloud Information Services (CIS). The CIS produces all of the features regarding available resources like processing elements, VMs number, and rating of each PE. The broker makes use of the information in mapping operation based on a proposed hill-climbing algorithm.

Proposed Hill-Climbing Algorithm

Based on the hill-climbing algorithm, the broker saves each VM’s capability for mapping the operation of tasks. The capability weight sets on the creation of virtual machine VMj.
C_j (0)=〖P_〗_(〖num〗_j )*〖P_〗_(〖mips〗_j )
Where Cj (0) is the capability of VMj at time 0, processors number P_numj, and the processor’s capability number P_mipsj. The capability weight of VM is updated based on the allocation of any task or it is returned from VMj.
C_j (t)=C_j (t)+∆C_j (t)
Where Cj(t) is the variety of capability weight of the current VM and can be calculated as follows:
In the case of decrement, the capability weight is determined as ΔCj(t) = -Load when the task is mapped to VMj, where Load is the task computation workload.
When the task is accomplished and VMj is freed, the capability is incremented i.e. ΔCj(t) = Load.
We define the move on the side of the increasing value of proposed hill climbing for the next task mapping.
M_s (t)=〖〖arg 〗⁡〖〖max〗_(s∈VMS) 〗 {(C〗_s (t) )^r}
Where Ms (t) is the uphill move that chooses a suitable VM.
Cs (t) is VM’s current capability weight.
r is used as a control parameter for VM’s capability for weight relative importance.
s € Available and suitable VMs for the current task.

Load Balancing Factor

The rule of the uphill move is operating completely based on the performance of the VM, let’s say, if there is a high capability power for VM then it will be chosen with high desirability. That means it’s very important to balance the load for all running VMs.
To balance the load, the factor of the VMj load (LBs) is appended to uphill move rule during the selection of VM in order to compute the tasks to finish the rate. The modified equation is:
M_s (t)=〖〖arg 〗⁡〖〖max〗_(s∈allowedVMS) 〗 {(C〗_s (t) )^(r * ) LB_(s^(1-r) )}
Where LBs = 1/ETs, here ETs is the possible end time for VMs which representing the high VM load lead to a low opportunity for next task mapping.

The Reliability Factor

If any task is finished or failed or returned from VM, no need to make changes to steps of capability weight that means ignoring the faults and reliability of the VM.
In case of successful completion of the task on VM and VMj is free from the tasks, the updated capability weight is as follows:
C_j (t)=C_j (t)+L*SRF
Where SRF is the successful Reliability Factor that means it increasing the reliability of VM and providing a great opportunity to access the task mapping.
If a task goes wrong on VM, the capability weight is affected.
C_j (t)=C_j (t)+L*FRF
Where FRF is the failure reliability factor that means it decreasing the VM reliability and facilitates a soft opportunity for task mapping.

Table 1: Cloud Sim Parameters

Table 2: Selected Parameters of the Proposed Hill-Climbing Algorithm

**Figure 1 Standard Deviation with Fault Insertion**

**Figure 2 Standard Deviation with fault insertion**

Based on the above experimental results, the proposed hill-climbing algorithm proves that it considers minimum time to execute the tasks in any case with fault insertion and without fault insertion as well.

Conclusion

The hill-climbing algorithm with load balancing and adaptive virtual machine reliability has been proposed to solve the NP-hard problem of task scheduling in cloud computing resources. Specifically, it determines the available resources for upcoming tasks that included reliability and load. However, the proposed hill-climbing algorithm prefers the virtual machines because they have a good computing capability, high reliability, and a light load in order to execute the tasks for getting more balanced and have better performances. Experimentally, the parameter values are determined and simulation results stated that the proposed hill-climbing algorithm improves resource utilization and provides a high level of performance.

Future Scope

Hill-climbing Algorithm can be used on fog computing (Zahid et al., 2019)
Can be used in optimal deployment of components of cloud-hosted application (Ochei, Petrovski, & Bass, 2019)
Can be used for large scale data in cloud computing (Saleh, Nashaat, Saber, & Harb, 2019)
Can be used in Workflow scheduling in cloud computing (Alsmady, Al-Khraishi, Mardini, Alazzam, & Khamayseh, 2019)
Can be implemented in adaptive fault tolerance for online tasks scheduling in cloud computing (Keshk, Alsini, & Tawfeek, 2018)