RiBbiT

As a volunteer Math and English teacher in rural Namibia, Patrick quickly found a problem that could benefit from a computerized solution. School timetables are massive grids that indicate for each period of every school day, which teacher teaches which subject to which group of students.

Making a school timetable is hard. As you write down the combinations of teachers, subjects and students, you’ve got to make sure teachers aren’t scheduled to be in two places at once, that students receive proper number of lessons for each subject each week, that the same subject isn’t offered to a group of students more than once a day (except when double-periods are required, which should be consecutive). You’ve also got to martial limited resources carefully. For example, if every physical science class must take place in the Science Lab, then you’ll only be able to have one physical science class being taught at any given time. These are the most popular constraints, but each school has it’s own unique circumstances as well.

Around the world, well-funded school districts pay over US$100,000 for computer systems that automate the creation of the school timetable. But for schools in Namibia that can’t afford it (most of them), the responsibility to create the timetable falls to a “lucky” teacher or two at each school who must tackle it by hand, pencil, several erasers, and a really big piece of paper.

Patrick realized this problem is ripe for an open-source computer-based solution. He surveyed the freely available options and tested a few, but none were able to provide repeatable success. So, he dug in and created RiBiT, a command-line program written in C that can be used to generate school timetables.

You enter the teachers, the groups of students and subjects to be taught. You define which teachers will teach which subjects to which groups of students, and you can also define additional requirements. When it’s complete, you can print out schedules for each teacher and student group.

RiBbiT is extensible for programmers–you can define your own constraints as compiled libraries that are included by way of runtime configuration.

RiBbiT is named after the algorithm it uses to find solutions–a Recursive BackTracking algorithm. Because it uses this algorithm, it’s able to guarantee that it’ll find every possible timetable that can meet the provided requirements.

Frog image (“Hylomantis lemur – Lemur leaf frog”) created by Brian Gratwicke and licensed under Creative Commons – Attribution 2.0 Generic. Modifications by Patrick Cronin. Use of image does not imply endorsement of this site’s content.