Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №4, Москва, 1992
Авторы: Асратян А.С., Мирумян А.Н.
Преобразования учебных расписаний
Аннотация:
Задачи составления учебных расписаний отражают в себе основную закономерность задач теории расписаний: как только математическая модель достаточно полно описывает учебный процесс, задача составления расписания становится NP-полной в смысле Р. Карпа. В связи с этим приходится использовать эвристические алгоритмы построения расписаний или рассматривать упрощенные модели учебного процесса. Возможен, однако, и другой подход: сначала строим некоторое h-расписание, соответствующее матрице Т, а затем перестраиваем его в h-расписание, удовлетворяющее требуемым условиям. В настоящей работе найдены три типа преобразований, с помощью которых от заданного h-расписания А, соответствующего матрице нагрузок T, можно перейти к любому h-расписанию С, также соответствующему матрице нагрузок Т. Предложен полиномиальный алгоритм такого перехода. Приводятся также некоторые комбинаторные применения полученных результатов. В частности, дано новое доказательство критерия однозначной представимости дважды стохастической матрицы в виде выпуклой комбинации подстановочных матриц. Графовые аналоги полученных результатов позволили решить для двудольных мультиграфов проблему А. Коцига о локализации преобразований реберных раскрасок.
Ключевые слова:
составление учебного расписания, матрица нагрузок, теория расписаний, преобразования расписаний
Язык публикации: русский,  страниц: 18 (с. 94-111)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Асратян Армен Суренович
  • Мирумян А.Н.