Details

Выпускная квалификационная работа посвящена разработке системы автоматического распределения аудиторного ресурса для составления расписания поточных занятий в Санкт-Петербургском политехническом университете Петра Великого. Актуальность работы обусловлена неэффективностью существующего процесса составления расписания, который выполняется преподавателями вручную по принципу "кто первый занял время". Это приводит к появлению множества окон в расписании, неоптимальному распределению временных слотов и проблемам с размещением потоков первых курсов в аудиториях достаточной вместимости. В работе проведен анализ существующих решений на российском рынке и выявлены их недостатки для использования в СПбПУ. Формализована математическая модель задачи составления расписания с учетом всех ограничений университета: вместимости аудиторий, численности групп, пожеланий преподавателей, поддержки четных и нечетных недель. Доказана NP-полнота задачи путем сведения к задаче раскраски графа. Разработана математическая модель задачи, реализованы и протестированы выбранные алгоритмы. Создано клиент-серверное приложение на базе современных технологий. Полученная система поддерживает загрузку данных из Excel-файлов, управление сущностями расписания через веб-интерфейс и экспорт результатов в удобном формате.

The graduate qualification work is devoted to the automatic distribution of classroom resource system development for flow classes scheduling in St. Petersburg Peter the Great Polytechnic University. The relevance of the work is due to the inefficiency of the existing process of scheduling, which is carried out by teachers manually on the principle of “who took the time slot first”. This leads to the appearance of many gaps in the schedule, suboptimal distribution of time slots and problems with the placement of first-year students in classrooms of sufficient capacity. The paper analyzes existing solutions on the Russian market and identifies their disadvantages for use in SPbPU. A mathematical model of the scheduling problem was formalized considering all the university constraints: classroom capacity, number of groups, teachers requests, support of even and odd weeks. The NP-completeness of the problem was proved by reducing it to a graph coloring problem. A mathematical model of the problem was developed, selected algorithms were implemented and tested. A client-server application based on modern technologies was created. The resulting system supports downloading data from Excel files, managing schedule entities through a web interface and exporting results in a convenient format.