Алгоритм составления расписания занятий в ВУЗЕ

← →
Inventor (2005-03-10 10:54) [0]

Кто - нибудь занимался подобным? Начал писать свой алгоритм, но с первых строк столкнулся с множеством проблем. Мастера, с чего бы начали Вы решать этот алгоритм?

← →
Закулиса Мировая (2005-03-10 11:01) [1]

С анализов. Т.е анализа. В смысле, системного. Один из этапов коего - сбор данных. Одним из подэтапов которого - общение с будущими пользователями системы с целью задокументировать их работу, то есть то, что некоторые называют "бизнес-процессы". Т.е. пошёл бы в учебную часть и посмотрел, как они сетку на ватмане вырисовывают и ластиком подтирают.

← →
digger © (2005-03-10 11:01) [2]

В нашем ВУЗе несколько дипломников подряд пытались решить эту задачу, но так и не до вели до ума. Эта задача не так проста. Поэтому у нас до сих пор все делается в ручную.

← →
Inventor (2005-03-10 11:13) [3]

2 Digger - аналогично. я точно знаю, что было 3 дипломных работы на эту тему в моём ВУЗЕ, и с такими же результатами.

2 Закулиса Мировая - мой близкий родственник 20 лет работал директором школы. как она "сетку на ватмане вырисовывала и ластиком подтирала" я уже спрашивал. анализировал.
на основе этих данных оптимизационный алгоритм не написать.

← →
Рамиль © (2005-03-10 11:18) [4]

digger © (10.03.05 11:01) [2]
Inventor (10.03.05 11:13) [3]
У нас тоже никто не брался.

← →
GrayHairs (2005-03-10 11:23) [5]

Я не мастер, но расскажу. Именно про сбор данных. В одном учебном заведении были учебные помещения в нескольких корпусах в разных концах города. Таким образом нужно было учитывать
1)учебные предметные планы
2)почасовую загрузку преподавателей.
3)вместимость аудитории(мастерской - это было худож.училище)
4)время на переезд учащихся и преподавателей по городу - вставляя т.н. окна
5)Ну и личные особенности препод состава. Например для пожилых преподавателей исключить верхние этажи в корпусах без лифтов,
а преподавтели-совместители могли давать лекции только в определенные дни и часы... ну и т.д.
Одним словом - там и сейчас на ватмане рисуют. И долго будут.

← →
Sergey13 © (2005-03-10 11:31) [6]

2Inventor (10.03.05 10:54)
ИМХО, эта задача вообще не поддается четкой алгоритмизации.
Реально можно сделать только замену ватмана на таблицу в компе. Ну и несложные проверки на корректность. Типа один препод не может быть в одно время в разных аудиториях и т.п.

← →
КаПиБаРа © (2005-03-10 11:45) [7]

Sergey13 © (10.03.05 11:31) [6]
ИМХО, эта задача вообще не поддается четкой алгоритмизации.

ИМХО эта задача не сложнее алгоритма игры в шахматы (шашки) :)

← →
ex080D:07BBh (2005-03-10 11:49) [8]

КаПиБаРа © (10.03.05 11:45) [7]
общий вариант решения есть то есть просто грубый набросок можно словами?

← →
Димон (2005-03-10 11:50) [9]

> [7] КаПиБаРа © (10.03.05 11:45)

с точки зерния реализации не сложнее.

с точки зрения оценки результата - сложнее.

в шахматах есть четкий критерий - мат, значит молодец.

Тут критерев много. Возможно нужно будет вводить многомерную дискретную функцию и ее оптимизировать.

← →
blackman © (2005-03-10 11:57) [10]

Зачем все усложнять ? Вводим несколько типичных расписаний по семестрам и потом даем выбирать и править, запоминать в качестве типового варианта. Примитивно и эффективно :)

← →
DeadMeat © (2005-03-10 12:03) [11]

Вот поэтому я и взял готовую...
TimeTable..
Но разбираться там тяжко. Хотя по словам тех, кто делал тоже самое, среди остальных аналогов, она проще и лучше...

← →
palva © (2005-03-10 12:04) [12]

Вообще имеется такая Теория расписаний. По ней написаны книги. Обычно они там рассматривают задачи, когда что-нибудь надо оптимизировать. Можно, например, брать деньги с преподов, если их желание будет учтено. Тогда можно оптимизировать общее поступление денег.

