Расписание

Автор dr.Faust, 5 ноября 2010, 11:42

0 Пользователи и 1 гость просматривают эту тему.

dr.Faust

Некоторое время назад ко мне обратился пользователь AcetonKZ за советом, какие компоненты ООо можно использовать для автоматизации составления школьного расписания. Почему в личку - не знаю. Но испросив у него разрешение я открываю эту тему. Для начала несколько цитат (приготовьтесь - сейчас будет сложно):
Цитата: AcetonKZ от 28 октября 2010, 21:05
... у каждого учителя есть определенная нагрузка в часах в неделю в некоторых классах. Само рассписание представляет собой таблицу, где строки - уроки с 1 по 8 в две смены сгруппированые по сменам, столбцы - классы школы (1А, 1Б и т.д.). Задача в том, чтобы расставить учителей так, чтоб в классах не было пустых уроков(окон), а учителя не ставились одновременно в два класса. Кроме того, учителя бывают не всегда вести уроки, например совмещающие две школы, студенты-практиканты(многие учатся в вузе и работаю в школе), учител ьне может приехать к первому уроку, т.к. живет далеко и  первый автобус приходит позже, т.е. не все учителя могут работать в любой урок, и.т.д.Также учителям желательно ставить уроки без "окон", или наоборот с "окнами" и др. условия для сортировки. Учителя еще мгут быть привязаны к спецкабинету, т.е. учитывать надо еще и нагрузку по кабинетам...
Цитата: AcetonKZ от 28 октября 2010, 21:31
Вот ссылка в тему
http://zdd.1september.ru/2006/08/5.htm
Цитата: AcetonKZ от 29 октября 2010, 09:15
... нюансов валом, главное правильно задать данные, правильные таблицы без дублирования данных, алгоритм пока тоже не вывел, то как это делают в ручную подавляющее большинство завучей конечно для программы не подходит. Так что есть желание помочь завучам(и педагогам, страдающим от не состыковок и утрясок расписания) которое и собираюсь реализовать на практике, возможно, не без ваших советов, т.к., честно, хоть ООо пользую давно, но такого рода задачи я не решал. Раньше подобное я на дельфях делал ,но они уже не столь универсальны, как этого хотелосьбы,  да и с килексом под линукс тоже дела из рук вон как плохо, т.ч. на ООо думаю будет самое оно!!!
Размышляя над задачей, я поговорил с несколькими знакомыми преподавателями (правда гуманитариями, ну да ладно) - мнение одно - если бы такая система существовала, это был бы мегапрорыв, но к несчастью создать её невозможно.
Я не занимался поисками специального ПО но думаю, что оно есть, хотя и стоить может немало.
Возможно кто-то знает такое ПО?

Про общее решение:
Я не силён в математике, но возмжно есть какая-то алгебра для лёгкого решения таких задач.
Например представляется интересным алгебра 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

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

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

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

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


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


dr.Faust

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

Но ведь хотя бы что-то можно сделать...
Свобода информации - свобода личности!

dr.Faust

Цитата: AcetonKZ от  5 ноября 2010, 11:02Думаю , что плясать надо от бэйза начинать, ибо табличность данных налицо и обработка этих данных и создание отчетов(самого этого расписания ) там до кучи!
Не очень он удобен, или интерфейс должен быть самодельным или надо часть задачи выносить в calc.
Вобщем я думаю Calc+Base+Basic (не думаю что задача настолько сложна вычислительно что потребуется прикручивать, что-то другое - сложность скорее логическая).
В качестве оценки расписание можно ввести итоговый вес расписания.
Продолжая утверждать, что преподы неважны - они только отношения на множестве задач.
Свобода информации - свобода личности!

prof-alex

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

«Студентов, ранее изучавших Бейсик, практически невозможно обучить хорошему программированию. Как потенциальные программисты они подверглись необратимой умственной деградации» Э. Дейкстра

dr.Faust

Мегапрорыв в работе наших завучей конечно.
Свобода информации - свобода личности!

AcetonKZ


convas

Никому не нужно:
ЦитироватьДата выпуска:     16.09.2001
Просмотров:    199
Загрузок:    14

dr.Faust

Цитата: convas от  5 ноября 2010, 20:27Никому не нужно
http://www.narod.ru/guestbook/?owner=608925&mainhtml=GuestBook.htm&messageshtml=GuestBookMsg.htm
Да...

Все хотят, но никому не нужно - здесь что-то не так...
Свобода информации - свобода личности!

dr.Faust

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

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

prof-alex

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

«Студентов, ранее изучавших Бейсик, практически невозможно обучить хорошему программированию. Как потенциальные программисты они подверглись необратимой умственной деградации» Э. Дейкстра

dr.Faust

#13
Цитата: prof-alex от  5 ноября 2010, 23:10где тут прилепить кнопочку "Сделать Хорошо"?
Желательно по центру.
Я отдаю себе отчёт в сложности задачи, однако открыв программу я должен увидеть календарь с расписанием и сразу же мочь что-то сделать. Конечно дальше мне придётся выполнить колоссальную работу по настройке, но всё это должно изменять уже существующие решение.
А если я его не могу увидеть как пример ещё до того как я начал его состалять где гарантия что продолбавшись 2-3 дня я получу то, что хочу?
Свобода информации - свобода личности!

AcetonKZ

#14
ЦитироватьЦена (НДС включен)
Для одной школы. 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 тысяч тенге и то, что купить за бюджетные средства не одобренный "с верху" софт получаем более чем исчерпывающее подтверждение того, что учителя долго мучаются от не состыковок расписания!

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

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