Научные направления - Теория расписаний


Как известно, Человечество в своём стремительном развитии старается всё более расширить сферы своей деятельности, сталкиваясь при этом с множеством новых ситуаций, из которых требуется искать выход. Для решения возникающих при этом задач Человек организует новые Процессы (т.е., протекающие во времени действия, направленные на решение конкретных прикладных задач), которые ставит под свой неусыпный контроль. Оптимизацией таких процессов занимаются многие науки, различающиеся способами моделирования процессов, спецификой решаемых задач и набором используемых методов. Одной из таких наук применительно к задачам дискретной оптимизации является теория расписаний.

В чём состоит специфика теории расписаний, её отличие от других наук, занимающихся сходными проблемами? Во-первых, для неё характерно огромное разнообразие теоретических моделей, проистекающее из разнообразия реальных моделируемых процессов. (Легко понять, что проблема оптимальной организации протекающих во времени процессов имеет глобальный характер и возникает практически во всех сферах человеческой деятельности.) Второй особенностью является комбинаторная природа исследуемых моделей и решаемых оптимизационных задач, которая обуславливает высокую комбинаторную сложность их решения. И, в-третьих, для теории расписаний характерна высокая актуальность (злободневность) решаемых задач, ввиду их ярко выраженной прикладной направленности.

При всём при том, теория расписаний занимается вполне теоретическими проблемами, разработкой наиболее общих и универсальных методов решения возникающих в ней оптимизационных задач. Естественным следствием разнообразия теоретических моделей теории расписаний является тот очевидный факт, что практически вся дискретная математика лежит внутри моделей и задач теории расписаний (как её «служебные подразделы») или используется в методах их решения – здесь применимы и потоковые алгоритмы, и результаты по задачам раскраски вершин и рёбер графов и мультиграфов, задачи выполнимости булевых формул и задачи на единичном кубе, векторные ряды и матрицы Адамара. При этом – такое «море» открытых проблем (доступных для понимания даже первокурснику), что рискнувшему погрузиться в это море студенту вопрос «чем бы заняться» – точно не грозит до самой старости.

ПРИМЕР ТИПИЧНОЙ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ – классическая задача OPEN SHOP (в вольном переводе на русский – скорее «свободный цех», чем «открытый магазин»). Имеется конечное множество операций {O1,…,ON}. Каждой операции Oi приписаны два атрибута и один числовой параметр:

M(Oi)\in {M1,…,Mm} – машина, на которой выполняется операция;

J(Oi)\in {J1,…,Jn} – работа, которой принадлежит операция;

pi – длительность операции Oi (в течение такого времени операция должна непрерывно выполняться на заданной машине).

Для задания РАСПИСАНИЯ выполнения операций на машинах достаточно задать интервал выполнения каждой операции (или – момент начала каждой операции). ОГРАНИЧЕНИЯ на допустимое расписание выполнения операций: Операции Oi, Oj не могут выполняться одновременно (в ненулевом интервале времени), если они имеют одинаковый атрибут M либо J. ЦЕЛЕВАЯ ФУНКЦИЯ – минимум длины расписания (хотя могут быть и другие целевые функции). Задачи с такой ЦФ называют «задачами на быстродействие».

Если длительности всех операций равны 1, задача имеет простую графскую интерпретацию. Пусть операции – вершины графа G=(V,E). Две вершины соединяем ребром, если они имеют одинаковый атрибут M либо J. (Таким образом, граф распадается на два «взаимно ортогональных» семейства клик.) Требуется покрасить вершины графа в минимальное число цветов.

Другая интерпретация: Изображение машин и работ вершинами двудольного графа (левой и правой доли), а операции Oi – мультиребром «толщины» pi между вершинами M(Oi) и J(Oi) (pi предполагаются целыми числами). При раскраске рёбер двудольного мультиграфа (в минимальное число цветов) требуется «интервальность» цветов рёбер для каждого мультиребра. (При этом в классической задаче OPEN SHOP каждая работа имеет не более одной операции на каждой машине.)

Ясно, что длина оптимального расписания не меньше максимальной степени вершины (D) в таком графе: OPT ≥ D.

ПРИМЕРЫ ТИПИЧНЫХ ОТКРЫТЫХ ПРОБЛЕМ:

  1. Можно ли решить задачу OPEN SHOP за полиномиальное время, если имеется 3 машины, а каждая работа имеет не более двух операций? (открыта с 1976 года)
  2. Верно ли, что всегда OPT ≤ 3/2 D? (открыта > 30 лет)
  3. Верно ли, что всегда OPT ≤ D+pmax? (pmax=max_i pi)

Преподаватели: