Составитель расписаний(автоматический)

← →
SarDoX (2005-11-04 10:03) [0]

я решил я все таки написать составитель расписаний.
но всю сложность работы понял тока спустя неделю работы. перечислю сложности:
а) у нас в лицее 7-11 классы, по 3 класса на параллеле, итого 15 классов.
б) надо учитывать
1)один учитель в один день не может вести урок у двух классов одновремеенно(так же некоторый учителя могут вести уроки как у одной параллели, так и у другой)
2)некоторые уроки должный быть парами, некторые нет
3)не должно быть дней, когда в расписании 2 физики, 2 алгебры, 2 русский, т.е. тяжелых дней(тут я решил ввести коэф сложности для каждого предмета)
4)одиночный уроки, такие как черчение, химия, геометрия и т.д
у одной параллели должны быть в один день
это далеко не весь список, чем дальше, тем хуже...
2 раза переписывал весь код.
решил было сделать генератором. получилось составлять расписание на неделю для одого класса с учетом парный - непарных предметов, учитывается кол-во предметов в неделю, например, если в неделе одно черчение, то оно должно быть только одно.
но позже понял, что если добавить еще 2 класса в параллели, то с генератором далеко не уедешь.. а если учесть, что потом бы пришлось добавлять 4 параллели..
в общем хотелось бы узнать, каким образо можно было бы это все осуществить, как правильно организовать программу. спрашиваю не потому, что нужно халява, а потому, что уже действительно не знаю, каким образом.
а начинать другую работу очень не хочется, хочется эту добить, сделать.

← →
msguns © (2005-11-04 13:48) [1]

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

Потом график учителей (персонально) с плановым кол-вом часов, набором предметов, "вилкой" дневной почасовой занятости и т.д.

И вот только потом "накладывать" учителей на уроки. Опять же в ручном режиме, но с программной подсказкой. И тоекущим контролем по всем трем параметрам (предметы+ученики+преподаватели)

← →
PAVIA © (2005-11-04 21:53) [2]

1. Подход.
Так как много огранечений, то можно попробовать с учетом этих огранечений сделать перебор.
2. Подумать как бы ты делал буть ты Заучем. И на основе этого делать программу.
Совсем подобную человеку составить не получиться, но выбрать оптимальные варианты возможно. Такие задачи только так и решаются.

← →
OpenSource (2005-11-04 22:18) [3]

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

← →
SarDoX (2005-11-08 07:21) [4]

значит так. занялся все же я этим и дальше.
программа успешно составляла действительно хорошее расписание с учетом многих факторов на неделю для одного класса.
если добавить еще параллель или несколько классов, то усложится программа не особо.
но появилась трудность - мы не знаем сколько классов в параллели, сколько параллелей в школе всего.
затем, нам надо где то хранить расписание на каждый день для каждого класса(если классы 1-11 и по 3 класса в параллели, то всего классов 33!!! ) + учителя, ведущие данный предмет + кабинет урока.
но мы не знаем, сколько классов у той или иной школы, для которой генерируется расписание, поэтому хранить в массивах(кт надо указывать длину заранее..) вряд ли получится. хранить инфу в бд? бред, т.к при составлении расписания для одного класса, надо учитывать расписание другого, а работа с бд(постоянный многочиленный запросы в бд...) очень замедлит работу программы. хранение в stringlist ах или еще чем нить подобном - тоже плохой вариант, даже - невозможный..
сложная задачка, однако..
ужо подумываю над другой темой.:(
предлагали тестовую программу? не, это уж слишком просто будет..
библиотека? у нас уже есть такая в школе, писать "велосипед" не особо хочется.
кто то предлагал по расписанию выводить графики загруженности учеников и учителй - представьте скока времени надо завучу потратить на забивание всего школьного расписания в прогу(даже если облегчить этот процесс..)
и результат - мало нужный кому либо график...
жалЪко, что прийдется оставить прогу..
мож еще кто идейку подкинет?

← →
SarDoX (2005-11-08 07:23) [5]

идейку, тему программы...

← →
RzCoDer © (2005-11-08 07:37) [6]

IF...THEN...BEGIN...END ELSE BEGIN...END

← →
Anatoly Podgoretsky © (2005-11-08 08:46) [7]

SarDoX (04.11.05 10:03)
Ты еще не понял ее сложности

← →
SarDoX (2005-11-08 08:51) [8]

Anatoly Podgoretsky, возможно, спорить не буду; чем дальше я писал, тем больше сложностей появлялось.
но того, что я уже понял, мне достаточно: я уже знаю, что не справлюсь с этой работой.

у кого есть какая нить оригинальныя идейка проги для написания, имеющая практическое приминение и, желательно, не встречающаяся в нете.
(кулинарный справочник(работал с бд access), например, который я писал в прошлом году)

← →
SarDoX (2005-11-08 08:52) [9]

RzCoDer? это ты про что? или ты думаешь, что этим можно всю прогу написать?

← →
Sergey_Masloff (2005-11-08 09:21) [10]

SarDoX (08.11.05 07:21) [4]
> а работа с бд(постоянный многочиленный запросы в бд...) очень замедлит >работу программы.
Ерунда. Ничего не замедлит тем более расписание составляется не каждые 5 секунд. Храни в БД.
Если хоть что-то получается то не в коем случае не бросай это - конечно полнофункциональный автомат не получится но если сделаешь хороший полуавтомат это колоссальный полезный опыт.

← →
Calm © (2005-11-08 09:41) [11]

Разделяю мнение Sergey_Masloff

SarDoX, ты уже сделал не мало.

← →
Чапаев © (2005-11-08 09:46) [12]

> Автоматом подобное "человеческое" расписание составить невозможно.

Ну почему ж... Один мой экс-препод даже книжку написал о том, что можно. Только очень долго, потому что задача NP-полная.

Правда, он доктор технических наук, а не лицеист. ;-)

