An Effective Cloud Workflow Scheduling Approach Combining PSO and Idle Time Slot-Aware Rules

Workflow scheduling is a key issue and remains a challenging problem in cloud computing.Faced with the large number of virtual machine(VM)types offered by cloud providers,cloud users need to choose the most appropriate VM type for each task.Multiple task scheduling sequences exist in a workflow application.Different task scheduling sequences have a significant impact on the scheduling performance.It is not easy to determine the most appropriate set of VM types for tasks and the best task scheduling sequence.Besides,the idle time slots on VM instances should be used fully to increase resources'utilization and save the execution cost of a workflow.This paper considers these three aspects simultaneously and proposes a cloud workflow scheduling approach which combines particle swarm optimization(PSO)and idle time slot-aware rules,to minimize the execution cost of a workflow application under a deadline constraint.A new particle encoding is devised to represent the VM type required by each task and the scheduling sequence of tasks.An idle time slot-aware decoding procedure is proposed to decode a particle into a scheduling solution.To handle tasks'invalid priorities caused by the randomness of PSO,a repair method is used to repair those priorities to produce valid task scheduling sequences.The proposed approach is compared with state-of-the-art cloud workflow scheduling algorithms.Experiments show that the proposed approach outperforms the comparative algorithms in terms of both of the execution cost and the success rate in meeting the deadline.

MERGING OPTIMALITY CONDITIONS WITH GENETIC ALGORITHM OPERATORS TO SOLVE SINGLE MACHINE TOTAL WEIGHTED TARDINESS PROBLEM

In this paper, a constrained genetic algorithm (CGA) is proposed to solve the single machine total weighted tardiness problem. The proposed CGA incorporates dominance rules for the problem under consideration into the GA operators. This incorporation should enable the proposed CGA to obtain close to optimal solutions with much less deviation and much less computational effort than the conventional GA (UGA). Several experiments were performed to compare the quality of solutions obtained by the three versions of both the CGA and the UGA with the results obtained by a dynamic programming approach. The computational results showed that the CGA was better than the UGA in both quality of solutions obtained and the CPU time needed to obtain the close to optimal solutions. The three versions of the CGA reduced the percentage deviation by 15.6%, 61.95%, and 25% respectively and obtained close to optimal solutions with 59% lower CPU time than what the three versions of the UGA demanded. The CGA performed better than the UGA in terms of quality of solutions and computational effort when the population size and the number of generations are smaller.