Level based batch scheduling strategy with idle slot reduction under DAG constraints for computational grid

• An idle slot reduction based levelized batch scheduling strategy.
• Batch is partitioned into groups as per the depth levels and allocated level wise.
• Reduces idle slots generated by inserting the best fitting succeeding modules.
• Reduces the effect of the communication cost on turnaround time.
• Significantly better performance for all the cases under study.

Scheduling in a grid environment optimizing the given objective parameters has been proven to be NP-complete. This work proposes a Level based Batch scheduling Strategy with Idle slot Reduction (LBSIR) while considering the inter module communication within the modules of the jobs represented using Direct Acyclic Graph (DAG) with the objective of optimizing the turnaround time and response time for a computational grid. The model works in two phases, allocation phase and idle slot reduction phase. Allocation phase begins by dividing the batch into a number of partitions as per the precedence level/depth level followed by the assignment of sub-jobs/modules from the partition to the best fit node in terms of the execution time offered for all the partitions. The idle slots generated during the allocation phase in each depth level are then reduced by inserting the best fit modules into these slots in the idle slot reduction phase after allocation of modules from higher depth level. Levelized allocation ensures minimizing the average response time being very useful for user interactive applications. An experimental study of the proposed strategy has been performed by comparing it with other similar methods having common objectives for evaluating its place in the middleware.