Планирование на одной машине - Single-machine scheduling

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

Показатели эффективности

Показатели производительности задач в задаче планирования одной машины включают:

• Опоздание – ${displaystyle max(0,receipt;date-due;date)}$
• Раннее – ${displaystyle max(0,due;date-receipt;date)}$
• Опоздание – ${displaystyle receipt;date-due;date}$
• Время потока – ${displaystyle end;date-start;date}$

Методы решения

Многие методы решения были применены для решения задач планирования одной машины. Некоторые из них перечислены ниже.

Эвристика

• Кратчайшее время обработки (SPT)

График SPT является оптимальным, если целью является минимизация среднего времени потока.

SPT-заказ - это заказ, основанный на времени обработки. Последовательность оставшихся заданий отсортирована по неубывающему времени обработки.

• Самый ранний срок (EDD)

График EDD является оптимальным, если цель - минимизировать максимальное опоздание.

EDD-заказ - это заказ в установленный срок. Последовательность оставшихся заданий отсортирована по неубывающей дате выполнения.

Примечание. «Опоздание» - это любое отклонение от установленного срока. Положительное опоздание - это «опоздание», отрицательное опоздание - «опоздание».

• Алгоритм Ходжсона

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

Вычислительная

• Генетические алгоритмы
• Нейронные сети
• Имитация отжига
• Оптимизация колонии муравьев
• Табу поиск

Рекомендации