Abstract Volunteer grid is a kind of distributed networks, consisting of contributed resources which are heterogonous and distributed. The heterogeneity of resources can be in terms of the time of availability, resource characteristics among others. Usually submitted jobs to volunteer grid usually require different heterogeneous resources depending on their requirements. Efficient scheduling of submitted jobs can be done if jobs are divided into small number of tasks to fulfil multiple requirements, which requires multi-resource scheduling policy to consider different constraints of resource and job before scheduling. In traditional scheduling policies only single scheduling or optimization constraint is considered to either complete job within specific deadline or to maximize the resource usage. Therefore, a scheduling policy is required to serve multiple constraints for optimizing resource usage and completing jobs within specified deadlines. The work presented in this paper proposed Quality of Service (QoS) based multi-constraint job scheduling heuristics for volunteer grid resources. Bin packing problem is also incorporated within the proposed heuristic for reordering and jobs assignment. The performance of proposed scheduling heuristic is measured by comparing it with other scheduling algorithms used in grid environment. The results presented suggest that there is a reasonable improvement in waiting time, turnaround time, slowdown time and job failure rate.

References

[1] Chen W., Fekete K., and Lee Y., “Exploiting Deadline Flexibility in Grid Workflow Rescheduling,” in Proceedings of 11th IEEE/ACM International Conference on Grid Computing, Brussels, pp. 105-112, 2010.

[2] Coffman J., Garey M., and Johnson D., “Dynamic Bin Packing,” SIAM Journal on Computing, vol. 12, no. 2, pp. 227-258, 1983.

[3] Coffman J., Garey M., and Johnson D., “Approximation Algorithms for Bin Packing: A Survey,” Approximation Algorithms for NP-Hard Problems, pp. 46-93, 1996.

[4] Ding D., Luo S., and Gao Z., “A Matrix Scheduling Strategy With Multi-Qos Constraints In Computational Grid,” in Proceedings of International Conference on Grid and Pervasive Computing, Berlin, pp. 59-68, 2010.

[5] Guitart J., Macías M., Rana O., Wieder P., Yahyapour R., and Ziegler W., “SLA-Based Resource Management and Allocation,” Market- Oriented Grid and Utility Computing, vol. 75, pp. 261-284, 2009.

[6] He X., Sun X., and Von Laszewski G., “Qos Guided Min-Min Heuristic for Grid Task Scheduling,” Journal of Computer Science and Technology, vol. 18, no. 4, pp. 442-451, 2003.

[7] Hongbing L., Linping W., and Wei W., “A Multi-Constraint Preemption Algorithm for Parallel Job Scheduling,” in Proceedings of 12th International Conference on Parallel and Distributed Computing, Applications and Technologies, Gwangju, pp. 73-78, 2011.

[8] Ioannidou M. and Karatza H., “Multi-Site Scheduling with Multiple Job Reservations and Forecasting Methods,” in Proceedings of International Symposium on Parallel and 0 5 10 15 20 25 30 FCFSSPNLJFRRProposed number of jobs failed QoS Based Multi-Constraints Bin Packing Job Scheduling Heuristic for ... 667 Distributed Processing And Applications, Berlin, pp. 894-903, 2006.

[9] Kakarontzas G. and Savvas I., “Agent-Based Resource Discovery and Selection for Dynamic Grids,” in Proceedings of 15th IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, Manchester, pp. 195-200, 2006.

[10] Khanli L. and Analoui M., “Grid_JQA: A QoS Guided Scheduling Algorithm for Grid Computing,” in Proceedings of 6th International Symposium on Parallel and Distributed Computing, Hagenberg, pp. 34-34, 2007.

[11] Leinberger W., Karypis G., and Kumar V., “Job Scheduling in The Presence of Multiple Resource Requirements,” in Proceedings of the ACM/IEEE Conference on Supercomputing, Portland, pp. 47, 1999.

[12] Leinberger W., Karypis G., and Kumar V., “Multi-Capacity Bin Packing Algorithms with Applications to Job Scheduling Under Multiple Constraints,” in Proceedings of the International Conference on Parallel Processing, Aizu- Wakamatsu City, pp. 404-412, 1999.

[13] Li H. and Buyya R., “Model-Driven Simulation Of Grid Scheduling Strategies,” in Proceedings of 3rd IEEE International Conference on e- Science and Grid Computing, Bangalore, pp. 287-294, 2007.

