<<
>>

Задачи распределения ресурса на сетях

удобно рассматривать, изображая операции вершинами сети, а зависимости - дугами (представления «операции-дуги, события-вершины» и «зависимо-сти-дуги, операции-вершины» эквивалентны [10]).
Пунктиром могут быть отражены ресурсные зависимости - когда для выполнения одних и тех же операций должны быть использованы одни и те же ресурсы. Примером могут являться сети, изображенные на рисунках 6 и 7. Полным резервом операции (i; J) называется величина AiJ- = t^ - tj , где tп - поздний срок начала (окончания) операции, а t]' - ранний срок начала (окончания) операции.

11

Рис. 7. Представление «операции-вершины» для сети рисунка 6

Рис. 7. Представление «операции-вершины» для сети рисунка 6

Для определения оптимального распределения ресурса необ-ходимо найти критические пути для каждого из вариантов распределения ресурса и сравнить длины этих путей (в сети, приведенной на рисунке 7, существует общий для операций «0-1» и «0-2» ресурс; потенциалы вершин, соответствующие различным способам использования этого ресурса - сначала выполняется операция «01», затем «0-2» и наоборот, приведены на рисунке 7 соответственно в квадратных скобках и без скобок).

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

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

Рис.<div class=

8. Пример распределения ресурса" />

Рис. 8. Пример распределения ресурса

Легко показать, что в рассматриваемом примере оптимально выполнять первой операцию с минимальным ti.

Если для выполнения проекта выделено ограниченное количество ресурса, то возникает задача наилучшего его использования. Обозначим wi - объем i-ой операции, /-(у,) - скорость ее выполнения в зависимости от количества ресурса vПредположим, что /(•) - непрерывная справа неубывающая функция, причем /(0) = 0. Если vi(t) - количество ресурса на i-ой операции в момент времени

t, то момент ti ее окончания определяется как минимальное время, удовлетворяющее уравнению:

ti

\ / (V (t ))dt = w,-.

0

Если количество ресурса, используемое при выполнении некоторой операции, не изменяется во времени, то говорят, что она выполняется с постоянной интенсивностью. Тогда продолжительность операции определяется выражением

ti(Vi) = wi //(v).

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

Пусть все операции независимы и выполняются ресурсом одного вида, количество которого равно R, а /(V,) - непрерывные строго монотонные вогнутые функции. Тогда существует оптимальное решение, в котором каждая операция выполняется с постоянной интенсивностью и все операции заканчиваются одновременно в момент времени T, определяемый как минимальное время, удовлетворяющее следующему неравенству:

n w

Z /"Чw) ? R,

i=1 T

где /_1Q - функция, обратная функции/(•), i = 1,n [7, 10].

Эвристические алгоритмы определения оптимального распределения ресурса для ряда случаев «невогнутых» функций интенсивности рассматриваются в [1-4].

Обширный класс задач КСПУ составляют задачи агрегирования - представления комплекса операций (проекта) в виде одной операции и исследования свойств таких представлений, для которых оптимизация в рамках агрегированного описания дает решение, оптимальное для исходного (детального) описания. Основные подходы к постановке и решению задач агрегирования рассматри-ваются в [1, 2, 10, 16].

<< | >>
Источник: В.Н. Бурков, Д.А. Новиков. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ. 2001

Еще по теме Задачи распределения ресурса на сетях:

  1. 3.2. Понятие канала распределения и основные этапы его построения
  2. 1.2.1 Искусственные нейронные сети в системах распознавания
  3. Задачи распределения ресурса на сетях
  4. 3.1. Компьютерные сети
  5. Оптимальное распределение ресурсов в агрегированных комплексах
  6. 2.1. Сети с упорядоченными событиями
  7. Задача распределения объемов работ.
  8. Обратная задача распределения ресурса
  9. Сетевая система комплексного оценивания
  10. БИБЛИОГРАФИЯ
  11. 8. Направления и задачи образовательной политики
  12. 17.2. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
  13. ТОПОЛОГИЯ ГЛОБАЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ
  14. ФИНАНСОВЫЕ РЕСУРСЫ, ОСОБЕННОСТИ ИХ ФОРМИРОВАНИЯ И ИСПОЛЬЗОВАНИЯ В УСЛОВИЯХ РЫНКА
  15. § 2.8. Цели и задачи глобализма
  16. 2.6. Бизнес-процессы по предоставлению мобильных услуг сети Интернет
  17. 5.1. Цели и задачи внедрения ЭД в ССМП
  18. Сети информационного обмена
  19. роль предпринимательских сетей в инвестиционностроительной сфере
- Аналитическая геометрия - Вариационное исчисление - Векторный и тензорный анализ - Высшая геометрия - Высшая математика - Вычислительная математика - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комплексное исчисление - Линейная алгебра - Линейное программирование - Математика для экономистов - Математическая логика - Математическая физика - Математический анализ - Пределы - Ряды - Статистика - Теория вероятностей - Теория графов - Теория игр - Теория принятия решений - Теория случайных процессов - Теория чисел - Функциональный анализ -
- Архитектура и строительство - Безопасность жизнедеятельности - Библиотечное дело - Бизнес - Биология - Военные дисциплины - География - Геология - Демография - Диссертации России - Естествознание - Журналистика и СМИ - Информатика, вычислительная техника и управление - Искусствоведение - История - Культурология - Литература - Маркетинг - Математика - Медицина - Менеджмент - Педагогика - Политология - Право России - Право України - Промышленность - Психология - Реклама - Религиоведение - Социология - Страхование - Технические науки - Учебный процесс - Физика - Философия - Финансы - Химия - Художественные науки - Экология - Экономика - Энергетика - Юриспруденция - Языкознание -