Standard

Задача минимизации максимального временного смещения для параллельных процессоров. / Григорьева, Н.С.

In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 10: ПРИКЛАДНАЯ МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ, Vol. 12, No. 4, 2016, p. 51-65.

Research output: Contribution to journalArticlepeer-review

Harvard

Григорьева, НС 2016, 'Задача минимизации максимального временного смещения для параллельных процессоров', ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 10: ПРИКЛАДНАЯ МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ, vol. 12, no. 4, pp. 51-65.

APA

Григорьева, Н. С. (2016). Задача минимизации максимального временного смещения для параллельных процессоров. ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 10: ПРИКЛАДНАЯ МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ, 12(4), 51-65.

Vancouver

Григорьева НС. Задача минимизации максимального временного смещения для параллельных процессоров. ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 10: ПРИКЛАДНАЯ МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ. 2016;12(4):51-65.

Author

Григорьева, Н.С. / Задача минимизации максимального временного смещения для параллельных процессоров. In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 10: ПРИКЛАДНАЯ МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ. 2016 ; Vol. 12, No. 4. pp. 51-65.

BibTeX

@article{2eb9d082dc5142a0b32ea2e74088d36d,
title = "Задача минимизации максимального временного смещения для параллельных процессоров",
abstract = "Задачa минимизации максимального временного смещения для составления расписаний для параллельных идентичных процессоров — классическая комбинаторная оптимизационная задача, имеет много приложений и является NP-трудной. Эта задача составления расписаний обозначается как P|rj |Lmax и формулируется следующим образом: задания должны быть выполнены на нескольких параллельных идентичных процессорах; требуется определить, где и когда каждое задание должно быть выполнено так, чтобы минимизировать максимальное смещение. Для каждого задания известны время поступления задания на выполнение, время выполнения и директивный срок, к которому задание должно быть закончено. Прерывания выполнения заданий не допускаются. Большинство разработок приближенных алгоритмов концентрируется на построении незадерживающих расписаний, в которых процессор не может простаивать, если есть готовое к выполнению задание. Но для построения оптимального расписания необходимо рассматривать такие допустимые расписания, в которых невынужденный простой процессора возможен. Цель данной статьи — представить приближенный алгоритм с невынужденными простоями ELS/IIT (в котором наибольшим приоритетом обладает задание с минимальным поздним началом) и метод ветвей и границ, который строит допустимое расписание с заданным значением максимального смещения. Для нахождения оптимального решения предлагается комбинировать метод ветвей и границ с бинарным поиском. Библиогр. 14 назв. Табл. 5.",
keywords = "параллельные процессоры, метод ветвей и границ, максимальное временное смещение, parallel identical processors, Branch and bound algorithm, maximum lateness",
author = "Н.С. Григорьева",
year = "2016",
language = "русский",
volume = "12",
pages = "51--65",
journal = " ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ",
issn = "1811-9905",
publisher = "Издательство Санкт-Петербургского университета",
number = "4",

}

RIS

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 -

ID: 9290878