← →
raidan © (2005-03-10 12:04) [13]

Классическая оптимизационная задача :)
Ну же, вспомним ТОПиУ (Теория Оптимального Планирования и Управления) :))))

← →
Тульский © (2005-03-10 12:09) [14]

Кстати, дядя Билли в детстве написал аналогичную программу, правда для своей школы.

← →
blackman © (2005-03-10 12:16) [15]

Система автоматического построения расписания учебных зянятий (алгоритм)
http://davidovsv.narod.ru/schedule/
Программа "1Я-Методист. Расписание занятий" предназначена для составления расписания занятий/сессии
http://www.kineshma.muh.ru/program.htm

← →
DiamondShark © (2005-03-10 12:17) [16]

> в шахматах есть четкий критерий - мат, значит молодец.
>
> Тут критерев много. Возможно нужно будет вводить многомерную
> дискретную функцию и ее оптимизировать.

Тут критерий тот же самый, только наоборот.
Если после вывешивания расписания мата нет, значит молодец.

← →
Ega23 © (2005-03-10 12:18) [17]

Одна из задач линейного программирования. Аналогична задаче раскройки. Сиплекс-метод поможет.

← →
matt © (2005-03-10 12:20) [18]

эта задача решается на основе теории исследования операций. (кажется она так называется)
в нашем вузе решена в 91 что ли году...

конкретный раздел теории - "динамическое программирование" на англицоком - "Dinamik optimization"...

← →
КаПиБаРа © (2005-03-10 12:22) [19]

ex080D:07BBh (10.03.05 11:49) [8]
Думаю что нужно ввести целевую фукцию и оптимизировать (искать минимум) ее с учитетом ограничений.

Именно так устроены программы по оптимальной загрузке блоков станций.

← →
Vlad Oshin © (2005-03-10 12:23) [20]

> Если после вывешивания расписания мата нет, значит молодец.

:)

неужели так все сложно?
надо будет занятся...
и деньги дать могут?

← →
matt © (2005-03-10 12:25) [21]

Vlad Oshin © (10.03.05 12:23) [20]
ага причем любой вуз..
в Нац. авиацонном расписание составляют 40 человек.
в нашем - 1 женщина.

← →
Жук Андрій (2005-03-10 12:27) [22]

Занимались. Мой друган курсовую по этому поводу писал. На этапе внедрения остановилось - не все преподы заполнили заявки (ну, типа в понедельник хочу до обеда, в среду - после обеда, а в субботу - выходной). Потом умер замдекана, который это дело продвигал, так что сделали большую доску, набили кучу гвоздиков и цепляют туда листочки.

Какая оптимизация? Это раскраска графов. А не решается оттого, что (1) есть только эвристические алгоритмы, которые не обязаны давать оптимальное решение (2) есть куча требований в каждом конкретном ВУЗе и у каждого конкретного преподавателя

сетевой график строй

← →
Inventor (2005-03-10 13:48) [25]

Это всё понятно, про теорию расписаний знаю.
теория это теория, но с чего начать практику.

ввод исходных данных (справочники УЧЕБНЫЕ ГРУППЫ, УЧЕБНЫЙ ПЛАН, СПЕЦИАЛЬНОСТИ, АУДИТОРИИ, ПРЕПОДАВАТЕЛИ и т.д.) в программе реализован, данные хранятся в IB...
всё что касаеться работы с базой данных отлажено и функционирует, но С ЧЕГО начать писать алгоритм?

2 месяца поиска литературы и учебников в сети, указанные выше ссылки уже видел...

> но С ЧЕГО начать писать алгоритм?

с пива :)

ЗЫ. А если честно - то с изучения того, что накопано. Потом надо будет записать формулировку задачи в терминах того алгоритма, который тобой выбран. Что на входе, что на выходе. Описать алгоритм решения. Разбить задачу на много маленьких. А там, глядишь, все само устаканится.

>
> с пива :)

преподу по системному анализу и исследованию операций

← →
Inventor (2005-03-10 14:40) [28]

ЭТО Н-Е-В-О-З-М-О-Ж-Н-О!!!

← →
aus (2005-03-10 19:44) [31]

Посмотреть в сторону Пролога.
Весьма полезная может оказаться вештчь!

Алгоритм составления расписания занятий в ВУЗЕ Найти похожие ветки