Оглавление
- 1 Оптимальное планирование работы
- 1.1 Оптимальное планирование заданий
- 1.2 Нотация для задач оптимального планирования
- 1.3 Одноступенчатые и многоэтапные задания
- 1.4 Машинная среда
- 1.5 Характеристики работы
- 1.6 Отношения приоритета
- 1.7 Временные задержки
- 1.8 Задержки с транспортировкой
- 1.9 Различные ограничения
- 1.10 Основные понятия
- 1.11 Многопроцессорные задачи
- 1.12 Целевые функции
- 1.13 Время выполнения и опоздание
- 1.14 Примеры задач
- 1.15 Стохастические варианты
- 1.16 Дополнительные ресурсы
- 1.17 Полный текст статьи:
- 2 Оптимальное планирование работы
Оптимальное планирование работы
-
Оптимальное планирование заданий
- Класс задач оптимизации, связанных с планированием
- Входные данные: список заданий и машин
- Результат: расписание, оптимизирующее целевую функцию
-
Нотация для задач оптимального планирования
- Введена Рональдом Грэмом и другими
- Состоит из полей α, β и γ
- Поле α описывает машинную среду
- Поле β описывает рабочие характеристики и ограничения
- Поле γ описывает целевую функцию
-
Одноступенчатые и многоэтапные задания
- Одноступенчатые задания: одноэтапное выполнение с заданным временем обработки
- Многоэтапные задания: несколько этапов выполнения, которые могут выполняться последовательно или параллельно
-
Машинная среда
- Одноступенчатые задания: P, Q, R
- Многоэтапные задания: O, F, J
-
Характеристики работы
- Время обработки: целое число, рациональное
- rj: время выхода задания
- dj: срок выполнения задания
- pmtn: возможность выгрузки и возобновления заданий
- размерj: количество машин для задания
-
Отношения приоритета
- prec: без ограничений
- цепочки: каждое задание предшествует не более чем одному другому
- внутреннее дерево: каждый узел предшествует не более чем одному заданию
- внешнее дерево: каждому узлу предшествует не более чем одно задание
- противоположный лес: граф отношений приоритета разбит на связанные компоненты
- sp-граф: последовательный параллельный граф
- ограниченная высота: длина самого длинного направленного пути ограничена
- порядок уровней: у каждого задания есть уровень, представляющий длину самого длинного направленного пути
- порядок интервалов: задание предшествует другому, если конец его интервала меньше начала интервала другого
-
Временные задержки
- ℓ: задержка одинакова для всех пар заданий
- ℓij: разные пары заданий могут иметь разную задержку
-
Задержки с транспортировкой
- tjk: задержка между завершением операции на машине k и началом операции на машине k+1
- tjkl: задержка между завершением операции на машине k и началом операции на машине l
- tk: задержка между завершением операции на машине k и началом операции на машине k+1
- tk:l: задержка между завершением операции на машине k и началом операции на машине l
- tj: задержка между завершением операции на машине k и началом операции на машине l
-
Различные ограничения
- rcrc: обещание о μ снимается, μkj может быть одинаковым для разных k
-
Основные понятия
- Различные операции одного задания могут быть назначены одной машине.
- Операция должна начинаться сразу после завершения предыдущей.
- Ни одна машина не должна простаивать.
-
Многопроцессорные задачи
- Выполнение задания на нескольких параллельных машинах.
- Каждая работа требует одновременного выполнения на всех машинах.
- Многоцелевые станки: каждая работа выполняется на одной машине из заданного набора.
-
Целевые функции
- Минимизация объективной ценности.
- Максимизация пропускной способности.
- Отсутствие объективного значения: составление приемлемого расписания.
-
Время выполнения и опоздание
- Время завершения задания.
- Максимальное время завершения (makespan).
- Опоздание: разница между временем завершения и сроком исполнения.
- Пропускная способность: удельная прибыль за выполнение в срок.
- Задержка с выполнением: максимальное опоздание.
- Раннее начало: максимальное опережение.
-
Примеры задач
- Назначение заданий на две идентичные машины для минимизации максимального времени обработки.
- Назначение процессов одной машине для минимизации максимального опоздания.
- Назначение задач переменному числу параллельных машин для минимизации общего времени выполнения.
- Задача цеха с 3 станками для минимизации максимального времени завершения.
- Назначение заданий для m параллельных машин для минимизации максимального времени выполнения.
-
Стохастические варианты
- Данные могут быть неизвестны или изменяться случайным образом.
- Игры с балансировкой нагрузки: задания принадлежат стратегическим агентам.
- Равновесие Нэша может быть неоптимальным.
-
Дополнительные ресурсы
- Планирование зоопарка: онлайн-инструмент для поиска оптимальной задачи планирования.
- Результаты оценки сложности задач планирования: классификация задач по сложности.