Resource Co-allocation Algorithms for Job Batch Scheduling in Dependable Distributed Computing

P. 243–256.

Toporkov V. V., Toporkova A. S., Yemelyanov D. M., Bobchenkov A. V.

This work presents slot selection algorithms in economic models for independent job batch scheduling in distributed computing with non-dedicated resources. Existing approaches towards resource co-allocation and multiprocessor job scheduling in economic models of distributed computing are based on search of time-slots in resource occupancy schedules. The sought time-slots must match requirements of necessary span, computational resource properties, and cost. Usually such scheduling methods consider only suited variant of time-slot set. This work discloses a scheduling scheme that features multi-variant search. Two algorithms of linear complexity for search of alternative variants are proposed and compared. Having several optional resource configurations for each job makes an opportunity to perform an optimization of execution of the whole batch of jobs and to increase overall efficiency of scheduling.

Keywords: планирование, распределенные вычисления, задание, неотчуждаемость ресурсов, метапланировщик, виртуальные организации, экономические принципы, distributed computing, scheduling, job, non-dedicated recourses, metasheduler, virtual organizations, economic principles

In book

Dependable Computer Systems

Vol. 97. , Berlin, Heidelberg: Springer, 2011.