TY - JOUR

T1 - Задача минимизации максимального временного смещения для параллельных процессоров

AU - Григорьева, Н.С.

PY - 2016

Y1 - 2016

N2 - Задачa минимизации максимального временного смещения для составления расписаний для параллельных идентичных процессоров — классическая комбинаторная оптимизационная задача, имеет много приложений и является NP-трудной. Эта задача составления расписаний обозначается как P|rj |Lmax и формулируется следующим образом: задания должны быть выполнены на нескольких параллельных идентичных процессорах; требуется определить, где и когда каждое задание должно быть выполнено так, чтобы минимизировать максимальное смещение. Для каждого задания известны время поступления задания на выполнение, время выполнения и директивный срок, к которому задание должно быть закончено. Прерывания выполнения заданий не допускаются. Большинство разработок приближенных алгоритмов концентрируется на построении незадерживающих расписаний, в которых процессор не может простаивать, если есть готовое к выполнению задание. Но для построения оптимального расписания необходимо рассматривать такие допустимые расписания, в которых невынужденный простой процессора возможен. Цель данной статьи — представить приближенный алгоритм с невынужденными простоями ELS/IIT (в котором наибольшим приоритетом обладает задание с минимальным поздним началом) и метод ветвей и границ, который строит допустимое расписание с заданным значением максимального смещения. Для нахождения оптимального решения предлагается комбинировать метод ветвей и границ с бинарным поиском. Библиогр. 14 назв. Табл. 5.

AB - Задачa минимизации максимального временного смещения для составления расписаний для параллельных идентичных процессоров — классическая комбинаторная оптимизационная задача, имеет много приложений и является NP-трудной. Эта задача составления расписаний обозначается как P|rj |Lmax и формулируется следующим образом: задания должны быть выполнены на нескольких параллельных идентичных процессорах; требуется определить, где и когда каждое задание должно быть выполнено так, чтобы минимизировать максимальное смещение. Для каждого задания известны время поступления задания на выполнение, время выполнения и директивный срок, к которому задание должно быть закончено. Прерывания выполнения заданий не допускаются. Большинство разработок приближенных алгоритмов концентрируется на построении незадерживающих расписаний, в которых процессор не может простаивать, если есть готовое к выполнению задание. Но для построения оптимального расписания необходимо рассматривать такие допустимые расписания, в которых невынужденный простой процессора возможен. Цель данной статьи — представить приближенный алгоритм с невынужденными простоями ELS/IIT (в котором наибольшим приоритетом обладает задание с минимальным поздним началом) и метод ветвей и границ, который строит допустимое расписание с заданным значением максимального смещения. Для нахождения оптимального решения предлагается комбинировать метод ветвей и границ с бинарным поиском. Библиогр. 14 назв. Табл. 5.

KW - параллельные процессоры

KW - метод ветвей и границ

KW - максимальное временное смещение

KW - parallel identical processors

KW - Branch and bound algorithm

KW - maximum lateness

UR - http://vestnik.spbu.ru/html16/s10/s10v4/05.pdf

M3 - статья

VL - 12

SP - 51

EP - 65

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

SN - 1811-9905

IS - 4

ER -