Автоматическое составление расписаний

← →
TimeTable (2005-12-25 22:46) [0]

Интересует сабж.
Какие могут возникнуть проблемы? Может у кого есть какие нароботки :) , ссылки по сабжу.
Вот кое-что нашел по этому поводу:
http://algolist.manual.ru/oldforum/viewtopic.php?t=666&postdays=0&postorder=asc&start=0

← →
Sergey Masloff (2005-12-25 22:59) [1]

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

← →
версия для печати (2005-12-25 23:47) [2]

Сорри если опять торможу, но какие могут быть трудности с написанием САБЖа?

← →
paul_k © (2005-12-26 09:37) [3]

Sergey Masloff (25.12.05 22:59) [1]
Еще один ;-)
(ну, пока искусственный интеллект не изобретут а до этого далеко)
Неужели все так грустно??
в чем засада? согласовать составленное с народом?

← →
seg (2005-12-26 09:41) [4]

Засада в том, что никто не хочет шевелить мозгами.

← →
paul_k © (2005-12-26 09:52) [5]

seg (26.12.05 9:41) [4]
Засада в том, что никто не хочет шевелить мозгами.

И все???
неужели?

← →
seg (2005-12-26 10:44) [6]

И все???
неужели?

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

← →
paul_k © (2005-12-26 10:51) [7]

seg (26.12.05 10:44) [6]
то есть составлять алгоритмы составления расписания дело руководства заведения? или его дело платить за это "не студентам"
или? сидеть над бамаськой и ручками парится? или?

← →
Чапаев © (2005-12-26 10:54) [8]

> в чем засада?

В том, что задача NP-полная...

← →
Ломброзо © (2005-12-26 10:57) [9]

Буквально на прошлой неделе читал где-то про решение подобной задачи на базе OLAP с кубом, включающем три десятка измерений. Интересно, с какой скоростью это всё работает.

← →
Чапаев © (2005-12-26 11:02) [10]

> с кубом, включающем три десятка измерений. Интересно, с
> какой скоростью это всё работает.

Не то страшно, что три десятка, а то страшно, что решается тупым перебором...

← →
TUser © (2005-12-26 11:12) [11]

> Сорри если опять торможу, но какие могут быть трудности
> с написанием САБЖа?

Трудности состоят в том, что задача (а) NP-полная и (б) в каждом конкретном случае может быть очень много обстоятельств, которые надо учесть - всего в программе предусмотреть не получается. Одному преподу надо группу разделить на половинки, другому не нравится аудитория номер 135, третьему принципиально необходимо две пары подряд.

← →
seg (2005-12-26 11:17) [12]

составления расписания дело руководства заведения?

Вот именно.
Иначе получается, что студенты сами себе составляют расписания.
Т.е. яйца курицу учат...

← →
msguns © (2005-12-26 11:45) [13]

>версия для печати (25.12.05 23:47) [2]
>Сорри если опять торможу, но какие могут быть трудности с написанием САБЖа?

Трудностей нет никаких. Ее просто нельзя написать. В смысле нельзя написать такую, которой бы реально пользовались.

← →
arhis (2005-12-26 11:50) [14]

seg (26.12.05 11:17) [12]

Наконец-то прозвучал голос разума во всей этой мыльной опере с расписаниями.

← →
paul_k © (2005-12-26 11:51) [15]

msguns © (26.12.05 11:45) [13]
В смысле нельзя написать такую, которой бы реально пользовались
можно разжевать это "для тупых"? пожалуйста.
Я вижу пока одно, уже упомянутое. Человеческий фактор вида

> Одному преподу надо группу разделить на половинки,
> другому не нравится аудитория номер 135, третьему
> принципиально необходимо две пары подряд.

Но это к расписанию занятий. А расписание электричек скажем, теже грабли?

← →
seg (2005-12-26 11:52) [16]

Ее просто нельзя написать.

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

← →
Ломброзо © (2005-12-26 11:53) [17]

>msguns © (26.12.05 11:45) [13]

Да ну. Я вот являюсь фанатичным пользователем MS Outlook начиная с Office 97, дык на тот аутлук с его календарём смотреть было стыдно, а сейчас его можно без ложной скромности назвать идеальным планировщиком, особенно в упряжке с MS Exchange и MS Project.

