Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

НАУЧНЫЕ НАПРАВЛЕНИЯ - ТЕОРИЯ РАСПИСАНИЙ

30 апреля 2012 года в 17:28   Просмотров: 49609

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

 

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

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

ПРИМЕР ТИПИЧНОЙ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ – классическая задача 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)

© ИМ СО РАН, Новосибирский Государственный Университет, 2010г. 

Оставить комментарий

Пожалуйста, введите символы, показанные на рисунке.

Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта