 |
Задача линейного программирования №2
|
|
|
|
𝒔𝒏→𝐦𝐢𝐧
- 𝑠𝑖+𝑑𝑖≤𝑠𝑗 если работа i предшествует работе j
- 𝑠1= 0 ограничение на начало проекта
- 𝑠𝑖≥0 для каждой работы i
- 𝑑𝑖≤𝑑𝑖≤𝑑𝑖 для каждой работы i
- 𝐶𝑑1,…,𝑑𝑛,𝑠𝑛≤𝐶𝑚𝑎𝑥 – бюджетное ограничение
Билет № 10. Эвристические методы решения проблемы RSPSP, проблема MRCPSP
RSPSP – resource constrained Project scheduling Problem.
Необходимо минимизировать длительность при ограничении на ресурсы.
Ресурсы
- Возобновляемые (трудовые, сколько доступно часов в день)
- Не возобновляемые
Существует 2 типа ресурсов RSPSP
- Продолжительность работ не зависит от количества ресурсов
- Продолжительность зависит от количества ресурсов MRCPSP (то есть, если увеличиваются ресурсы, то можно уменьшить время и наоборот)
Эвристические методы решения RSPSP
- Конструктивные (схема расписания, правило приоритета)
- Улучшающие
Схема расписания
Классификация по методу:
· Последовательная (последовательно по приоритету)
Предполагает последовательное определение старта для работ из списка приоритетов с учетом ограниченных ресурсов в соответствии с выбранным направлением.
- Параллельная (одновременно в один день)
Предполагает формирование загрузки ресурсов параллельно идущими работами из списка приоритета в каждый день выполнения проекта.
Классификация по направлению:
- Прямая (нач-конец)
- Обратная (конец-начало)
- Двунаправленная (нач, конец, нач, конец)
В итоге чем в расписание меньше человеко-часов тем лучше.
Правила приоритета
1. Правила, основанные на внутренней информации о работах
2. Правила, основанные на информации о сети
|
|
|
3. Правила, основанные на информации СРМ
4. Правила, основанные на ресурсах
5. Гибридные правила
Правила 1 категории
- SPT = Shortest Processing Time
- LPT = Longest Processing Time
- 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
Ресурсные правила
- GRD = Greatest Resource Demand (трудоемкость продаж)
- 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
Основная идея: Применение дополнительных средств и ресурсов может сократить продолжительность критического пути.
Основная цель: Ускорить время реализации проекта при минимальных затратах.
|
|
|
Алгоритм
· Расчет модели и определение критического пути
· Расчет градиента издержек для каждой работы критического пути
· Исключение из полученного списка тех работ, у которых отсутствует градиент издержек
· Начало процесса сокращения длительности работ с критической работы, которая имеет наименьший градиент издержек
· Отслеживать возможное появление нового критического пути
· Если в сети имеются два и более критических пути, то следует сокращать длительности на одну и ту же величину на всех параллельных критических путях.
Недостатки
· Возможность появления нового критического пути
· Чревато срывом сроков так как за работами теперь надо следить так как они сокращены до максимума
· Не дает оптимального решения так как не учитывает количество параллельных путей
Решение недостатка, так как учитывает параллельные пути, дает оптимальное решение
|
|
|
