ОБЗОР МОДЕЛЕЙ И АЛГОРИТМОВ РАЗМЕЩЕНИЯ ЗАДАНИЙ В СИСТЕМАХ С ПАРАЛЛЕЛЬНЫМ ОБСЛУЖИВАНИЕМ

Представлен обзор зарубежных публикаций по проблеме эффективного распределения заданий в системах обслуживания (проблема диспетчеризации). Отобранные для обзора модели касаются систем с независимыми параллельными безотказными серверами и случайными потоками заданий, не имеющих внутренней структуры. Общая трактовка проблемы сформулирована как задача оптимизации, которая имеет многочисленные варианты в зависимости от дополнительных предположений. Изложение моделей следует классификации этих предположений по объемуихарактеруаприорнойинформации, возможностям наблюдения в процессе функционирования системы и критериям эффективности. Приведено описание основных отмеченных в литературе и используемых на практике алгоритмов диспетчеризации и их сравнительных свойств. Отмечены основные методы, используемые при анализе моделей и построении стратегий размещения заданий. Обзор призван акцентировать внимание на одной из важных и далеких от окончательного разрешения проблем обработки больших объемов информации.

METHODS AND ALGORITHMS FOR JOB SCHEDULING IN SYSTEMS WITH PARALLEL SERVICE: A SURVEY

The review of research papers devoted to the analysis of the dispatching problem in queueing systems is presented. The analysis is restricted to the class of systems with independent, operating in parallel, fully rehable servers, stochastic incoming flows of customers without any preceding constraints. The general goal of the analysis carried out in most of the papers is the solution of an optimization problem, which specification heavily depends on additional assumptions made. The models considered in the review are classified into several classes depending on the amount of a priori information and observability at decision times and performance criteria. The description of the dispatching algorithms most commonly found in literature and their properties is given. The main methods used for the analysis of the systems under these dispatching algorithms are reviewed. This review is intended to draw attention of the research community to one of the important problems in the field of information processing.