Алгоритм создания школьного расписания - PullRequest
84 голосов
/ 01 февраля 2010

Мне было интересно, есть ли известные решения для алгоритма создания школьного расписания. По сути, речь идет об оптимизации «дисперсии по часам» (как в случае учителей, так и в классе) для конкретных ассоциаций класс-предмет-учитель. Мы можем предположить, что у нас есть наборы классов, предметов уроков и учителей, связанных друг с другом на входе, и что расписание должно соответствовать между 8:00 и 16:00.

Я думаю, что, вероятно, нет точного алгоритма для этого, но, возможно, кто-то знает хорошее приближение или подсказки для его разработки.

Ответы [ 16 ]

2 голосов
/ 04 мая 2010

В этой статье описана проблема школьного расписания и подход к алгоритму: « Разработка SYLLABUS - интерактивного планировщика на основе ограничений для школ и колледжей. » [PDF]

Автор сообщает мне, что программное обеспечение SYLLABUS все еще используется / разрабатывается здесь: http://www.scientia.com/uk/

2 голосов
/ 06 февраля 2010

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

1 голос
/ 04 мая 2012

Вы можете сделать это с помощью генетических алгоритмов, да. Но вы не должны :). Это может быть слишком медленно, а настройка параметров может занимать слишком много времени и т. Д.

Есть и другие успешные подходы. Все реализовано в проектах с открытым исходным кодом:

  • Подход, основанный на ограничениях
    • Реализовано в UniTime (не для школ)
    • Вы также можете пойти дальше и использовать целочисленное программирование. Успешно сделано в Университете Удине , а также в Университете Байройта (я принимал там участие) с использованием коммерческого программного обеспечения (ILOG CPLEX)
    • Подход, основанный на правилах, с использованием эвристика
  • Различные эвристики - FET и мои собственные

См. Здесь список программ учета времени

1 голос
/ 01 февраля 2010

Как правило, программирование с ограничениями является хорошим подходом к решению задач такого типа. Поиск по «программированию ограничений» и календарному планированию или «календарному планированию на основе ограничений» как в переполнении стека, так и в Google даст хорошие ссылки Это не невозможно - просто немного сложно подумать при использовании традиционных методов оптимизации, таких как линейная или целочисленная оптимизация. Одним из выводов будет - существует ли график, который удовлетворяет всем требованиям? Это само по себе, очевидно, полезно.

Удачи!

0 голосов
/ 09 апреля 2015

Я не знаю, кто-нибудь согласится с этим кодом, но я разработал этот код с помощью своего собственного алгоритма и работаю для меня в ruby. Надеюсь, это поможет тем, кто его ищет в следующем коде periodflag, dayflag subjectflag и teacherflag - это хэш с соответствующим идентификатором и значением флага, которое является логическим. Любая проблема, свяжитесь со мной ....... (-_-)

periodflag.each do | k2, v2 |

            if(TimetableDefinition.find(k2).period.to_i != 0)
                subjectflag.each do |k3,v3|
                    if (v3 == 0)
                        if(getflag_period(periodflag,k2))
                            @teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id)
                            @teacherlists=Employee.find(@teachers)
                            teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle] 
                            teacherflag.each do |k4,v4|
                                if(v4 == 0)
                                    if(getflag_subject(subjectflag,k3))
                                        subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3)
                                        if subjectperiod.blank?
                                            issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3)
                                            if issubjectpresent.blank?
                                                isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4)
                                                if isteacherpresent.blank?
                                                    @finaltt=TimetableAssign.new
                                                    @finaltt.timetable_struct_id=@timetable_struct.id
                                                    @finaltt.employee_id=k4
                                                    @finaltt.section_id=section.id
                                                    @finaltt.standard_id=standard.id
                                                    @finaltt.division_id=division.id
                                                    @finaltt.subject_id=k3
                                                    @finaltt.timetable_definition_id=k2
                                                    @finaltt.timetable_day_id=k1
                                                    set_school_id(@finaltt,current_user)
                                                    if(@finaltt.save)

                                                        setflag_sub(subjectflag,k3,1)
                                                        setflag_period(periodflag,k2,1)
                                                        setflag_teacher(teacherflag,k4,1)
                                                    end
                                                end
                                            else
                                                @subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3)
                                                @finaltt=TimetableAssign.new
                                                @finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
                                                @finaltt.employee_id=@subjectdetail.employee_id
                                                @finaltt.section_id=section.id
                                                @finaltt.standard_id=standard.id
                                                @finaltt.division_id=division.id
                                                @finaltt.subject_id=@subjectdetail.subject_id
                                                @finaltt.timetable_definition_id=k2
                                                @finaltt.timetable_day_id=k1
                                                set_school_id(@finaltt,current_user)
                                                if(@finaltt.save)

                                                    setflag_sub(subjectflag,k3,1)
                                                    setflag_period(periodflag,k2,1)
                                                    setflag_teacher(teacherflag,k4,1)
                                                end
                                            end
                                        end
                                    end
                                end
                            end
                        end
                    end
                end
            end
        end
0 голосов
/ 04 января 2011

Я думаю, вы должны использовать генетический алгоритм, потому что:

Также взгляните на: аналогичный вопрос и еще один

...