Билет № 10. Эвристические методы решения проблемы RSPSP, проблема MRCPSP

RSPSP – resource constrained Project scheduling Problem.

Необходимо минимизировать длительность при ограничении на ресурсы.

Ресурсы

• Возобновляемые (трудовые, сколько доступно часов в день)
• Не возобновляемые

Существует 2 типа ресурсов RSPSP

1. Продолжительность работ не зависит от количества ресурсов
2. Продолжительность зависит от количества ресурсов MRCPSP (то есть, если увеличиваются ресурсы, то можно уменьшить время и наоборот)

Эвристические методы решения RSPSP

1. Конструктивные (схема расписания, правило приоритета)
2. Улучшающие

Схема расписания

Классификация по методу:

· Последовательная (последовательно по приоритету)

Предполагает последовательное определение старта для работ из списка приоритетов с учетом ограниченных ресурсов в соответствии с выбранным направлением.

• Параллельная (одновременно в один день)

Предполагает формирование загрузки ресурсов параллельно идущими работами из списка приоритета в каждый день выполнения проекта.

Классификация по направлению:

• Прямая (нач-конец)
• Обратная (конец-начало)
• Двунаправленная (нач, конец, нач, конец)

В итоге чем в расписание меньше человеко-часов тем лучше.

Правила приоритета

1. Правила, основанные на внутренней информации о работах

2. Правила, основанные на информации о сети

3. Правила, основанные на информации СРМ

4. Правила, основанные на ресурсах

5. Гибридные правила

Правила 1 категории

1. SPT = Shortest Processing Time
2. LPT = Longest Processing Time
3. RND = Random (но, с учетом отношения предшествования)

Правила 2 категории

1. MIS = Most Immediate Successors (наибольшее число прямых последователей)

2. MTS = Most Total Successors (больше всего последователей)

3. LNRJ = Least Non-Related Job (меньше всего связанных с ней работ)

4. GRPW = Greatest Rank Positional Weight (макс. сумма продолжительности работ и ее последователей)

Правила на основе CPM

1. EST = Earliest Start Time

2. EFT

3. LST

4. LFT

5. MSLK = Minimum Slack

6. RSM = Resource Scheduling Method (больше, меньше)

7. ESTD = Dynamic Earliest Start Time

8. EFTD = Dynamic Earliest Finish Time

9. MSLKD = Dynamic Minimum Slack

Ресурсные правила

1. GRD = Greatest Resource Demand (трудоемкость продаж)
2. GCUMRD = Greatest Cumulative Resource Demand (с учетом продукции)

3. RED = Resource Equivalent Duration (средневзвеш. Ресурсы х продажи)

4. CUMRED = Cumulative RED (накопл.)

Гибридные правила

1. WRUP = Weighted Resource Utilization and Precedence (ресурсы и другая приоритетность)

2. IRSM = Improved Resource Scheduling Method

3. WCS = Worst Case Slack

Улучшающие эвристические методы

1. Операторы поиска соседних решений

2. Формирование серии решений

3. Метаэвристические методы

Смысл: из существующих ресурсов последовательно улучшая их выбрать наиболее близкое к оптим. (то есть меньше простоев человеко-дней)

Операторы поиска соседних решений

1) Унарные операторы (изменение одного расписания)

• парная замена (меняем местами 2 работы)
• сдвиг (сдвигаем одну работу)

2) Бинарные операторы (получение из 2х одного)

• 1-точечное пересечение (скрещиваем)
• 2-точечное пересечение (скрещиваем в 2ух местах)
• универсальное пересечение (много пересечений из 2ух составляем 1 расписание)

Способ должен позволять спускаться по кривой

Поиск серии решений

· Крутой спуск (steepest descent) – из всех соседних решений выбрать самое лучшее

· Самый быстрый спуск (fastest descent) – поиск более подходящего решения среди соседей до первого найденного

· Метод итераций – время от времени начинать процесс крутого и наискорейшего спуска заново с некоторого случайно полученного конструктивным эвристическим методом решения (необходима память чтобы запоминать какие уже были)

Метаэвристические методы

• Поиск с запретами (tabu search) метод спуска с памятью (запрещенные позиции, которые уже использовались)
• Имитация закаливания (simulated annealing) (моделирование отжима)
• Начальное условие
• Соседние состояния
• Определяется вероятность перехода в эти состояния
• Изменение условия
• Вероятность перехода
• Муравьиные алгоритмы (Ant colony optimization)
• Генетический алгоритм (genetic algorithm)

Начинается с популяции из n решений. Для получения нового решения используем бинарный оператор для 2-х старых решений и вносим мутацию (унарный оператор, применяемый с низкой вероятностью)

+ быстро, наглядно, сразу несколько рассматривается попарно

- вырождение, сложность выбора схемы кодирования

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

Проблема MRCPSP

Задача RSPSP с учетом наличия мультиработ (мультирешений)

У работ есть альтернативы

Сделать одним либо другим способом

Тип

Решается методом DCPM

Выбрать наилучшую работы (характеризуется разной продолжительностью/ресурсами)

Тип

Когда продолжительность зависит от ресурсов, решаться может генетическим алгоритмом

Вопрос № 11. Проблемы TCTP и эвристические методы их решения (CPM-COST, метод Гояла)

TCTP – time cost trade-off problem

Ключевая проблема – нахождение компромисса между продолжительностью и стоимостью проекта.

Задачи для решения

1. Нахождение такого расписания проекта с заданной продолжительностью (навязанный финиш), которое позволит минимизировать стоимость его исполнения.

2. Нахождение такого расписания проекта с заданным бюджетным ограничением, которое позволит минимизировать продолжительность его выполнения.

Методы решения CPM-COST, Метод Гояла

Эвристические методы

CPM-COST

Основная идея: Применение дополнительных средств и ресурсов может сократить продолжительность критического пути.

Основная цель: Ускорить время реализации проекта при минимальных затратах.

Алгоритм

· Расчет модели и определение критического пути

· Расчет градиента издержек для каждой работы критического пути

· Исключение из полученного списка тех работ, у которых отсутствует градиент издержек

· Начало процесса сокращения длительности работ с критической работы, которая имеет наименьший градиент издержек

· Отслеживать возможное появление нового критического пути

· Если в сети имеются два и более критических пути, то следует сокращать длительности на одну и ту же величину на всех параллельных критических путях.

Недостатки

· Возможность появления нового критического пути

· Чревато срывом сроков так как за работами теперь надо следить так как они сокращены до максимума

· Не дает оптимального решения так как не учитывает количество параллельных путей

Решение недостатка, так как учитывает параллельные пути, дает оптимальное решение

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: