Планирование для однородных станков — это задача оптимизации в информатике и исследовании операций. Это вариант задачи оптимального расписания работ. Дан набор из n заданий (работ) J1, J2, ..., Jn с различным временем выполнения, которые должны быть распределены на m станков (машин). Цель состоит в минимизации — полного времени, необходимого для завершения всего расписания. Время, которое машина i затрачивает на обработку задания j, обозначается как pi,j. В общем случае времена pi,j не связаны между собой и возможна любая матрица положительных времён обработки. В конкретном варианте, называемом планированием для однородных машин, некоторые машины равномерно быстрее других. Это значит, что для каждой машины i существует коэффициент скорости si и время выполнения задания j на машине i равно pi,j = pj / si.

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

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

Алгоритмы

Минимизация среднего времени завершения Минимизация среднего времени завершения может быть выполнена за полиномиальное время: Алгоритм SPT (, cначала кратчайшее время обработки), сортирует задания по времени выполнения в порядке возрастания, а затем назначает их обработчику с наименьшим текущим временем завершения. Алгоритм работает за время O(n log n) и минимизирует среднее время завершения на одинаковых машинах, P||. Горовиц и Сахни представили точный алгоритм со временем выполнения O(n log m n) для минимизации среднего времени завершения на однородных машинах, Q||. Бруно, Коффман и Сети представили алгоритм, работающий за время , для минимизации среднего времени завершения на несвязанных машинах, R||.

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

Сахни предлагает алгоритм экспоненциального времени и алгоритм приближения полиномиального времени для одинаковых машин.

Горовиц и Сахни предложили

Точные алгоритмы динамического программирования для минимизации взвешенного среднего времени завершения на однородных машинах. Эти алгоритмы работают экспоненциальное время. Приближённая схема полиномиального времени, которые для любого ε>0 достигают значения не более (1+ε)OPT. Для минимизации взвешенного среднего времени завершения на двух однородных машинах, время работы составляет = , что делает их FPTAS (, полностью полиномиальная по времени аппроксимационная схема). Они утверждают, что их алгоритмы легко расширяютс для любого количества однородных машинах, но не анализируют время работы в этом случае. Они не представляют алгоритм для взвешенного среднего времени завершения на неоднородных машинах.

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

Алгоритм наибольшее время обработки в первую очередь обеспечивает приближённое решение с постоянным коэффициентом.

Горовиц и Сахни предложили: Точные алгоритмы динамического программирования для минимизации максимального времени завершения как на однородных, так и на неоднородных машинах. Эти алгоритмы работают за экспоненциальное время (вспомним, что все эти задачи являются NP-трудными). Приближённые схемы полиномиального времени, которые для любого ε>0 достигают значения не более (1+ε)OPT. Для минимизации максимального времени завершения на двух однородных машинах их алгоритм работает за время , где — наименьшее целое число, для которого . Следовательно, время выполнения составляет , что делает его . Для минимизации максимального времени завершения на двух неоднородных машинах, время выполнения составляет = . Они утверждают, что их алгоритмы могут быть легко расширены для любого количества однородных машин, не анализируют время выполнения в этом случае.

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

Эпштейн и Сгалл обобщили PTAS для однородных машин, чтобы обрабатывать более общие целевые функции. Пусть Ci (где i находится между 1 и m) — время завершения работы машины i в заданном расписании. Вместо минимизации целевой функции max(Ci), можно минимизировать целевую функцию max(f(Ci)), где f — любая фиксированная функция. Аналогично, можно минимизировать целевую функцию sum(f(Ci)).

Монотонность и правдивость В некоторых сценариях скорость машины является её конфиденциальной информацией, и мы стремимся стимулировать машины раскрывать свою истинную скорость, то есть нам нужен механизм, обеспечивающий правдивость. Важным фактором для достижения правдивости является монотонность. Это означает, что если машина сообщает о более высокой скорости, а все остальные входные данные остаются неизменными, то общее время обработки, выделенное машине, слабо увеличивается. Применительно к данной проблеме:

Аулетта, Де Приско, Пенна и Персиано представили монотонный алгоритм с 4-кратной аппроксимацией, который работает за полиномиальное время при фиксированном числе машин. Амброзио и Аулетта доказали, что алгоритм наибольшее время обработки в первую очередь является монотонным, когда скорости машин являются степенями некоторого , но не когда . В отличие от этого, не является монотонным для c > 2. Андерман, Азар и Сорани представили монотонный алгоритм с 5-кратной аппроксимацией, который работает за полиномиальное время даже при переменном числе машин. Ковач представил алгоритм с 3-кратной аппроксимацией.

Расширения Зависимые задания: В некоторых случаях задачи могут быть взаимозависимыми. Например, апример, рассмотрим сценарий, где сначала считываются учетные данные пользователя с консоли, затем они используются для аутентификации, и только после успешной аутентификации отображаются определённые данные на консоли. Очевидно, что одна задача зависит от другой. Это явный пример существования определённого порядка между задачами. Фактически это можно смоделировать с помощью частичного порядка. Тогда, по определению, набор задач образует структуру решетки. Это еще больше усложняет проблему планирования для многопроцессорных систем.

Статическое/Динамическое: Алгоритмы планирования задач для машин бывают статическими или динамическими. Алгоритм расписания является статическим, если алгоритм принимает решения о том, какие вычислительные задачи будут назначены каким процессорам, ещё до запуска программы . Алгоритм является динамическим, если он принимает решения во время выполнения программы. Для статических алгоритмов обычно используется подход, при котором задачи ранжируются в соответствии с их зависимостями, а затем применяется метод списочного планирования для их распределения по процессорам.

Многоэтапные задачи: В некоторых случаях каждая задача может состоять из нескольких операций, которые должны выполняться параллельно. Такие ситуации рассматриваются в рамках планирования для , поточных линий и .

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

Примечания

Категория:Оптимальные расписания Категория:NP-полные задачи