[14] Milenkovič M., Operating Systems: Concepts and Design, McGraw-Hill, 1987.

[15] Nouman M. and Shamsi J., “Volunteer Computing: Requirements, Challenges, and Solutions,” Journal of Network and Computer Applications, vol. 39, pp. 369-380, 2014.

[16] Panigrahy R., Talwar K., Uyeda L., and Wieder U., “Heuristics for Vector Bin Packing,” in Proceedings of Research. Microsoft, 2011.

[17] Parsons E. and Sevcik K., “Coordinated Allocation of Memory and Processors in Multiprocessors,” in Proceedings of ACM SIGMETRICS Performance Evaluation Review, Philadelphia, pp. 57-67, 1996.

[18] Rubab S., Hassan M., Mahmood A., and Shah N., “Bin Packing Multi-Constraints Job Scheduling Heuristic for Heterogeneous Volunteer Grid Resources,” in Proceedings of 4th International Conference on Computer Science and Computational Mathematics, Langkawi, pp. 644- 649, 2015.

[19] Rubab S., Hassan M., Mahmood A., and Shah N., “Job Scheduling Approach Based on Quality of Service Classification in Volunteer Grid Environment,” in Proceedings of 4th International Conference on Computer Science and Computational Mathematics, pp. 520-524, 2015.

[20] Srinivasan S., Kettimuthu R., Subramani V., and Sadayappan P., “Selective Reservation Strategies For Backfill Job Scheduling,” in Proceedings of Workshop on Job Scheduling Strategies for Parallel Processing, Berlin, pp. 55-71, 2002.

[21] Stallings W., Operating Systems, Prentice Hall, 1995.

[22] Stillwell M., Schanzenbach D., Vivien F., and Casanova H., “Resource Allocation Algorithms for Virtualized Service Hosting Platforms,” Journal of Parallel and Distributed Computing, vol. 70, no. 9, pp. 962-974, 2010.

[23] Tawfeek M., El-Sisi A., Keshk A., and Torkey F., “Cloud Task Scheduling Based on Ant Colony Optimization,” The International Arab Journal of Information Technology, vol. 12, no. 2, pp. 129-137, 2015.

[24] Tomás L., Caminero A., Caminero B., and Carrión C., “Using Network Information to Perform Meta-Scheduling in Advance in Grids,” in Proceedings of European Conference on Parallel Processing, Berlin, pp. 431-443, 2010.

[25] Wang C., Chen H., Hsu C., and Lee J., “Dynamic Resource Selection Heuristics for A Non- Reserved Bidding-Based Grid Environment,” Future Generation Computer Systems, vol. 26, no. 2, pp. 183-197, 2010.

[26] Watanabe K., Fukushi M., and Kameyama M., “Adaptive Group-Based Job Scheduling for High Performance and Reliable Volunteer Computing,” Journal of Information Processing, vol. 19, pp. 39-51, 2011.

[27] Xhafa F. and Abraham A., “Computational Models and Heuristic Methods for Grid Scheduling Problems,” Future Generation Computer Systems, vol. 26, no. 4, pp. 608-621, 2010. 668 The International Arab Journal of Information Technology, Vol. 16, No. 4, July 2019 Saddaf Rubab is a Ph.D. student at Universiti Teknologi PETRONAS, Malaysia. In the context of her PhD studies, she is working on high- performance, reliable and fault tolerant grid systems. Apart from this, her research interests concern resource management issues in distributed computing infrastructure. Mohd Fadzil Hassan obtained his PhD in Informatics in 2007 from the University of Edinburgh, UK. He is currently the Dean, Centre for Graduate Studies, Universiti Teknologi PETRONAS (UTP), Malaysia. His research interests are in the area of Artificial Intelligence, Multi-Agent Systems and Service Oriented Architecture (SOA). Ahmad Mahmood earned his PhD in Information Systems in 2005 from the University of Salford, UK. He is currently the Dean of Faculty of Science and IT. With his research team, a number of journal articles and conference papers have been published. Nasir Mehmood earned his PhD in Information Technology in 2012 from Universiti Teknologi PETRONAS, Malaysia. He is serving as Head Department of Computer Science and Associate Professor at Dr. A. Q. Khan Institute of Computer Sciences and Information Technology (KICSIT), Kahuta, Pakistan.