Journal influence
Bookmark
Next issue
Abstract:
Аннотация:
Authors: () - , Mezentsev Yu.A. (mesyan@yandex.ru) - Novosibirsk State Technical University (Professor), Novosibirsk, Russia, Ph.D | |
Keywords: optimisation, scheduling theory, , modeling |
|
Page views: 15259 |
Print version Full issue in PDF (1.92Mb) |
Основной задачей теории расписаний (ТР) является разработка методов синтеза расписаний работы обслуживающих систем (ОС). Наиболее актуальны применения ТР в управлении многопроцессорными вычислительными системами, а также в календарном планировании и регулировании производственных процессов. Среди различных разновидностей ОС [1] особое место занимают параллельные системы. Существует ряд подходов к синтезу расписаний массово параллельных систем [2-4]. Однако алгоритмы, учитывающие специфику конкретных предметных областей, например предназначенные для составления расписаний вычислительных систем, не всегда эффективны при синтезе расписаний ОС другого профиля, в частности, производственных объектов. Наивысшую актуальность разработка подобных алгоритмов обретает при синтезе расписаний параллельно-последовательных дискретных ОС, каковыми являются большинство производственных (технологических) объектов и процессов. Простейшим примером модели неоднородной одностадийной параллельной ОС является классическая задача о назначениях. Для синтеза расписаний параллельных (многоканальных) ОС в общем случае используются более сложные модели, описание и анализ которых составляют предмет рассмотрения настоящей статьи. Формальная постановка задачисинтеза расписанийпараллельных динамических систем Естественным обобщением статической задачи о назначениях является учет динамики поступления в ОС заявок для обслуживания. Пусть известно расписание поступления заявок в параллельную ОС. В этом случае необходимо учитывать величины задержек поступления заявок. Обозначим задержку поступления j-й заявки в ОС через и упорядочим заявки по возрастанию . Тогда динамическая модель оптимизации расписаний параллельной ОС будет иметь вид: , , (1) ££, , (2) (3) , непрерывные переменные, обнуляющие отрицательные задержки : , (4) , ,, (5) , , , (6) , , (7) . (8) Отрицательная задержка имеет смысл фактической задержки начала выполнения j-й заявки i-м прибором после завершения обслуживания им предшествующей заявки. Переменные вводятся для того, чтобы избежать появления отрицательных задержек . Критерий суммарного времени выполнения работ: . Приведем (1)-(8) к нормальному виду задачи математического программирования. Условия (4)-(7) содержат рекурсивные функции фактических задержек (расписание поступления заявок в ОС) tij. В явном виде tij как рекурсивные функции относительно переменных xij определяет (5). Раскрытие рекурсий (5) приводит к выражениям: , , , (9) где . При подстановке (9) в (6) и (7), получается задача, сложность которой в представлении (1)-(8) не адекватна возможностям современных алгоритмов оптимизации. Вместе с тем можно предложить различные способы ее редукции. Суть первого, заслуживающего внимание подхода состоит в приведении булевых функций типа к линейному виду посредством использования вспомогательных переменных, а также системы дополнительных неравенств. Подробно подобная процедура представлена в [5]. Обозначим: , , и введем в рассмотрение переменные , значения которых истинны только тогда, когда истинны значения . Соответствующие условия истинности можно задать посредством системы ограничений: , , , , . Тогда неравенства (7) примут вид: . Окончательно динамическая модель синтеза оптимального по быстродействию расписания (1)-(8), с учетом использованных преобразований, редуцируется в частично целочисленную линейную модель с булевыми переменными: , , (10) ££, , (11) (12) (13) , , , , , (14) , или , , (15) , , (16) , , (17) . (18) Таким образом, задача (1)-(8) сводится к задаче линейного программирования с булевыми переменными. Несмотря на формальную разрешимость редуцированной относительно (1)-(8) задачи (10)-(18), предложенный подход можно считать лишь начальным этапом общего решения [6]. Очевидно, что число булевых переменных в редуцированной задаче, как и число ограничений, увеличивается примерно в J/2 раз по сравнению с (1)-(8). Тем самым формальная сложность (1)-(8) редуцируется в вычислительную сложность (10)-(18). Второй возможный подход заключается в максимальном упрощении условий задачи. Его суть можно пояснить, модифицировав исходную задачу следующим образом. , , (19) ££, (20) (21) , , (22) , , (23) , . (24) Из контекста понятно, что второй подход к распределению заявок между приборами предполагает компромиссное решение по чистому быстродействию ОС без учета задержек и по равномерности распределения задержек между приборами. Линеаризовать векторный критерий можно посредством линейной свертки: , (25) где – параметр модели. Данную идею можно критиковать, однако модель (19)-(25) обладает неоспоримым преимуществом в размерности перед рассмотренной выше точной редукцией модели (1)-(8), а следовательно, по крайней мере на текущий момент времени, имеет большую практическую ценность. Численные эксперименты с обеими моделями подтверждают эффективность второго подхода, так как при использовании (19)-(25) наблюдается падение быстродействия синтезируемых расписаний ОС не более чем на 8 % от оптимального уровня, что для рассматриваемых объектов вполне приемлемо. Проиллюстрируем использование рассмотренных моделей для синтеза расписаний параллельных ОС на небольшом примере. Рассмотрим параллельную ОС, состоящую из двух неидентичных приборов, в которую на обслуживание неодновременно поступает семь заявок. Данные о нормах времени обслуживания заявок и задержках (расписании) поступления заявок в систему приведены в таблице.
Результатом решения задачи (10)-(18) с данными таблицы является вектор , на котором определены значения критериев и . Сформируем также матрицу времени завершения операций . С учетом задержек поступления заявок будем иметь: , , =18, =11. Отметим, что данный результат является наилучшим по всем рассматриваемым критериям. Для задачи (19)-(25) с данными таблицы также определим: , , и . Применение модели (19)-(25) при разных значениях параметра приводит к следующим результатам: , =21, =12, , =19, =11, Анализ результатов применения предложенных моделей для синтеза расписаний параллельных ОС подтверждает вывод о существенном преимуществе в размерности модели (19)-(25) перед (10)-(18) и о незначительном проигрыше в эффективности синтезируемых расписаний при тех же обстоятельствах. Список литературы 1. Левин В.И. Структурно-логические методы исследования сложных систем с применением ЭВМ. – М.: Наука, 1987. – 304 с. 2. Иванов Л.Н., Корчагин И.Я. Проблемно-ориентированная концепция построения структур массово параллельных вычислительных систем. // Автометрия. – Новосибирск. - 2002. – Т. 38. - № 5 – С. 68-75. 3. Коффман Э.Г. и др. Теория расписаний и вычислительные машины. - М.: Наука, 1984. – 336 с. 4. Корчагин И.Я. Использование метода аналогий в задачах распределения ресурсов и маршрутизации сообщений в массово параллельных вычислительных системах. / Вест. Хакасского гос. ун-та. - Абакан. - 2003. - Вып. 5, Сер. 1. - С. 53-58. 5. Иванов Л.Н., Мезенцев Ю.А. Модели синтеза расписаний параллельных обслуживающих систем. / Омский науч. вест. - Омск, Изд-во ОГТУ, 2006. - №9(46). - С.164-167. 6. Мезенцев Ю.А. Декомпозиционный метод решения одного класса задач оптимального проектирования. / Науч. вест. НГТУ. - Новосибирск, Изд-во НГТУ, 2006. - №3(24). - С. 67–100. |
Permanent link: http://swsys.ru/index.php?page=article&id=108&lang=&lang=&like=1&lang=en |
Print version Full issue in PDF (1.92Mb) |
The article was published in issue no. № 1, 2008 |
Perhaps, you might be interested in the following articles of similar topics:
- Программа выбора технологических режимов дискретно-непрерывного литья цветных металлов и их сплавов
- Подход к моделированию процесса оптимизации параметров эллиптических орбит спутниковой системы
- Программный комплекс планирования производства на малом предприятии
- Метод выбора оптимальной технологии строительства коммуникационного тоннеля
- Методы хранения данных систем видеонаблюдения с использованием грид-технологий
Back to the list of articles