Software & Systems

Основной задачей теории расписаний (ТР) является разработка методов синтеза расписаний работы обслуживающих систем (ОС). Наиболее актуальны применения ТР в управлении многопроцессорными вычислительными системами, а также в календарном планировании и регулировании производственных процессов.

Среди различных разновидностей ОС [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.