Материал: Оптимизация и моделирование в автоматизированных системах

Рис. 2. Структурная схема алгоритма функционирования модели вычислительной машины

220

GENERATE

3,1,,200

TEST MARK

Q$Och,1,Met1

QUEUE

TERMINATE

1

SEIZE

Ustr

DEPART

Och

TEST

MP1,12 ADVANCE

5, 2

RELEASE Ustr

TERMINATE

1

TERMINATE

1

Рис. 3. Блок-диаграмма функционирования модели

После успешного запуска программы появится вывод результатов моделирования (рис. 4).

Рис. 4. Отчёт моделирования

221

На приведенном отчете показано время начала моделирования 0, время окончания моделирования 1046.175, количество блоков 12, количество устройств 0, модулей памяти 1.

Также отображены имена объектов модели, с присвоенным им именем и числовым значением. Отчет по блокам состоит из меток, присвоенных блокам, номеров блоков, типов блока, числа вхождений в блок, числа транзактов оставшихся в модели на момент завершения моделирования и количества заблокированных транзактов.

Таким образом, в процессе моделирования был сгенерирован 201 транзакт, 201 был обработан.

Литература

1.Советов, Б.Я., Моделирование систем: учебник для ВУЗов / Б.Я. Советов, С.А. Яковлев. – Москва: Высшая школа, 2001. – 343 с.

2.Волкова, В.Н. Моделирование систем и процессов / В.Н. Волкова, Г.В. Горелова, В.Н. Козлов. – Москва: Юрайт, 2016. – 596 с.

3.Боев В.Д. Моделирование систем. Инструментальные средства GPSS World / В.Д. Боев. – СПб.: БХВ-Петербург, 2005. – 368 с.

ФГБОУ ВО «Воронежский государственный технический университет», Россия

УДК 519.16

Е.А. Кумагина, Д.М. Кукушкина

МЕТОД ВЕТВЕЙ И ГРАНИЦ ДЛЯ ЗАДАЧИ УПОРЯДОЧЕНИЯ РАБОТ НА ОДНОМ ПРИБОРЕ С ДИРЕКТИВНЫМИ СРОКАМИ

В общем виде задача обслуживания потока требований одним прибором формулируется следующим образом. Пусть требования множества N = {1, 2, ..., n} обслуживается одним прибором. Каждое требование i, i N характеризуется моментом поступления di, длительностью обслуживания ti, директивным сроком Di. В каждый момент времени прибор обслуживает не более одного требования. Порядок обслуживания требований произвольный. Прерывания в обслуживании каждого отдельного требования не допускаются. Недопустимо начало обслуживания требований до их поступления в систему. Нарушения директивных сроков возможны. Требуется минимизировать суммарное число тактов обслуживания требований после директивного срока.

Поставленная задача относится к классу NP-трудных [1], поэтому поиск точного решения возможен только для задач небольшой размерности, и разработка эвристических методов является актуальной. Для решения поставленной

222

задачи предлагаются модификации, основанные на методологии метода ветвей и границ [2,3].

Каждую из вершин дерева ветвления будем представлять в виде v=(Ak, Bk), где k – уровень вершины, k =1,n , Ak – множество требований, уже постав-

ленных в расписание, Ak Bk = N , Ak ∩ Bk = .

Для решения поставленной задачи были разработаны процедуры:

1. В качестве выбора стартовой перестановки π0 рассматривались два варианта – лексикографическое упорядочение и упорядочение по неубыванию

вания множества Ak уже поставлены в расписание в порядке, определяемом путем к вершине v, требования множества Bk сортируются в порядке неубывания их приоритетов;

4.Для выбора очередной вершины для ветвления рассматривались две стратегии – оптимистичная (вершина с наименьшей нижней оценкой) и реалистичная (вершина с наименьшей верхней оценкой);

5.Вершина исключается из рассмотрения, если значение нижней (недостижимой) оценки в ней больше значения текущего рекорда;

6.Алгоритм завершает работу, когда осталась одна не отброшенная вер-

шина.

Для сравнения эффективности предложенных процедур был проведен вычислительный эксперимент. Были сгенерированы серии задач упорядочения 15 работ. Целочисленные времена выполнения работ, начальные и директивные сроки выбирались случайным образом из интервала (0, 100).

Наиболее эффективной оказалась следующая комбинация параметров метода ветвей и границ: сортировка по приоритетам первоначальной перестановки и реалистический способ ветвления.

На основе разработанных процедур разработан эвристический алгоритм,

вкотором используется обход дерева в глубину. На первом этапе алгоритма определяются n направлений поиска решения, в каждом из которых независимо от других направлений применяется только процедура ветвления в одной вершине на каждом уровне. Таким образом будет получено n допустимых решений, из которых выбирается лучшее. Относительное отклонение полученных решений от оптимального составило в среднем 0,574% при оптимистической стратегии и 3,217% в среднем при реалистической стратегии.

223

При реализации этого подхода возможно распараллеливание работы алгоритма [4]: создается количество потоков равное количеству требований, и в каждом потоке решается задача поиска решения. Предложенная реализация позволила уменьшить время получения решения в среднем в 3 раза.

В работе рассмотрена NP-трудная задача обслуживания потока требований одним прибором. Представлен подход к ее решению, основанный на методе ветвей и границ. В ходе вычислительного эксперименты выбраны параметры алгоритма.

Литература

1.Прилуцкий, М.Х. Задача упорядочения работ как задача о назначениях

/М.Х. Прилуцкий, Е.А. Кумагина // Вестник Нижегородского университета им. Н.И. Лобачевского. – 1999. – № 2. – С. 270-275.

2.Прилуцкий, М.Х. Метод ветвей и границ решения задачи многоресурсного сетевого планирования / М.Х. Прилуцкий, Е.А. Кумагина // Системы управления и информационные технологии. – 2014. Т. 56. – № 2. – С. 48-51.

3.Старостин, Н.В. Метод ветвей и границ решения квадратичной задачи о назначениях с приложениями в области высокопроизводительных вычислений / Н.В. Старостин, М.А. Быкова // Системы управления и информационные технологии. – 2017. – Т. 67. – № 1. – С. 13-18.

4.Панкратова, М.А. Гибридные схемы решения задачи отображения параллельной программы на вычислительную сеть / М.А. Панкратова // Системы управления и информационные технологии. – 2015. – Т. 61. – № 3. – С. 64-70.

ФГБОУ ВО «Нижегородский государственный университет им. Н.И. Лобачевского», Россия

УДК 004.4

Ю.С. Скворцов, А.В. Шматова

МОДЕЛЬ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ СЕВООБОРОТА

В статье рассматривается модель динамического программирования для оптимизации севоборота.

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

224