← →
arhis (2005-12-26 11:53) [18]

paul_k © (26.12.05 11:51) [15]

Вы уж определитесь расписание чего вам нужно.

← →
paul_k © (2005-12-26 11:56) [19]

arhis (26.12.05 11:53) [18]
а есть разница?
расписание загрузки станков, рсписание занятости аудиторий, расписание посещениея бани по отделам, и так далее.

← →
paul_k © (2005-12-26 11:57) [20]

расписание загрузки станков работниками имеется в виду

← →
Sergey13 © (2005-12-26 12:04) [21]

2[19] paul_k © (26.12.05 11:56)
>а есть разница?
Неужели нет?

← →
paul_k © (2005-12-26 12:17) [22]

← →
Sergey13 © (2005-12-26 12:20) [23]

2 [22] paul_k © (26.12.05 12:17)
>с точки зрения алгоритмизации процесса в чем разница?
Так в разных алгоритмах самих процессов. ИМХО.
Если все так просто - напиши и продавай. Богатства Била Гейтса не обещаю, но на хлеб с маслом хватит. ИМХО, опять же.

← →
seg (2005-12-26 12:27) [24]

с точки зрения алгоритмизации процесса в чем разница?

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

Какая раница между выпуском деталей и чтением лекций?
Судя по этому алгоритму - никакой.

← →
paul_k © (2005-12-26 12:41) [25]

Sergey13 © (26.12.05 12:20) [23]
Если все так просто - напиши и продавай
так и прошу разъяснить в чем сложность?

seg (26.12.05 12:27) [24]
Какая раница между выпуском деталей и чтением лекций?
между расписанием работы апреаодавателья с в аудитории X с группой N и выходом на работу к часу Х дабы исключить простой станка не вижу никакой разницы.
Вы, видимо, намекаете на разницу труда токаря петрова и лектора петрова. И какое это влияние оказывает на оптимальное заполнение сетки занятий лектора и сетки трудочасов токаря?

← →
Sergey13 © (2005-12-26 12:46) [26]

2[25] paul_k © (26.12.05 12:41)
>так и прошу разъяснить в чем сложность?
В неопределенности исходных данных. И большом количестве "случайных" факторов, кардинально влияющих на результат. Например препод может работать не только в одном месте и поэтому "в понедельник только с утра, а пятницу только после обеда".

← →
paul_k © (2005-12-26 13:04) [27]

Sergey13 © (26.12.05 12:46) [26]
то есть в множестве модификаторов влияющих на общее рабочее время.. то есть нада сначала ручками на каждой какедре рабочие дни преподавателей внести. Капризы разные учитывать типа вот в аудитории ХХХ я преподавать буду а в аудитории YYY мне доска не нравится.
и отсюда исходить так?
Вы упираете на сложность внедрения алгоритма хотя,
Чапаев © (26.12.05 10:54) [8]
В том, что задача NP-полная...
указывает на сложности составления самого алгоритма.

← →
seg (2005-12-26 13:09) [28]

Расписание работы станка может быть очень простым - круглосуточным.
График работы рабочих - в 3 смены.
Вот и все расписание.

в аудитории YYY мне доска не нравится.

в аудитории YYY может не быть наглядных пособий...

2[28] seg (26.12.05 13:09)
>Расписание работы станка может быть очень простым - круглосуточным.
Расписание работы станка нафик никому не нужно. Он железный. Включи и работай. Вот с людьми, которые на нем работают сложнее. 8-)

← →
seg (2005-12-26 14:06) [30]

Вот с людьми, которые на нем работают сложнее. 8-)

С людьми всегда сложнее, чем с техникой.

seg (26.12.05 13:09) [28]
угу. станка именно беспрерывно и бесперебойно.
но не работника петрова, у которого обед по расписанию:) и заменить его на час нада. чтоб станок не простаивал

Sergey13 © (26.12.05 13:35) [29]
от собственно и я про то же..
тока не понимаю, в чем сложности то заполнения сетки? так, кажется, ещё называют расписания? объясните дураку тупому, ПОЖАЛУЙСТА!!!

