Планирование для одинаковых станков — это задача оптимизации в информатике и исследовании операций. Дан набор из n заданий (работ) J1, J2, ..., Jn с различным временем выполнения, которые должны быть распределены на m станков (машин), чтобы оптимизировать определённую целевую функцию, например, минимизировать работ.

Планирование для одинаковых станков является частным случаем планирования для однородных станков, которое, в свою очередь, является частным случаем оптимального планирования работы. В общем случае время выполнения каждого задания может быть различным на разных станках. В случае планирование для одинаковых станков время выполнения каждого задания одинаково для всех машин. Таким образом, планирование для одинаковых станков эквивалентно . Специальным случаем планирования для одинаковых станков является планирование для одного станка.

В стандартной 3-позиционной нотации для задач расписания работ вариант планирования для одинаковых машин обозначается буквой P в первом поле. Например, «P||» означает задачу планирование для одинаковых станков без ограничений, в которой целью является минимизация максимального времени завершения.

В некоторых вариантах задачи вместо минимизации максимального времени завершения требуется минимизировать среднее время выполнения (усреднённое по всем n заданиям). Это обозначается как P||. В более общем случае, когда некоторые работы важнее других, может потребоваться минимизировать взвешенное среднее времени завершения, где каждая работа имеет свой вес. Это обозначается как P||.

Алгоритмы

Минимизация среднего и взвешенного среднего времени выполнения Минимизация среднего времени завершения (P||) может быть выполнени за полиномиальное время. Алгоритм SPT (задание с наименьшим временем обработки в первую очередь, ) сортирует задания по их времени выполнения (в порядке возрастания) и назначает их исполнителям работ (машинам) в этом порядке. Алгоритм работает за время O(n log n) и минимизирует среднее время завершения на одинаковых машинах, P||.

Может быть много SPT расписаний. Поиск SPT расписания с наименьшим временем завершения работ (называется OMFT – , оптимальное среднее время завершения) является NP-трудной задачей.

Минимизация средневзвешенного времени завершения является NP-трудной задачей даже для одинаковых машин, что доказывается сведением к задачи о рюкзаке. Эта задача остается NP-трудной даже если количество машин фиксировано и составляет не менее 2, что доказывается сведением к задаче разбиения.

Сахни предлагает экспоненциальный по времени выполнения алгоритм и приближённую схему полиномиального времени для решения обеих NP-трудных задач для одинаковых машин:

Оптимальное среднее время завершения Средневзвешенное время завершения

Минимизация максимального времени выполнения (время завершения) Задача минимизации максимального времени выполнения (P||) является NP-трудной задачей даже для одинаковых машин, что доказывается сведением к задаче разбиения. Известно много точных и аппроксимационных алгоритмов.

Грэм доказал следующее: Любой (который обрабатывает задания в произвольном фиксированном порядке и назначает каждое задание первой доступной машине) является приближением для одинаковых машин. Эта граница является точной для любого m. Время выполнения такого алгоритма составляет O(n). Конкретный алгоритм списочного планирования, называемый наибольшее время обработки в первую очередь(, LPT), который сортирует задания по убыванию длительности, является аппроксимацией для одинаковых машин. Его также называют .

Коффман, Гэри и Джонсон представили другой алгоритм с названием , использующий методы упаковки в контейнеры и имеющий коэффициент аппроксимации 13/11≈1,182.

Хуанг и Лу предложили простой алгоритм полиномиального времени, который обеспечивает аппроксимацию 11/9≈1,222 за время O(m log m + n), решая более общую задачу распределения работ по принципу максимальной доли.

Сахни представил алгоритм PTAS (полиномиальная по времени аппроксимационная схема), который достигает аппроксимации (1+ε)OPT за время . Если m фиксировано, это FPTAS (, полностью полиномиальная по времени аппроксимационная схема). Для m=2 время выполнения улучшается до . Алгоритм использует технику, называемую интервальным разбиением.

Хохбаум и Шмойс представили несколько аппроксимационных алгоритмов для любого количества одинаковых машин (даже если их число не фиксировано): Для любого r >0 существует алгоритм с коэффициентом аппроксимации не более (6/5+2−r ) за время . Для любого r >0 существует алгоритм с коэффициентом аппроксимации не более (7/6+2−r ) за время . Для любого ε>0 существует алгоритм с коэффициентом аппроксимации не более (1+ε) за время . Это алгоритм PTAS. Когда количество машин является частью входных данных, задача является , поэтому алгоритм FPTAS невозможен. Леунг улучшил время выполнения этого алгоритма до .

Максимизация минимального времени завершения Максимизация минимального времени завершения (P||) применяется, когда «задания» являются запасными частями, необходимыми для поддержания работоспособности машин, и эти части имеют разный срок службы. Цель состоит в том, чтобы машины работали как можно дольше. Алгоритм достигает как минимум оптимального значения.

Вёгингер представил алгоритм PTAS, который достигает коэффициента аппроксимации за времяin , где — огромная константа, экспоненциально зависящая от требуемого коэффициента аппроксимации ε. В алгоритме используется алгоритм Ленстры для целочисленного линейного программирования.

Целевая функция общего вида Алон, Азар, Вёгингер и Ядид рассматривают более общую целевую функцию. Для заданной положительной вещественной функции f, зависящей только от времени завершения Ci, они исследуют следующие задачи: минимизацию , минимизацию , максимизацию и максимизацию . Они доказывают, что если функция f неотрицательна, выпукла и удовлетворяет сильному условию непрерывности, которое они называют «F*», то обе задачи минимизации имеют PTAS (приближённую схему полиномиального времени). Аналогично, если функция f неотрицательна, вогнута и удовлетворяет F*, то обе задачи максимизации также имеют PTAS. В обоих случаях время выполнения PTAS равно O(n), но с константами, экспоненциально зависящими от 1/ε.

См. также

Примечания

Ссылки Summary of parallel machine problems without preemtion

Категория:Оптимальные расписания