Show HN: Constraint-Based School Timetabling with Prolog | Hacker News Reader

Show HN: Constraint-Based School Timetabling with Prolog

metalevel.at

20 pointstriska4 comments

A few days ago, a commenter remarked that Prolog seems to be a good choice to solve combinatorial problems such as timetabling tasks.

That's indeed the case! Prolog is an excellent choice for modeling combinatorial problems, and it is routinely used in practice to solve scheduling tasks such as school timetabling.

To show this, I have set up a page where you can interactively solve school timetabling instances with Prolog, and I invite you to try a few instances:

https://www.metalevel.at/prolog/timetabling/

The Prolog source code of the timetabling engine is freely available from:

https://www.metalevel.at/simsttab/

Complementing the showcase, I have uploaded a short video that explains how it works:

https://www.metalevel.at/prolog/videos/timetabling

Enjoy!

Thank you for your hard work in promoting Prolog! It has made a great impact on the community. Do you think you can do a few posts on interfacing Prolog with external systems? E.g. not just manual, carefully crafted proof-of-concept demos. But a full interface with perhaps an API endpoint or database with utf-8 data. A lot of Prolog tutorials refuse to acknowledge the fact that it has poor support for non-proprietary Web/GUIs, compared to at least JS/Ruby/Python. It would be really helpful if you can do a post illustrating how to get from the step of multi-language data entry in e.g. React with a Python backend to getting it processed in Prolog.

Thank you very much for your kind words, and for your interest!

Yes, absolutely: In fact, Prolog was designed for natural language processing and convenient interfacing.

However, currently, all existing Prolog systems fall short for such use cases in that they do not optimally combine efficiency with convenience when processing lists of characters. Ideally, lists of characters are efficiently represented internally, i.e., as sequences as raw bytes, and at the same time made available to Prolog programmers as "completely normal" lists, like all other lists, so that they are amenable to DCGs etc.

So, to seriously advertise such use cases, there must first be a Prolog system that handles lists of characters in an efficient way.

Recently, Mark Thom has confirmed his interest in implementing such an efficient internal representation in Scryer Prolog, please see the relevant issue:

https://github.com/mthom/scryer-prolog/issues/95

Rust programmers may be interested in helping with the implementation!

School timetabling is one of those areas which can become a rabbit-hole very quickly. Here in Australia, at least, you have to contend with student subject preferences -- so you end up having constraints around, for example, the number of teachers qualified to teach French at different levels, and the number of students who would like to do French (at different levels of preference and proficiency) and then generate classes.

Then you can also start adding in geographic information -- things like optimising classroom allocations not only for equipment but also for student and teacher transit times between sessions, and for accessibility for specific students and teachers.

And then you have to consider the quality-of-life characteristics of the timetables you generate -- for example, ensuring that a 0.8FTE teacher doesn't have a day where they come in for two sessions only, one first thing in the morning and one last thing in the afternoon.

Oh, and you need to ensure that students get the right number of minutes of instructions for each subject, accounting for exceptional days (like sports carnivals and assemblies) and public holidays. And it'd be good to keep students together a bit, but also mix them up between classes so that they socialise across the whole year level.

There are so many more constraints that can be added over time, with differing levels of importance and significance, that the problem space rapidly becomes huge. That's probably why there are only a handful of players in the market (at least here in Australia).

Reply on news.ycombinator.com