OberonCore

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



В новостях на 1 сентября говорили о 58 тысячах школ.



Совершенно бесспорно.



Кстати, это серьёзный аргумент. Расписание, работающее под Линуксом, да в свете перевода школ на Линукс к 2009 году - это хорошая зацепка.



Я имел в виду полноценную информационную систему, модулем которой является Расписание. Сейчас во многих школах уже есть базы данных по предметам, по контингенту - заводить их по-новой для составления расписания очень неудобно, хотя этот вопрос решаемый либо экспортом, либо подключением к уже существующей системе.

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

Ага. И все из них сейчас подключены к интернету. И сейчас в них в огромных объемах закачиваются гос. средства, в том числе и на компьютеное оборудование. А процентов 80% из них (и это еще оптимистическая оценка) просто не знают что с этим всем делать.

Да даже заново завести их -- дел на 1 день, ну максимум на неделю.

Своевременное напоминание.
А то народ все посложнее хочет -- силы некуда девать... эх...

Последний раз когда я видел, была спец. программка, кажется, досовская -- просто работала. Управляла ею препод. математики (диспетчеров в школе не бывает).

Ну вот, раз программа досовская, то в ней заведомо нет экспорта в html.
И если программа в ББ будет решать те же задачи, что и эта программа, плюс html-экспорт, тогда расписание можно будет вывешивать на сайте.
Не говоря уже о том, насколько лучше можно сделать пользовательский интерфейс.

Если речь идет об этом (http://troitskliceum.narod.ru/) лицее, то можно считать, что одна потенциальная установка уже есть

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

1) Составляло первую прикидку над которой должен был работать человек

2) Требовало корректировки процесса.

И то и другое плохо. А программ которые решают все проблемы по моему просто нет.

Все совсем наоборот. Собственно, полностью автоматическое решение задачи невозможно, да и не очень нужно. Главное, это автоматизированное (а не автоматическое) рабочее место для составления расписания и решения сопутствующих задач: выполнение нагрузки, основное расписание и текущее расписание с учетом разных замен и пр.

На мой взгляд, основные части системы такие должны быть:
1) "Рабочий стол" для распределения заранее заданной нагрузки (т.е. назначение занятий). Основное требование -- тщательно проработанный интерфейс, а этого довольно трудно добиться, скорее всего придется сделать вариантов 5-10, из которых останется только один.
2) Генератор отчетов. Основные требования: а) презентабельность и практичность печатных форм, б) экспорт в ХТМЛ для размещения на сайте школы.
3) Собственно модуль решения задачи автоматического составления расписания. По большому счету, без этого модуля можно обойтись на первых порах. Ну или сделать просто заглушку, которая будет тупо перебирать варианты. Я по крайней мере просто не представляю пока, с какой стороны к решению этой задачи подобраться -- может быть какие-нибудь генетические алгоритмы использовать, а может что-то из методов ядерной физики пригодится?

А вообще я рад, что задача вызвала интерес (больше всего меня беспокоило отношение info21).
Так что я попробую на след. неделе сделать более подробную постановку задачи, хотя и для меня это трудно довольно таки будет -- на самом деле я к школам практически никакого отношения не имею и не знаю, что им нужно на самом деле Поэтому мне было бы очень интересно узнать мнения тех, кто к школам имеет прямое отношение.

IMHO, это обычная задача раскраски графа (хорошая матмодель для составления расписаний, а также распределения регистров оптимизирующим компилятором):
http://en.wikipedia.org/wiki/Graph_coloring
В этой же вики-статье указано простейшее приличное "жадное" решение (IMHO) -- алгоритм Уэлша и Пауэлла. (NB предварительная сортировка вершин имеет значение.) По крайней мере, на роль заглушки вполне сгодится (реализация алгоритма -- всего несколько строк; я его использовал для распределения регистров в компиляторе Си).
Этот же простой алгоритм используется и здесь:
http://rain.ifmo.ru/cat/view.php/vis/gr ... ing-2002-1

В качестве лирического отступления
http://ru.wikipedia.org/wiki/Генетический_алгоритм
Это вам не рациональные числа. Те размножаются делением.

Почему?? (Пожалуйста, в личку, если не трудно.)

UPDATED
Убрал в личку

В науке мы как считаем: гипотез типа поменьше.
А тут важно "дорожку подмести".

Я увидел здесь транспортную задачу линейного программирования (хотя мог чего недоглядеть). "http://ru.wikipedia.org/wiki/Транспортная_задача"
Там по одну сторону - часы учебного плана (Аi), по другую - время преподавателей(Вj), в центре - "удобство" преподавателей и студентов (Cij).
Хотя надо подумать прокатит ли - очевидно что при решении надо уметь фиксировать часть расписания,
Если удастся впихнуть в эти рамки, то решать должно очень быстро.

Спасибо за помощь, но, честно говоря, сейчас просто нет времени анализировать, насколько применимы методы решения транспортной задачи к задаче составления расписание, да и не уверен, нужно ли это.
Я вот сейчас глянул мельком в yandex и google. Похоже, что задача составления расписания -- это одна из классических задач (как транспортная задача, задача коммивояжера и т.п., еще часто звучит понятие NP-полноты, но я в теории алгоритмов не очень ориентируюсь), и для нее давно разработана теория решения.

Вот некоторые ссылки, что мне понравились:

ЗАДАЧА СОСТАВЛЕНИЯ ШКОЛЬНОГО РАСПИСАНИЯ
http://www.mnogosmenka.ru/pilikov/school.htm
там в конце есть подборка уже существующего софта.

School timetable
http://en.wikipedia.org/wiki/School_timetable
В конце тоже много полезных ссылок, но все на английском.

GPL software для решения задачи расписания. Заявлена поддержка Linux и Windows
http://www.tablix.org/
Т.е. похоже, что можно не изобретать велосипед, а использовать готовое решение (ну по крайней мере для начала).
---
Анализировать сейчас существующие наработки у меня просто нет времени, попробую этим заняться в субботу.

А вообще хочу подчеркнуть еще раз, что главное -- это не программа автоматического составления расписания, а автоматизированное рабочее место диспетчера, т.е. тщательность проработки интерфейса намного важнее, чем алгоритм автоматического составления расписания. Т.е. программа должна быть инструментом в руках диспетчера, а на диспетчер -- инструментом ввода данных для программы.