Are there any algorithms for resource scheduling of courses-teachers-classes

algorithmsresources

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.

Best Answer

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
Related Topic