Расписание

[dr.Faust]

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

... у каждого учителя есть определенная нагрузка в часах в неделю в некоторых классах. Само рассписание представляет собой таблицу, где строки - уроки с 1 по 8 в две смены сгруппированые по сменам, столбцы - классы школы (1А, 1Б и т.д.). Задача в том, чтобы расставить учителей так, чтоб в классах не было пустых уроков(окон), а учителя не ставились одновременно в два класса. Кроме того, учителя бывают не всегда вести уроки, например совмещающие две школы, студенты-практиканты(многие учатся в вузе и работаю в школе), учител ьне может приехать к первому уроку, т.к. живет далеко и  первый автобус приходит позже, т.е. не все учителя могут работать в любой урок, и.т.д.Также учителям желательно ставить уроки без "окон", или наоборот с "окнами" и др. условия для сортировки. Учителя еще мгут быть привязаны к спецкабинету, т.е. учитывать надо еще и нагрузку по кабинетам...

Вот ссылка в тему
http://zdd.1september.ru/2006/08/5.htm

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

Размышляя над задачей, я поговорил с несколькими знакомыми преподавателями (правда гуманитариями, ну да ладно) - мнение одно - если бы такая система существовала, это был бы мегапрорыв, но к несчастью создать её невозможно.
Я не занимался поисками специального ПО но думаю, что оно есть, хотя и стоить может немало.
Возможно кто-то знает такое ПО?

Про общее решение:
Я не силён в математике, но возмжно есть какая-то алгебра для лёгкого решения таких задач.
Например представляется интересным алгебра n мерных графов (боюсь, что её нет), где одно ребро соединяло бы сразу n точек и могло бы пресдтавлять урок, т.к. урок это комбинация времени, преподавателя, кабинета и группы.
Вообще вижу 2 пути - расставлять уроки в таблице и удалять их из неё. Второй путь мне представляется более интересным.
Вижу его так:
Все занятия рассматривать как комплексные (предмет, преподаватель), для того, чтобы уйти от классов преподавателей и оперировать уникальными занятиями.
Разделим все требования к урокам на 3,5 класса:
1 Безусловные требования - те которые не зависят от положения других занятий в таблице (География не может быть первым уроком, т.к. преподаватель приезжает только к 10:00, Биология не может начинаться в 15:00 так как преподаватель ходит домой кормить грудничка и т.д.)
2 Условные требования - те которые не зависят от положения других занятий в таблице (Биология не может идти одновременно с Химией, потому, что идут в одном кабинете, Физкультура не может идти одновременно с Литературой, потому, что у них один преподаватель, История не может идти одновременно с Историей и т.п.)
3 Безусловные пожелания - то что не очень обязательно, но крайне желательно (физкультура не должна быть последним уроком, а алгебра первым, а вот литература очень желательно первым, а все остальные позиции нежелательны)
3,5  Условные пожелания (Преподаватель А хочет иметь одно окно, а преподаватель Б хочет только сплошняком, а физику нельзя ставить после физкультуры и т.п.)

Алгоритм:
Возьмём таблицу Группа*Время.
Расставим все занятия в таблицу руководствуясь правилам 1 и игнорируя все остальные. При этом в одной ячейке получим несколько занятий.
Руководствуясь правилом 3 присвоим каждому занятию степень нежелательности.
1 Отберём 2 группы занятий с максимальным (наихудшая группа) и минимальным (наилучшая группа) весом и таких, что не единственные в данной позиции. Если все имеют один вес в каждую группу отберём все занятия.
2 На основании правила 3,5 увеличим степень нежелательности каждого попарно учитвая только пары где оба занятия из разных групп (наихудшей и наилучшей).
3 Отберём из этих групп 2 новые — из группы с минимальными весами наилучшую, из группы с максимальными — наихудшую.
4 На основании правила два выявим конфликты в парах занятий учитывая только пары где занятия из разных групп и удалим в конфликтующих парах занятия с максимальным весом.
Будем продолжать в том же порядке.
При этом, если на последнем шаге (4) не будет выявлено ни оного конфликта будем просто удалять все занятия вошедшие в наихудшую группу.
Прервёмся если на шаге 1 не удастся отобрать ни одного занятия (все единственные). Из получившейся таблице составим все возможные таблицы такие где в каждой позиции только одно занятие.

Как-то так.

[VlhOwn]

