Ranking and Cyclic Job Scheduling in QoS-Guaranteed Grids

Toporkov Victor; Toporkova Anna; Tselishchev Alexey; Yemelyanov Dmitry; Potekhin Petr

doi:10.1007/978-3-319-19216-1_48

Publications

Book chapter

Ranking and Cyclic Job Scheduling in QoS-Guaranteed Grids

P. 505-514.

Toporkov V., Toporkova Anna, Tselishchev A., Yemelyanov D., Potekhin P.

In this work, we describe approaches to creation of a ranked jobs framework within the model of cycle scheduling in Grid virtual organizations with such quality of service (QoS) indicators as an average job execution time and a number of required scheduling cycles. Two methods for job selection and scheduling are proposed and compared: the first one is based on the knapsack problem solution, while the second one introduces a heuristic parameter of job and computational resources “compatibility”. Along with these methods we present experimental results demonstrating the efficiency of proposed approaches and compare them with random job selection.

Language: English

Full text (PDF, 6.09 Mb)

DOI

Text on another site

Keywords: Grid virtual organizations scheduling resource management job flow batch knapsack problem quality of service

In book

Ranking and Cyclic Job Scheduling in QoS-Guaranteed Grids

Theory and Engineering of Complex Systems and Dependability Proceedings of the Tenth International Conference on Dependability and Complex Systems DepCoS-RELCOMEX, June 29 – July 3 2015, Brunów, Poland

Edited by: W. Zamojski, J. Mazurkiewicz, J. Sugier et al. Vol. 365: Advances in Intelligent Systems and Computing . Cham; Heidelberg; NY; Dordrecht; L.: Springer, 2015.

Monographs of System Dependability. Dependability of Networks

Vol. 2. Wrocław: Oficyna Wydawnicza Politechnki Wroclawskiej, 2010.

This chapter describes an economic model for independent job flow management in distributed computing environments with non-dedicated resources. The model is based on the concept of fair resource distribution between users and owners of computational nodes by means of economic mechanisms in a virtual organization. Scheduling is performed in cycles in accordance with dynamically updated schedules on local processor nodes. Schedule optimization is performed using dynamic programming methods using the set of criteria in accordance with the economic policy of the virtual organization.

Added: Apr 20, 2012

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

Toporkov V. V., Toporkova A. S., Yemelyanov D. M. et al. In bk.: Dependable Computer Systems. Vol. 97. Berlin; Heidelberg: Springer, 2011. P. 243-256.

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.

Added: Apr 20, 2012

Междисциплинарное значение науки и практики логистики и управления цепями поставок в исследованиях сетевых форм организации

Стерлигова А. Н. Прикладная логистика. 2011. № 9. С. 3-10.

Added: Feb 21, 2013

A general approximation approach for multi-machine scheduling problems with minimizing the maximum penalty

Lazarev A. A., Lemtuzhnikova D., Werner F. Otto-von-Guericke Universitaet, 2019

We consider NP-hard multi{machine scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness. For such problems, we introduce a metric which delivers an upper bound on the absolute error of the objective function value. Taking the given in- stance of some problem and using the introduced metric, we determine the nearest instance for which a polynomial or pseudo-polynomial algorithm is known. For this determined instance, we construct a schedule which is then applied to the original instance. It is shown how this approach is applied to di_erent scheduling problems.

Added: Apr 26, 2020

Finding the Pareto Set for a Bi-criteria Scheduling Problem on a Single Machine with Equal Processing Times

Lazarev A. A., Arkhipov D. I., Werner F. Otto-von-Guericke University Magdeburg, Germany. Institut fur Mathematische Optimierung, 2015. No. 11.

The following special case of the classical NP-hard scheduling problem 1jrj jLmax is considered. There is a set of jobs N = f1; 2; : : : ; ng with identical processing times pj = p for all jobs j 2 N. All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness Lmax. We analyze algorithms for the makespan problem 1jrj jCmax, presented by Garey et al. (1981) and Simons (1978) and give two polynomial algorithms to solve the problem under consideration and to construct the Pareto set with respect to the criteria Lmax and Cmax. The complexity of the presented algorithms is O(Q _ n log n) and O(n2 log n), respectively, where 10􀀀Q is the accuracy of the input-output parameters.

Added: Apr 10, 2015

Программы СКИФ как пример современного управления интеллектуальной собственностью союзного государства

Бек Н. Н., Никитин Л. Л. Экономика и управление собственностью. 2010. № 2. С. 53-56.

A successful realization of the Russia and Belarus Union State’s project SKIF made a strong impulse to supercomputing in both countries. The scale of positive externalities to a large degree was made of the selected open model of intellectual property management. This made supercomputing available not only to the large corporations and state R&D bodies, but to the small and medium business as well. This resulted in the rise of innovation implementation and their contribution to modernization of Russian and Belarusian economies on the whole.

Added: Oct 14, 2012

Wage Differentials and State Private Sector Employment Choice in the Federal Republic of Yugoslavia

Jovanovic B., Lokshin M. Policy Research Working Paper. WPS. World Bank Group, 2003. No. 2959.

The authors use the newly available Yugoslavian Labor Force Survey data to investigate wage differentials and employment decisions in the state and private sectors in Yugoslavia. For the analysis the authors use three empirical models that rely on different statistical assumptions. They extend the standard switching regression model to allow non-normality in the joint distribution of the error terms. After correcting for the sector selection bias and controlling for workers' characteristics the authors find a private sector wage advantage. The wage premium is largest for workers with low education levels and declining for workers with higher educational levels. Given the regulatory and tax policies that pushed the private sector into the informal sphere of the economy during the period covered by our data, the authors argue that the state-private wage gap is likely to grow in the future. This will make it increasingly difficult for the state sector to attract and retain highly skilled employees.

Added: Nov 14, 2012

Методика измерения удовлетворенности клиентов в российских компаниях сферы услуг

Носикова О. О. Практический маркетинг. 2010. № 6. С. 18-23.

In this article comparative analysis of two methodologies of client satisfaction evaluation - CSI and NPS - is given. Based on this analysis it is proved that in case of tuning of NPS up to Russian specifics it better fits authors criteria for services industry. Necessity for testing of western NPS methodology before its mass use in practice of companies on Russian market is justified. Main results of adaptation of present methodology in Russia (with example of insurance industry) are given.

Added: Oct 11, 2012