← →
SarDoX (2005-11-08 09:59) [13]

Sergey_Masloff, Calm ---
было бы замечательно по аси пообщаться.
для каждого урока нужно хранить: номер урока, само название урока + учитель.
уроков у одного класса в день 6, в неделю - 36, а у всех параллелей 11 * 6 * 6 = 396 уроков в неделю.
я не пойму, в чем хранить?
если вопрос не понятен, то:
возмем 9-10 классы.
некоторые учителя ведут уроки как у 9, так и у 10 классов(например, русский ).
вот я сгенерировал расписание для 9-х классов.
вот я сгенерировал расписание для 10А класса.
потом, когда я генерирую расписание для 10Б класса, мне уже надо учитывать расписание не только 10А , но и 9-х классов, т.е что б не получилось, что у одного учителя(здесь -учителя русского) в один час сразу два урока - у 9* и у 10Б класса.
т.е. мне надо проверить всю параллель 9-х классов, нет ли у какого нить из них 3-м уроком в понедельник русского языка . если нет, то я могу добавить 10Б в понед третьим уроком русский, else опять перегенирировать расписание.
это самое else встречается в алгоритме очень часто, т.е перебор будет очень большим(хотя меня это не волнует).
как мне все это хранить, где?
сейчас, когда прога генерили расисание для одного класса на всю недедлю, я храню так(переделывать прийдется точно.):
weak:array[1..6, 1..6] of string;
1-6 уроки
1-6 дни недели
мне пока не надо учитывать учителей, лишь что б одновременно уроко не было.
но куда мне добавить учителей? по идее надо к каждому уроку прописывать
3 урок / русский яз / анна викторовна
и, не торопитесь, нельзя забывать, что классов может быть 11*3=33!!! шт.
а создавать 33 массива бред.(да и мож в какой нить школе нет 4 класса..)
хранить в одной бд? гм. я не представляю как.
проблему объяснил, как смог, по-другому не смогу.

← →
SarDoX (2005-11-08 10:10) [14]

а если учесть, что одни и те же учителя(например, биология, химия, черчение) ведут уроки у 7,8,9,10,11...
продожить? или сами поняли, что прийдется перебирать все классы, начиная с 7 да 10В, что б добавить биологию в 11А:)

← →
Джо © (2005-11-08 13:44) [15]

Когда-то (давно) думал над подобной задачей. Додумался до того, что неплохо было бы придумать специальный мета-язык описания условий.

← →
Anatoly Podgoretsky © (2005-11-08 14:02) [16]

SarDoX (08.11.05 09:59) [13]
Хочешь еще одну проблему, на много порядков проще, чем остальные?
Ты видел реальное расписание? Это такая гигантская простыня, и как собираешься ее отображать на дисплее? Как этим будут пользоваться учителя, а ведь это предмет для постоянной смены, в течении часа может быть изменено несколько раз. Печатать каждый раз, а не жалко пустой траты бумаги. Или у каждого учителя есть компьютер и средство оповещения об изменении?

← →
NORDmen © (2005-11-08 14:03) [17]

2SarDoX :
я делал такую прогу все работало. могу даже исходники дать.
пишите на мыло.

← →
Jeer © (2005-11-08 14:09) [18]

NORDmen © (08.11.05 14:03) [17]
SarDoX (04.11.05 10:03)

Ребятишки !
Пока Вы не начнете с постановки задачи + необходимый мат.аппарат - это все будет "козьи потягушки".

Срочно за теорию.

← →
NORDmen © (2005-11-08 14:24) [19]

2jeer:
я вообще не въезжаю к чему этот бред. случайный генератор слов?

← →
Anatoly Podgoretsky © (2005-11-08 15:10) [20]

NORDmen © (08.11.05 14:24) [19]
Видимо не дано, попробуй еще раз внимательно прочитать, потом еще много раз подряд. Если не поможет, значит не судьба, но и не наша проблема.

← →
msguns © (2005-11-08 15:19) [21]

>NORDmen © (08.11.05 14:24) [19]
>я вообще не въезжаю к чему этот бред. случайный генератор слов?

В чем бред ? В том, что для подобной задачи 90% решения заложено в постановке задачи ?

