Job Scheduling Strategies in Grid Computing

Ardi Pujiyanta, Lukito Edi Nugroho, - Widyawan


Grid computing can be thought of as large-scale distributed cluster computing and distributed parallel network processing. Users can obtain enormous computing power through network technology, which is challenging to get from a single computer. Job scheduling in grid computing is a critical issue that affects the overall grid system capability. In traditional scheduling, jobs are placed in queues, waiting for the availability of resources. Reservations reject if the required resources not obtained at the specified time. The impact that arises is the reduced use of resources. The scheduling algorithm and the parameters used to perform the work may vary, such as execution time, delivery time, and the number of resources. There is no guarantee when the job will execute using the scheduling algorithm. Therefore, it is necessary to improve resource utilization in the grid system and ensure that jobs will be carried out. This paper proposes a reservation scheduling strategy for MPI work, First Come First Serve Left Right Hole (FCFS-LRH). MPI jobs execute simultaneously, using more than one resource for implementation. When Completed, user MPI jobs will be scheduled on virtual compute nodes and mapped to actual compute nodes. The experimental results show that the increase in resource utilization strongly influenced by time flexibility.


Advance reservation; MPI Job; FCFS-LRH; grid systems.

Full Text:



M. Caramia, S. Giordani, and A. Iovanella, “Grid scheduling by on-line rectangle packing,” Networks, vol. 44, no. 2, pp. 106–119, 2004, doi: 10.1002/net.20021.

K. Czajkowski et al., “A resource management architecture for metacomputing systems,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 1459, pp. 62–82, 1998, doi: 10.1007/bfb0053981.

I. Foster, C. Kesselman, C. Lee, B. Lindell, K. Nahrstedt, and A. Roy, “A distributed resource management architecture that supports advance reservations and co-allocation,” IEEE Int. Work. Qual. Serv. IWQoS, no. 1, pp. 27–36, 1999, doi: 10.1109/IWQOS.1999.766475.

A. Sulistio and R. Buyya, “A grid simulation infrastructure supporting advance reservation,” Proc. IASTED Int. Conf. Parallel Distrib. Comput. Syst., vol. 16, pp. 1–7, 2004.

W. Smith, I. Foster, and V. Taylor, “Scheduling with advanced reservations,” pp. 127–132, 2002, doi: 10.1109/ipdps.2000.845974.

J. Shi, J. Luo, F. Dong, J. Zhang, and J. Zhang, “Elastic resource provisioning for scientific workflow scheduling in cloud under budget and deadline constraints,” Cluster Comput., vol. 19, no. 1, pp. 167–182, 2016, doi: 10.1007/s10586-015-0530-0.

A. Sulistio, K. H. Kim, and R. Buyya, “On incorporating an on-line strip packing algorithm into elastic grid reservation-based systems,” Proc. Int. Conf. Parallel Distrib. Syst. - ICPADS, vol. 1, 2007, doi: 10.1109/ICPADS.2007.4447738.

P. Xiao, Z. Hu, X. Li, and L. Yang, “A novel statistic-based relaxed grid resource reservation strategy,” Proc. 9th Int. Conf. Young Comput. Sci. ICYCS 2008, no. 2, pp. 703–707, 2008, doi: 10.1109/ICYCS.2008.117.

P. Xiao and Z. Hu, “Two-dimension relaxed reservation policy for independent tasks in grid computing,” J. Softw., vol. 6, no. 8, pp. 1395–1402, 2011, doi: 10.4304/jsw.6.8.1395-1402.

I. Foster, A. Roy, and V. Sander, “A quality of service architecture that combines resource reservation and application adaptation,” IEEE Int. Work. Qual. Serv. IWQoS, vol. 2000-January, no. June, pp. 181–188, 2000, doi: 10.1109/IWQOS.2000.847954.

C. Hu, “Flexible Resource Capacity Reservation Mechanism for Service Grid Using Slack Time,” J. Comput. Res. Dev., vol. 44, no. 1, p. 20, 2007, doi: 10.1360/crad20070103.

M. Barshan, H. Moens, B. Volckaert, and F. De Turck, “A comparative analysis of flexible and fixed size timeslots for advance bandwidth reservations in media production networks,” 2016 7th Int. Conf. Netw. Futur. NOF 2016, 2017, doi: 10.1109/NOF.2016.7810118.

M. Barshan, H. Moens, J. Famaey, and F. De Turck, “Deadline-aware advance reservation scheduling algorithms for media production networks,” Comput. Commun., vol. 77, no. 2015, pp. 26–40, 2016, doi: 10.1016/j.comcom.2015.10.016.

B. Li, Y. Pei, H. Wu, and B. Shen, “Resource availability-aware advance reservation for parallel jobs with deadlines,” J. Supercomput., vol. 68, no. 2, pp. 798–819, 2014, doi: 10.1007/s11227-013-1067-8.

