I'm developing an application to help school principals in dedicating teachers to classes and courses over the hours of a week (scheduling). The scenario is roughly something like this:

  1. User enters the list of teachers and their free times into the system
  2. User enters the list of courses for this semester
  3. User enters the list of available classes into the system

Well, up to here, there is no big deal. Just simple CRUD operations and nothing extraordinary. However, now what makes this system useful is that the application should automatically and based on an algorithm create the semester scheduling.

I think you've got the main idea here. For example application should suggest that teacher A should go to class 1 for mathematics, and at the same time teacher B should go to class 2 for physics. This way all of the classes would be dedicated to lessons and teacher times won't overlap each other. Piece a cake for school principal.

However, I can't find a good algorithm for this resource dedication. I mean it seems hard to me.

Searching Google resulted in articles from different websites, but they are of no help and use to me. For example:

http://en.wikipedia.org/wiki/Resource_allocation or http://en.wikipedia.org/wiki/Scheduling_(production_processes)

Is there any algorithm out there, or any application or engine which can help me here? Does this requirements have a known name, like for example time scheduling engine?

Any help would be appreciated.

  • 2
    This problem is called "timetabling". A working heuristic is described under www.lalescu.ro/liviu/fet/doc/en/generation-algorithm-description.html – frececroka Dec 4 '12 at 8:05
  • 4
    I think that may be a NP-complete problem see constraint programing – ratchet freak Dec 4 '12 at 8:08
  • @Lorenz, thanks for the name. That was a helpful clue. – Saeed Neamati Dec 4 '12 at 8:20
  • 2
    You can program an algorithm to produce some results. However, the challenge is to consider whether there is 1 or more solutions and the criteria to use to select the best solution. The other aspect you need to consider is that you may have certain constraints. For example, a senior teacher may work less hours than a junior one and/or consider the fact that a teacher has certain hours of class room work per day per educational level, and so on. This is not a simple problem. What you may be looking for is "A constraint-driven human resource scheduling method", using variety of "OR" algorithms. – NoChance Dec 4 '12 at 10:00
  • Take a look at ERP, if you substitute a 'Teacher' for a piece of 'Machinery', that has uptime, downtime, batch-runs, scheduled maintenance etc... OpenERP is opensource, and, I believe some of the modules may be adapted to your requirements. – ADP Dec 11 '12 at 4:49

I have seen a custom solution for this. Some of the major points:

  • There are different approaches to organizing the week, for example the order to actually start 'packing' events can vary. Approaches can include 'Monday first', 'AMs first', '2 day schedule', '6 day schedule', 'A/B schedule'.

  • Class size is not an absolute. It's best to have an 'ideal' size plus a minimum and maximum.

  • Teachers work different schedules. Some are part time. Some Districts count any hours worked in a given day as having worked a full day. Some count half-days this way and some count quarter days. So the solution tends to be specific to the district.

  • It's important to allow and build in some flexibility and 'wiggle-room'. Scheduling resources too 'tightly' leads to issues when the inevitable 'stuff' comes up such as teachers sick, kids sick, weather event days, etc.

  • Students enter and leave the district through the year. For some districts that can easily be 20% of their student body. Scheduling algorithms needs to allow for this factor also.

  • Special Education has a whole set of requirements including IEP, instruction alone, etc. Also the instructor travel between schools and so distance and travel time has to be incorporated for these services.

  • There are different roles to be considered including Teachers, Teacher Assistants, Aides, Translators etc.

  • People eat lunch :)

  • Teachers need time for Lesson Preparation, Meetings, and Discussions with Parents.

  • It is good to distinguish direct Service (actually seeing students) activities as compared to indirect activities.

At the higest level, given your requirements, I would imagine an algorithm for you would be:

For each Course
    For each available Teacher
        For each available Classroom
           Select the first Classroom available and book the resource.
           Update the course and teachers availability.
        end Classrooms
    end Teachers
end Courses

What limited experience I have had with finite domain constraint resolution has been with Mozart/Oz. There is a relatively good tutorial as part of the standard documentation: http://www.mozart-oz.org/documentation/fdt/index.html

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.