SA-Based QoS Aware Workflow Scheduling of Collaborative Tasks in Grid Computing
DOI:
https://doi.org/10.47839/ijc.23.1.3436Keywords:
grid computing, workflow tasks scheduling, simulated annealing algorithm, quality of service constraintsAbstract
Scheduling workflow tasks in grid computing is a complex process, especially if it is associated with satisfying the user's requirements to complete tasks within a specified time, with lowest possible cost. This paper presents a proposed Simulated Annealing (SA) based Grid Workflow Tasks Scheduling Approach (SA-GWTSA) that takes into account users’ QoS (quality of service) constraints in terms of cost and time. For a given set of inter-dependent workflow tasks, it generates an optimal schedule, which minimizes the execution time and cost, such that the optimized time is within the time constraints (deadline) imposed by the user. In SA-GWTSA, the workflow tasks, which are modeled as a DAG, are divided into task divisions, each of which consists of a set of sequential tasks. Then, the optimal sub-schedules of all task divisions are computed applying SA algorithm, and used to obtain the execution schedule of the entire workflow. In the proposed algorithm, the sub-schedule of each branch division is represented by a vector, in which each element holds the ID of the service provider chosen from a list of service providers capable of executing the corresponding task in the branch. The algorithm uses a fitness function that is formulated as a multi-objective function of time and cost, which gives users the ability to determine their requirements of time against cost, by changing the weighting coefficients in the objective function. The paper also exhibits the experimental results of assessing the performance of SA-GWTSA with workflows samples of different sizes, compared to different scheduling algorithms: Greedy-Time, Greedy-Cost, and Modified Greedy-Cost.
References
N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller, “Equation of state calculations by fast computing machines,” Journal of Chemical Physics, vol. 21, issue 6, pp. 1087–1092, 1953.
M. Aggarwal, R. D. Kent and A. Ngom, “Genetic algorithm based scheduler for computational grids,” Proceedings of the 19th International Symposium on High Performance Computing Systems and Applications (HPCS’05), Guelph, ON, Canada, 15-18 May 2005, pp. 209-215.
J. Yu and R. Buyya, “A budget constrained scheduling of workflow applications on utility grids using genetic algorithms,” Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing (HPDC’06), Paris, France, 19-23 June 2006, pp. 1-10.
J. Yu and R. Buyya, “Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms,” Scientific Programming, vol. 14, pp. 217–230, 2006.
L. Zhang, Y. Chen, R. Sun, S. Jing and B. Yang, “A task scheduling algorithm based on PSO for grid computing,” International Journal of Computational Intelligence Research, vol. 4, issue 1, pp. 37–43, 2008.
R. Chen, D. Shiau, S. H. Andlo, “Combined discrete particle swarm optimization and simulated annealing for grid computing scheduling problem,” Lecture Notes in Computer Science, vol. 57, Springer, Berlin, pp. 242–251, 2009.
A. Kant, A. Sharma, S. Agarwal, and S. Chandra, “An ACO approach to job scheduling in grid environment,” In: B. K. Panigrahi, S. Das, P. N. Suganthan and S. S. Dash (eds), Swarm, Evolutionary, and Memetic Computing, SEMCCO 2010, Lecture Notes in Computer Science, vol. 6466, Springer, Berlin, Heidelberg, 2010.
Y. Jiang, M. Chen, “Task scheduling for grid computing systems using a genetic algorithm,” The Journal of Supercomputing, vol. 71, issue 4, pp. 1357–1377, 2015.
L. Bouali, K. Oukfif, S. Bouzefrane, F. B. Oulebsir, “A hybrid algorithm for DAG application scheduling on computational grids,” International Conference on Mobile, Secure and Programmable Networking (MSPN’2015), Paris, France, June 2015, pp. 63-77.
E. Gabaldon, F. Guirado, J. L. Lerida, J. Planes, “Particle swarm optimization scheduling for energy saving in cluster computing heterogeneous environments,” Proceedings of the 2016 IEEE 4th International Conference on Future Internet of Things and Cloud Workshops (FiCloudW), Vienna, Austria, August 2016, pp. 321–325.
E. Gabaldon, S. Vila, F. Guirado, J. L. Lerida, J. Planes, “Energy efficient scheduling on heterogeneous federated clusters using a fuzzy multi-objective meta-heuristics,” Proceedings of the IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), Naples, Italy, 2017, pp. 1-6.
M. T. Younis, S. Yang, “Hybrid meta-heuristic algorithms for independent job scheduling in grid computing,” Applied Soft Computing, vol. 72, pp. 498-517, 2018.
T. K. Ghosh, S. Das, N. Ghoshal, “Job scheduling in computational grid using a hybrid algorithm based on genetic algorithm and particle swarm optimization,” O. Castillo, D. Jana, D. Giri, A. Ahmed (eds), Recent Advances in Intelligent Information Systems and Applied Mathematics, ICITAM, Studies in Computational Intelligence, vol. 863, Springer, 2019.
A. Chhabra, G. Singh, and K. S. Kahlon, “Performance‑aware energy‑efficient parallel job scheduling in HPC grid using nature‑inspired hybrid meta‑heuristics,” Journal of Ambient Intelligence and Humanized Computing, vol. 12, pp. 1801–1835, 2021.
W. Abdulal, O. A. Jadaan, A. Jabas, and S. Ramachandram, “Mutation based simulated annealing algorithm for minimizing makespan in grid computing systems,” Proceedings of the IEEE International Conference on Network and Computer Science (ICNCS’2011), Kanyakumari, India, April 2011, pp. V6-90-V6-94.
J. Yu, R. Buyya and C. K. Tham, “QoS-based scheduling of workflow applications on service grids,” Proceedings of the 1st IEEE International Conference on e-Science and Grid Computing (e-Science’05), Melbourne, Australia, December 2005, pp. 1-8.
S. H. Benedict and V. Vasudevan, “Improving scheduling of scientific workflows using tabu search for computational grids,” Information Technology Journal, vol. 7, issue 1, pp. 91–97, 2008.
M. Meddeber and B. Yagoubi, “Tasks assignment for Grid computing,” International Journal of Web and Grid Services, Inderscience Enterprises Ltd., pp. 427-443, 2011.
N. A. Bahnasawy, M. A. Koutb, M. Mosa and F. Omara, “A new algorithm for static task scheduling for heterogeneous distributed computing systems,” African Journal of Mathematics and Computer Science Research, vol. 4, issue 6, pp. 221-234, 2011.
A. M Bidgoli and Z. M. Nezad, “A new scheduling algorithm design for grid computing tasks,” Proceedings of the 5th Symposium on Advances in Science and Technology, Khavaran Higher-education Institute, Mashhad, Iran, 2011, pp. 12-14.
R. Goel, D. Singh, and Minakshi, “Scheduling algorithm design for grid computing,” International Journal of Innovations in Engineering and Technology (IJIET), vol. 3, issue 1, October 2013.
H. S. Hossam, H. Abdel-Galil, and M. Belal, “WorkStealing algorithm for load balancing in grid computing,” International Journal of Advanced Computer Science and Applications, vol. 12, issue 7, pp. 98-104, 2021.
M. Rahman, R. Hassan, R. Ranjan, and R. Buyya, “Adaptive workflow scheduling for dynamic grid and cloud computing environment,” Concurrency and Computation: Practice and Experience, vol. 25, pp. 1816–1842, 2013.
P. Chauhan and Nitin, “Decentralized scheduling algorithm for DAG based tasks on P2P grid,” Hindawi Publishing Corporation Journal of Engineering, vol. 2014, Article ID 202843, pp. 1-14, 2014.
R. Garg and A. K. Singh, “Adaptive workflow scheduling in grid computing based on dynamic resource availability,” Engineering Science and Technology, an International Journal, vol. 18, pp. 256-269, 2015.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
