RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр., 2016, выпуск 4, страницы 51–65 (Mi vspui310)  

Информатика

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

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

Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7–9

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

Ключевые слова: параллельные процессоры, метод ветвей и границ, максимальное временное смещение.

DOI: https://doi.org/10.21638/11701/spbu10.2016.405

Полный текст: PDF файл (311 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.8
Поступила: 9 марта 2016 г.
Принята к печати: 29 сентября 2016 г.

Образец цитирования: Н. С. Григорьева, “Задача минимизации максимального временного смещения для параллельных процессоров”, Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр., 2016, № 4, 51–65

Цитирование в формате AMSBIB
\RBibitem{Gri16}
\by Н.~С.~Григорьева
\paper Задача минимизации максимального временного смещения для~параллельных процессоров
\jour Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр.
\yr 2016
\issue 4
\pages 51--65
\mathnet{http://mi.mathnet.ru/vspui310}
\crossref{https://doi.org/10.21638/11701/spbu10.2016.405}
\elib{https://elibrary.ru/item.asp?id=28173686}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vspui310
  • http://mi.mathnet.ru/rus/vspui/y2016/i4/p51

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления
    Просмотров:
    Эта страница:142
    Полный текст:17
    Литература:20
    Первая стр.:10
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021