Задачи составления учебных расписаний отражают в себе основную закономерность задач теории расписаний: как только математическая модель достаточно полно описывает учебный процесс, задача составления расписания становится NP-полной в смысле Р. Карпа. В связи с этим приходится использовать эвристические алгоритмы построения расписаний или рассматривать упрощенные модели учебного процесса. Возможен, однако, и другой подход: сначала строим некоторое h-расписание, соответствующее матрице Т, а затем перестраиваем его в h-расписание, удовлетворяющее требуемым условиям. В настоящей работе найдены три типа преобразований, с помощью которых от заданного h-расписания А, соответствующего матрице нагрузок T, можно перейти к любому h-расписанию С, также соответствующему матрице нагрузок Т. Предложен полиномиальный алгоритм такого перехода. Приводятся также некоторые комбинаторные применения полученных результатов. В частности, дано новое доказательство критерия однозначной представимости дважды стохастической матрицы в виде выпуклой комбинации подстановочных матриц. Графовые аналоги полученных результатов позволили решить для двудольных мультиграфов проблему А. Коцига о локализации преобразований реберных раскрасок.

составление учебного расписания, матрица нагрузок, теория расписаний, преобразования расписаний

Математические вопросы и теория численных методов