C. Castillo, G. N. Rouskas, and K. Harfoush, “Online algorithms for advance resource reservations,” J. Parallel Distrib. Comput., vol. 71, no. 7, pp. 963–973, 2011, doi: 10.1016/j.jpdc.2011.01.003.

F. Camillo, E. Caron, R. Guivarch, A. Hurault, C. Klein, and C. Pérez, “Resource management architecture for fair scheduling of optional computations,” Proc. - 2013 8th Int. Conf. P2P, Parallel, Grid, Cloud Internet Comput. 3PGCIC 2013, pp. 113–120, 2013, doi: 10.1109/3PGCIC.2013.23.

E. Gomes and M. A. R. Dantas, “Towards a resource reservation approach for an opportunistic computing environment,” J. Phys. Conf. Ser., vol. 540, no. 1, 2014, doi: 10.1088/1742-6596/540/1/012002.

R. Umar, A. Agarwal, and C. R. Rao, “Advance Planning and Reservation in a Grid System,” Commun. Comput. Inf. Sci., vol. 293 PART 1, pp. 161–173, 2012, doi: 10.1007/978-3-642-30507-8_15.

L. Grandinetti, F. Guerriero, L. Di Puglia Pugliese, and M. Sheikhalishahi, “Heuristics for the local grid scheduling problem with processing time constraints,” J. Heuristics, vol. 21, no. 4, pp. 523–547, 2015, doi: 10.1007/s10732-015-9287-0.

A. Mishra, “An enhanced and effective preemption based scheduling for grid computing enabling backfilling technique,” Conf. Proceeding - 2015 Int. Conf. Adv. Comput. Eng. Appl. ICACEA 2015, pp. 1015–1018, 2015, doi: 10.1109/ICACEA.2015.7164855.

R. Istrate, A. Poenaru, and F. Pop, “Advance reservation system for datacenters,” Proc. - Int. Conf. Adv. Inf. Netw. Appl. AINA, vol. 2016-May, pp. 637–644, 2016, doi: 10.1109/AINA.2016.106.

A. Sulistio et al., “An Adaptive Scoring Job Scheduling algorithm for grid computing,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 5, no. 1, pp. 68–72, 2015, doi: 10.1177/1094342006068414.

O. Dakkak, S. Awang Nor, and S. Arif, “Scheduling through backfilling technique for HPC applications in grid computing environment,” ICOS 2016 - 2016 IEEE Conf. Open Syst., pp. 30–35, 2017, doi: 10.1109/ICOS.2016.7881984.

S. Leonenkov and S. Zhumatiy, “Introducing New Backfill-based Scheduler for SLURM Resource Manager,” Procedia Comput. Sci., vol. 66, pp. 661–669, 2015, doi: 10.1016/j.procs.2015.11.075.

A. Shukla, S. Kumar, and H. Singh, “An improved resource allocation model for grid computing environment,” Int. J. Intell. Eng. Syst., vol. 12, no. 1, pp. 104–113, 2019, doi: 10.22266/IJIES2019.0228.11.

A. Pujiyanta, L. E. Nugroho, and Widyawan, “Planning and Scheduling Jobs on Grid Computing,” Proceeding - 2018 Int. Symp. Adv. Intell. Informatics Revolutionize Intell. Informatics Spectr. Humanit. SAIN 2018, pp. 162–166, 2019, doi:

M. Carvalho and F. Brasileiro, “A user-based model of grid computing workloads,” in 2012 ACM/IEEE 13th International Conference on Grid Computing, 2012, pp. 40–48, doi: 10.1109/Grid.2012.13.

A. Hirales-Carbajal, J.-L. González-García, and A. Tchernykh, “Workload Generation for Trace Based Grid Simulations,” in Procedding of the Ist international supercomputer conference in Mexico ISUM., 2010, pp. 1–9.

A. Iosup, D. H. J. Epema, J. Maassen, and R. Van Nieuwpoort, “Synthetic grid workloads with Ibis, KOALA, and GRENCHMARK,” in Integrated Research in GRID Computing - CoreGRID Integration Workshop 2005, Selected Papers, 2007, pp. 271–283, doi: 10.1007/978-0-387-47658-2_20.

B. Barzegar, A. M. Rahmani, K. Zamanifar, and A. Divsalar, “Gravitational emulation local search algorithm for advanced reservation and scheduling in grid computing systems,” ICCIT 2009 - 4th Int. Conf. Comput. Sci. Converg. Inf. Technol., pp. 1240–1245, 2009, doi: 10.1109/ICCIT.2009.319.



  • There are currently no refbacks.

Published by INSIGHT - Indonesian Society for Knowledge and Human Development