Саш, сформулированная задача вполне тянет на дипломную работу студента мехмата, специализирующегося по кафедре "Методы оптимизации и исследование операций". Собственно, нечто похожее писала в качестве дипломной работы моя жена. Для этого существует целый раздел математики, так и называющийся - "Теория расписаний".
Ключевые слова: методы оптимизации, целочисленное программирование, потоки в сетях.

[convas]

Есть море теоретических работ по Теории расписаний.
И одна практическая, которая заглохла на корню:
http://davidovsv.narod.ru/schedule/

[AcetonKZ]

Из дома дам ссылку на коммерческий составитель расписаний, такой софт уже есть ,но стоит денег, надо сделать в GNU варианте

2convas: спасибо, по ссылке ценная информация!

Почему в личку - не знаю.

Может это элементарно , а я такую фигню спрашиваю
Не думал, просто ,что будет интересно многим, поэтому пока кроме идеи ничего нет, то и писал Вам в личку!


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

[dr.Faust]

Я же говорил - приготовьтесь - будет сложно.
Задача явно крайне не простая. Например для описания правил придётся выдумать целый язык их описания.

Но ведь хотя бы что-то можно сделать...

[dr.Faust]

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

Не очень он удобен, или интерфейс должен быть самодельным или надо часть задачи выносить в calc.
Вобщем я думаю Calc+Base+Basic (не думаю что задача настолько сложна вычислительно что потребуется прикручивать, что-то другое - сложность скорее логическая).
В качестве оценки расписание можно ввести итоговый вес расписания.
Продолжая утверждать, что преподы неважны - они только отношения на множестве задач.

[prof-alex]

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

[dr.Faust]

Мегапрорыв в работе наших завучей конечно.

[AcetonKZ]

Вот ссылка, как и обещал, на готовый софт

http://www.softk.kz/catalog/program.php?ID=3126&CID=551&progdesc=long

[convas]

Никому не нужно:

Дата выпуска:     16.09.2001
Просмотров:    199
Загрузок:    14

[dr.Faust]

Никому не нужно

http://www.narod.ru/guestbook/?owner=608925&mainhtml=GuestBook.htm&messageshtml=GuestBookMsg.htm
Да...

Все хотят, но никому не нужно - здесь что-то не так...

[dr.Faust]

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

Я открываю программу для составления расписания и что вижу? Расписание? Ага - сейчас! Я вижу какое-то поле в клеточку и кучу непонятных кнопок. Неужели кто-то подумал, что вместо того, что бы начать составлять расписание я буду читать справку? Я похож на кретина читающего инструкции? Оставим это дело проффесианалам (ну это те которые не только знают как правильно работать, но и учат этому остальных, а до объективной реальности им дела нет), а мне нужно расписание и я составлю его быстрее чем прочту справку и разберусь какая кнопка что значит.
Программа может быть сколь угодно сложной внутри, но обязана быть примитивной снаружи - в идеале с одной кнопкой "Сделать Хорошо".
Ну как Inkscape, ну вы поняли.

[prof-alex]

Программа может быть сколь угодно сложной внутри, но обязана быть примитивной снаружи - в идеале с одной кнопкой "Сделать Хорошо".

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

[dr.Faust]

где тут прилепить кнопочку "Сделать Хорошо"?

Желательно по центру.
Я отдаю себе отчёт в сложности задачи, однако открыв программу я должен увидеть календарь с расписанием и сразу же мочь что-то сделать. Конечно дальше мне придётся выполнить колоссальную работу по настройке, но всё это должно изменять уже существующие решение.
А если я его не могу увидеть как пример ещё до того как я начал его состалять где гарантия что продолбавшись 2-3 дня я получу то, что хочу?

[AcetonKZ]

Цена (НДС включен)
Для одной школы. 1-3 лицензии.       14 695.38 тг. (за 1 лицензию)
Для дистрибютеров. 5-9 школ.       за 4 лицензии: 58 781.51 тг.
дополнительно за 1 лицензию свыше 4: + 12 246.15 тг.
Для дистрибютеров. 10 и более школ.       за 9 лицензий: 120 012.25 тг.
дополнительно за 1 лицензию свыше 9: + 9 796.92 тг.

делим на 147 и получаем в доларах
ответ на

Никому не нужно:

Учитывая зарплату завуча в 50-60 тысяч тенге и то, что купить за бюджетные средства не одобренный "с верху" софт получаем более чем исчерпывающее подтверждение того, что учителя долго мучаются от не состыковок расписания!

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

По поводу устройства проги и интерфейса согласен с др. Фауст