Analysis of delays in scheduling homogeneous tasks under uncertainty

Yu. E. Malashenko, I. A. Nazarova

Dorodnicyn Computing Center, Russian Academy of Sciences, 40 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The problem of management of the computationally resource-intensive tasks of search type allowing parallelization by the data is considered. Tasks arrive in a system at any time one by one or in groups; their service time is not known in advance. For processing planning, the optimization model is used which is based on current information on tasks performance: the sojourn time and the amount of data already processed. Using the model for each task, the portion of data to be processed in the plan period is determined. In calculations, required computational expenses are estimated and assumptions about the distribution laws of unknown tasks characteristics are not made. The proposed scheduling rule allows to form the order of task execution in dynamics, priority being given to “less intensive” tasks.

Keywords: computationally intensive tasks; parallel computing; scheduling optimization; principle of guaranteed result.

Received: 08.11.2013

DOI: 10.14375/19922264140102

Bibliographic databases:

•