← →
NORDmen © (2005-11-08 15:29) [22]

Удалено модератором
Примечание: МАТ и нападки на участников, отдохни три дня

← →
arhis (2005-11-08 15:40) [23]

msguns © (08.11.05 15:19) [21]
100% Постановка и является решением.

← →
Red_imp © (2005-11-08 16:46) [24]

Задача довольно интересная и непростая. Я кстати сейчас тоже занимаюсь составлением расписаний (не уроков) и у меня задача намного легче хотя могу попробовать и помочь. Есть чтото похоее с составлением графиков.

Сначала постарайся представить всю структуру сразу чтоб по ходу решения задачи не вылезали лишние задачки и проблемки. А на данном этапе попробуй начать с учителей а не с уроков. У каждого учителя есть определённое количество часов работы определённый предмет и день недели в который он выходной (может и не быть).
Хотя может это и неправильно.

← →
msguns © (2005-11-08 17:38) [25]

>Red_imp © (08.11.05 16:46) [24]
>А на данном этапе попробуй начать с учителей а не с уроков. У каждого учителя есть определённое количество часов работы определённый предмет и день недели в который он выходной (может и не быть).
Хотя может это и неправильно.

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

← →
red_imp © (2005-11-09 09:26) [26]

to msguns ©

Я конено согласен просто меньше условий обрабатывать: в день у учителя максимум 8 уроков а в неделю норма 18 часов. А вобще расписание составляется хотябы на четверть и помоему оно не меняется из-за неявки учителей. Хотя я просто я говорю что ИМХО лучше я специально не занимался составлением расписание уроков немного другая тема.

>red_imp © (09.11.05 09:26) [26]
>..в день у учителя максимум 8 уроков а в неделю норма 18 часов

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

навсякий случай, вдруг пригодится кому..
http://www.asctimetables.com/timetables_ru.html

← →
arhis (2005-11-09 15:49) [29]

> А ведь есть еще "экстрачасы", это когда либо на 1,5 ставки
> (дефицит учителей), либо подменяет коллегу. В этом деле
> вообще бардак, не поддающийся никакой "автоматизации". Завуч
> (директор) запросто может отнять "лишние" часы у одного
> учителя и отдать их другому. Вне всякого "графика".

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

Автору мой совет - бери другую тему.

arhis (09.11.05 15:49) [29]
Зачем, этого же до пенсии хватит.

← →
Zhekson (2005-11-09 16:14) [31]

Anatoly Podgoretsky © (08.11.05 15:10) [20]
мда, обидели человека... не стыдно??? или соблазн унизить перевесил???

Я тоже не сразу въехал, да и Вы не мгновенно это сделали... Могли ведь и опередить ;)))

to msguns ©

Да конечно тут все так сразу в уме учесть невозможно надо сначала только с бумажкой сидеть и все условия писать. Короче жуть полная.

to SarDoX

извините за офтоп
Ты вобще откуда??? из какого города?

← →
SarDoX (2005-11-10 05:50) [33]

г.Владивосток
10 класс.
ну значит что я надумал...
всю инфу хранить само собой в бд, в разных таблицах
для каждого учителя свою таблицу составить, 6*6(дни недели*уроки)
если у учителя есть урок, то в соотв. клетку ставить 1, если нет, то 0.
для каждой параллели составить таблицу-связку урок-учитель.
для каждого класса составить таблицу как для учителей, т.е. 6*6.
генерировать расписание каждому классу по очереди
основые условия

//среда-3урок
генерировать предмет
определить через связку учителя
проверить, нет ли у учителя предмета в текущ день, т.е в среду 3 уроком, если нет, то --- другие условия, усли их пройдет, то добавить предмет и в таблицу учителя поставить 1:) , если да, то начать сначала, т.е перегенерировать предмет.
седня примусь за осуществеление. бд и sql я знаю, тут пролем не будет.
--
а бросать тему это глупо, имхо.
--
автор знает, что он хочет сделать
--
учесть все в уме невозможно. я когда тему брал, вообще не предполагал, что будет стока проблем, чем дальше писал, тем дальше ужасался. но теперь, вроде бы, все в голове уложилось.

← →
SarDoX (2005-11-10 06:42) [34]

связок учитель-предмет будет стока же, скока и параллелей.

>бд и sql я знаю, тут пролем не будет.

как то противоречит ранее сказанному:

>всю инфу хранить само собой в бд, в разных таблицах
>для каждого учителя свою таблицу составить, 6*6(дни недели*уроки)
>если у учителя есть урок, то в соотв. клетку ставить 1, если нет, то 0.
>для каждой параллели составить таблицу-связку урок-учитель.
>для каждого класса составить таблицу как для учителей, т.е. 6*6.

← →
SarDoX (2005-11-10 12:43) [36]

не придирайтесь. я думал, что мне немного про другие таблицы говорили, типа dbgrid.
основной код программы я уже закончил :)

to SarDoX

Хотелось бы посмотреть на структуру БД

Составитель расписаний(автоматический) Найти похожие ветки