Теория расписаний, нужна помощь в доказательстве NP-полноты (original) (raw)

Приветствую участников сообщества.

Собственно, "ковыряюсь" со следующей задачей. Опишу её условиями. Тем, кто готов повтыкать, рекомендую сразу рисовать графики/диаграммы Гантта или чё-то подобное, чтобы яснее представлять себе картинку. Итак:

  1. Есть система, состоящая из двух приборов. Назовём их соответственно прибор 1, прибор 2.
  2. Есть список требований. Для каждого требования задано, на каком приборе оно должно быть обслужено, причём, такой прибор для требования единственный. Задано время обслуживания каждого требования. Каждый прибор может одновременно обслуживать не более одного требования. Требования обслуживаются без прерываний.
  3. Если прибор 1 занят обслуживанием, то требование на прибор 2 не может поступить раньше, чем освободится прибор 1.
  4. Если прибор 2 занят обслуживанием, то требование, закончившее обслуживание на приборе 1, не может покинуть систему раньше, чем освободится прибор 2.
  5. Минимизировать makespan (т.е. чтобы обслуживание последнего требования закончилось как можно ранее)

Предполагается, что требования начинают поступать в нулевой момент времени, а время на доставку требований к приборам не учитывается.

Эта задача оказалась полиномиально разрешимой. Рассмотрев пару математических неравенств, можно показать, что требования в систему должны поступать парами (одно на прибор 1 и одно на прибор 2), пока такое возможно. А порядок можно задать сортировкой. Т.е. разделить список всех требований на 2 списка: "требования на прибор 1" и "требования на прибор 2". И каждый из полученных списков отсортировать, например, по невозрастанию. И, повторюсь, из этих отсортированных списков выбирать последовательно по одному требованию и парами запускать в систему. Это даст требуемый оптимум (сумма максимумов из времён одновременно запускаемых требований).

Теперь добавляется ещё одно ограничение. Заданы директивные сроки, к которым каждое требование должно закончить обслуживание. Для простоты рассматриваю хотя бы два срока: D1 и D2. То есть часть требований должна быть обслужена к сроку D1, а оставшаяся часть к сроку D2. Если таковое невозможно, то считается, что задача решения не имеет.

Здесь сразу вытекают очевидные свойства.

  1. Если, забив на сроки, мы построили оптимальное расписание (вышеописанным алгоритмом), и оказалось, что всё выполнилось раньше D1, то расписание построено, никакой проблемы нет.
  2. Если, забив на сроки, мы построили оптимальное расписание (вышеописанным алгоритмом), и оказалось, что всё выполнилось позже D2, то решения задача не имеет, никакой проблемы нет.
  3. Проблема возникает, если построенное обычным образом (вышеописанным алгоритмом) расписание ведёт к тому, что обслуживание заканчивается между D1 и D2. Здесь и следует искать решение задачи.
    3а) Теперь берём только требования с директивным сроком D1 и строим (вышеописанным алгоритмом) расписание для них. Если всё заканчивается позже D1, то задача решения не имеет.

Итак, проблема имеет место, если оказалось, что одновременно выполнены 2 условия:
а) Построенное обычным образом (вышеописанным алгоритмом) расписание ведёт к тому, что обслуживание заканчивается между D1 и D2.
б) Расписание, построенное обычным образом (вышеописанным алгоритмом) только из требований с директивным сроком D1 ведёт к тому, что обслуживание заканчивается не позже D1.

Сдаётся мне, что проблема эта NP-полна. Почему? Потому что я пробую применить к ней подход такой (пока ерундовый, ибо ещё только копаю задачу): опять же отсортировать списки требований на прибор 1 и прибор 2. И пытаться ставить их последовательно парами. На каждом шаге постановки в недостроенном расписании проверять обычным (вышеописанным) алгоритмом, если продолжить последовательность в расписании только требованиями с директивным сроком D1, то не "вылезем ли" мы за пределы D1. И если вылазим, то не ставить очередное неблагоприятное требование с директивным сроком D2 сюда, а просто его пропустить. Рано или поздно, делая шаги постановок парами, настанет момент, когда закончатся требования с директивным сроком D1 и по ходу построения мы не вылезем за D1. Тогда можно взять все пропущенные требованя со сроком D2 и плюс к ним все пока не затронутые требования со сроком D2. И ими достроить дальше расписание. Естественно, этот подход является эвристическим, так как использует "жадный" подход, когда мы пропускаем или ставим очередное требование с директивным сроком D2.

Что собой по сути представляет оптимальное расписание? Всяческими равносильными преобразованиями можно показать, что нас интересует только класс расписаний, у которых:

  1. В расписании, пока не закончились требования с директивным сроком D1, нету пары одновременно обслуживаемых требований с директивным сроком D2.
  2. Пока идут требования с директивным сроком D1, расписание представляется в виде пар, полученных сортировкой по невозрастанию (из всех задействованных на этом участке требований, т.е. со сроками D1 и D2).
  3. Далее есть требования только с директивным сроком D2, и на этом участке тоже расписание представлено в виде пар, полученных сортировкой по невозрастанию.

По сути, множество требований с директивным сроком D2 в оптимальном расписании разбивается на 2 части: одна "перемешана" с требованиями со сроком D1 и, таким образом, вышеописанным алгоритмом построен первый "кусок" расписания. А из второй части тербований со сроком D2 снова вышеописанным алгоритмом построен оставшийся "кусок" расписания. Вот момент, который наталкивает на NP-полноту задачи в том и состоит, что заранее непонятно, как разделить требования со сроком D2 на два множества... Но свести какую-нить NP-полную задачу к особому случаю данной задачи у меня пока не вышло. У кого есть здравые идеи, как выйти на такую NP-полную задачу, или может всё же выйти на полином в задаче с директивными сроками, с удовольствием выслушаю.

Welcome for discussion, guys & girls!