2[31] paul_k © (26.12.05 15:20)
В собственно механическом заполнении сетки проблем нет. Сложность в автоматизации расчета того, что в клеточки писАть. 8-)

← →
seg (2005-12-26 15:31) [33]

тока не понимаю, в чем сложности то заполнения сетки?

В данных, которые надо записывать в эту сетку.

seg (26.12.05 13:09) [28]
в аудитории YYY может не быть наглядных пособий...
да???? не может быть. ибо тогда это не аудитория а "лаборатория" или "спецаудитория" необходимость проведения занятия в "спецаудитории" свойство учебного плана, предмета чего угодно... Но, повторяю я пока вижу только одну сложность. Капризы (Или человеческий фактор, если хотите)
Преподаватель оплачивается исходя из почасовой нагрузки. Следовательно мечта каждого преподавателя отработать свои недельные часы подряд, делательно за минималное количество дней и в наиболее близкой к кафедре теплой аудитории. 20-3 дня отчитал и - свободен.
По факту - если один работает так то другой должен иметь кучу "окон".
понятно что в составлении расписания основная задача это "сбалансировать" эти желания. Выяснить кто "равнее" перед машиной и кому график ставить плотне а кому нет.
И решать это может только человек на основе совокупности знаний, которые полностью формализовать не представляется возможным.
Это понятно.
Но вот скажите а в чем сложность автоматизации заполнения сетки? Контроля "пересечений", дать юзеру возможность двигать занятия по расписанию (менять местами, сдвигать и так далее. естественно с подвижками или предупреждениями необходимыми). В чем тут сложность?
как правильно заметил Sergey Masloff (25.12.05 22:59) [1] в общем случае проблема ПОЛНОЙ автоматизации процесса не имеет решения именно за счет "человеческого фактора"
Но исходя из мнений Sergey13 © и seg] можно сделать ошибочный вывод, что вообще братся за этот процесс не стоит, ибо он не решаем, что, мягко говоря, не совсем верно.
при некоей идеализации задачи решение вполне существует. А притягивать идеал к реальной жизни уже задача юзера. Или скажете, что опять я не прав?

[34] paul_k © (26.12.05 15:35)
> А притягивать идеал к реальной жизни уже задача юзера. Или
> скажете, что опять я не прав?

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

← →
seg (2005-12-26 15:46) [36]

На самом деле задача настолько проста, что обычно ее решает завуч за час, используя только карандаш и бумагу.
Если что-то не нравится, то корректируется к следующему семестру.

2[34] paul_k © (26.12.05 15:35)
>Но исходя из мнений Sergey13 © и seg] можно сделать ошибочный вывод
И ты его сделал. 8-) Я нигде не говорил, что делать не надо. Ты "просил" трудностей - я их тебе пытался "давать".

Джо © (26.12.05 15:39) [35]
Угу.. А значит выглядеть она должна не сложнее привычной "бамаськи" и позволять при этом намного больше. не так ли?

> что обычно ее решает завуч за час

угу в сельской средней школе из 2-х трех учителей и стольких же классов.
Составление расписания (особенно школьного) - это недели склок дрязг и ругани.. тому на час больше выделили а почему не мне и так далее... Но это из серии "капризов".

Sergey13 © (26.12.05 15:46) [37]
Я гоыворил о завдаче составления идеального расписания. отсюда и аналогия с заводом. Ты указывал на трудности в автоматизации реального бардака, сопровождающего этот процесс.

2 [38] paul_k © (26.12.05 16:01)
> Я гоыворил о завдаче составления идеального расписания. отсюда и аналогия с заводом.
На заводе может быть идеальное расписание? Да ладно. В институте 100 преподов, а на заводе 10000 деталей и заморочек куда как больше.

Sergey13 © (26.12.05 16:07) [39]
но производствунный процесс более формален и менее зависит от "капризов". Сделай преподу 8-ми часовой рабочий день и ему пофих будет подряд пары или с "окном". И это маленькая часть разницы..
на предприятии есть технологический процесс, практически готовый алгоритм. в учебном заведении такой строгости нетути..

Автоматическое составление расписаний Найти похожие ветки