Билет № 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 с учетом наличия мультиработ (мультирешений)

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

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

1 тип

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

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

2 тип

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