Constraint-based School Timetabling with Prolog

Try it:

Sample instances: example1.pl example2.pl example3.pl

What it means:

The input is a sequence of Prolog facts that describe what we want from a solution.

The dimensions of the timetable are specified by:

slots_per_week(W)
Each week has W time slots.
slots_per_day(D)
Each day has D time slots.

The main requirements are specified by:

class_subject_teacher_times(C, S, P, T)
Class C must have subject S, taught by person P, exactly T times per week.

Additional requirements are specified by:

class_freeslot(C, F)
No lesson must be scheduled at time F for class C.
coupling(C, S, L1, L2)
For class C, lessons L1 and L2 of subject S are to be scheduled in direct succession.
teacher_freeday(T, D)
For teacher T, day D must be kept free.
room_alloc(R, C, S, L)
Room R is to be used for class C and lesson L of subject S

How it works:

Watch the video:

The timetabling engine is freely available: Simsttab

Simsttab uses constraint logic programming over integers to find solutions that satisfy all requirements.

More about Prolog: The Power of Prolog

Main Page

slots_per_week(35).

slots_per_day(7).

%class_subject_teacher_times('1a', ume, ume1, 2).
%class_subject_teacher_times('1a', nej, nej1, 3).
class_subject_teacher_times('1a', deu, sjk1, 4).
class_subject_teacher_times('1a', mat, mat1, 5).
class_subject_teacher_times('1a', eng, anj1, 3).
class_subject_teacher_times('1a', h, zgo1, 2).
class_subject_teacher_times('1a', geo, geo1, 2).
class_subject_teacher_times('1a', ch, kem1, 2).
class_subject_teacher_times('1a', bio, bio1, 2).
class_subject_teacher_times('1a', ph, fiz1, 2).
class_subject_teacher_times('1a', f, rai1, 2).
class_subject_teacher_times('1a', lat, atvz1, 3).
coupling('1a', deu, 2, 3).
class_freeslot('1a', 0).
class_freeslot('1a', 1).

class_subject_teacher_times('1b', deu, sjk1, 4).
class_subject_teacher_times('1b', mat, mat2, 5).
class_subject_teacher_times('1b', eng, anj2, 3).
class_subject_teacher_times('1b', nej, nej2, 3).
class_subject_teacher_times('1b', h, zgo2, 2).
class_subject_teacher_times('1b', geo, geo1, 2).
class_subject_teacher_times('1b', ch, kem2, 2).
class_subject_teacher_times('1b', bio, bio1, 2).
class_subject_teacher_times('1b', ph, fiz2, 2).
class_subject_teacher_times('1b', f, rai1, 2).
class_subject_teacher_times('1b', ume, ume1, 2).
class_subject_teacher_times('1b', lat, atvz2, 3).

slots_per_week(35).

slots_per_day(7).

class_subject_teacher_times('1a', ume, ume1, 2).
class_subject_teacher_times('1a', nej, ume1, 3).
class_subject_teacher_times('1a', deu, sjk1, 4).
class_subject_teacher_times('1a', mat, mat1, 5).
class_subject_teacher_times('1a', eng, anj1, 3).
class_subject_teacher_times('1a', h, zgo1, 2).
class_subject_teacher_times('1a', geo, geo1, 2).
class_subject_teacher_times('1a', ch, kem1, 2).
class_subject_teacher_times('1a', bio, bio1, 2).
class_subject_teacher_times('1a', ph, fiz1, 2).
class_subject_teacher_times('1a', f, rai1, 2).
class_subject_teacher_times('1a', lat, atvz1, 3).
coupling('1a', deu, 2, 3).
class_freeslot('1a', 0).
class_freeslot('1a', 1).

class_subject_teacher_times('1c', deu, sjk2, 4).
class_subject_teacher_times('1c', mat, mat3, 5).
class_subject_teacher_times('1c', eng, anj3, 3).
class_subject_teacher_times('1c', nej, nej1, 3).
class_subject_teacher_times('1c', h, zgo1, 2).
class_subject_teacher_times('1c', geo, geo1, 2).
class_subject_teacher_times('1c', ch, kem1, 2).
class_subject_teacher_times('1c', bio, bio1, 2).
class_subject_teacher_times('1c', ph, fiz1, 2).
class_subject_teacher_times('1c', f, rai1, 2).
class_subject_teacher_times('1c', ume, ume1, 2).
class_subject_teacher_times('1c', lat, atvz1, 3).

class_subject_teacher_times('1d', deu, sjk3, 4).
class_subject_teacher_times('1d', mat, mat4, 5).
class_subject_teacher_times('1d', eng, anj3, 3).
class_subject_teacher_times('1d', nej, nej2, 3).
class_subject_teacher_times('1d', h, zgo2, 2).
class_subject_teacher_times('1d', geo, geo1, 2).
class_subject_teacher_times('1d', ch, kem2, 2).
class_subject_teacher_times('1d', bio, bio1, 2).
class_subject_teacher_times('1d', ph, fiz2, 2).
class_subject_teacher_times('1d', f, rai1, 2).
class_subject_teacher_times('1d', ume, ume1, 2).
class_subject_teacher_times('1d', lat, atvz2, 3).

class_subject_teacher_times('2a', deu, sjk1, 4).
class_subject_teacher_times('2a', mat, mat2, 5).
class_subject_teacher_times('2a', eng, anj1, 3).
class_subject_teacher_times('2a', nej, nej2, 3).
class_subject_teacher_times('2a', h, zgo2, 2).
class_subject_teacher_times('2a', geo, geo1, 2).
class_subject_teacher_times('2a', ch, kem2, 2).
class_subject_teacher_times('2a', bio, bio1, 2).
class_subject_teacher_times('2a', ph, fiz2, 3).
class_subject_teacher_times('2a', psi, psi1, 2).
class_subject_teacher_times('2a', lat, atvz2, 3).

class_subject_teacher_times('2b', deu, sjk2, 4).
class_subject_teacher_times('2b', mat, mat3, 5).
class_subject_teacher_times('2b', eng, anj2, 3).
class_subject_teacher_times('2b', nej, nej1, 3).
class_subject_teacher_times('2b', h, zgo1, 2).
class_subject_teacher_times('2b', geo, geo1, 2).
class_subject_teacher_times('2b', ch, kem1, 2).
class_subject_teacher_times('2b', bio, bio1, 2).
class_subject_teacher_times('2b', ph, fiz1, 2).
class_subject_teacher_times('2b', psi, psi1, 2).
class_subject_teacher_times('2b', lat, atvz1, 3).

class_subject_teacher_times('2c', deu, sjk2, 4).
class_subject_teacher_times('2c', mat, mat4, 5).
class_subject_teacher_times('2c', eng, anj2, 3).
class_subject_teacher_times('2c', nej, nej2, 3).
class_subject_teacher_times('2c', h, zgo2, 2).
class_subject_teacher_times('2c', geo, geo1, 2).
class_subject_teacher_times('2c', ch, kem2, 2).
class_subject_teacher_times('2c', bio, bio1, 2).
class_subject_teacher_times('2c', ph, fiz2, 2).
class_subject_teacher_times('2c', psi, psi1, 2).
class_subject_teacher_times('2c', lat, atvz2, 3).

class_subject_teacher_times('2d', deu, sjk3, 4).
class_subject_teacher_times('2d', mat, mat1, 5).
class_subject_teacher_times('2d', eng, anj3, 3).
class_subject_teacher_times('2d', nej, nej1, 3).
class_subject_teacher_times('2d', h, zgo1, 2).
class_subject_teacher_times('2d', geo, geo1, 2).
class_subject_teacher_times('2d', ch, kem1, 2).
class_subject_teacher_times('2d', bio, bio1, 2).
class_subject_teacher_times('2d', ph, fiz1, 3).
class_subject_teacher_times('2d', psi, psi1, 2).
class_subject_teacher_times('2d', lat, atvz1, 3).

class_subject_teacher_times('3a', deu, sjk1, 4).
class_subject_teacher_times('3a', mat, mat3, 4).
class_subject_teacher_times('3a', eng, anj1, 3).
class_subject_teacher_times('3a', nej, nej1, 3).
class_subject_teacher_times('3a', h, zgo1, 2).
class_subject_teacher_times('3a', geo, geo1, 2).
class_subject_teacher_times('3a', ch, kem1, 2).
class_subject_teacher_times('3a', bio, bio1, 2).
class_subject_teacher_times('3a', ph, fiz1, 2).
class_subject_teacher_times('3a', soc, soc1, 2).
class_subject_teacher_times('3a', lat, atvz1, 3).

class_subject_teacher_times('3b', deu, sjk2, 4).
class_subject_teacher_times('3b', mat, mat4, 4).
class_subject_teacher_times('3b', eng, anj1, 3).
class_subject_teacher_times('3b', nej, nej2, 3).
class_subject_teacher_times('3b', h, zgo2, 2).
class_subject_teacher_times('3b', geo, geo1, 2).
class_subject_teacher_times('3b', ch, kem2, 2).
class_subject_teacher_times('3b', bio, bio1, 2).
class_subject_teacher_times('3b', ph, fiz2, 2).
class_subject_teacher_times('3b', soc, soc1, 2).
class_subject_teacher_times('3b', lat, atvz2, 3).

class_subject_teacher_times('3c', deu, sjk3, 4).
class_subject_teacher_times('3c', mat, mat1, 4).
class_subject_teacher_times('3c', eng, anj2, 3).
class_subject_teacher_times('3c', nej, nej1, 3).
class_subject_teacher_times('3c', h, zgo1, 2).
class_subject_teacher_times('3c', geo, geo1, 2).
class_subject_teacher_times('3c', ch, kem1, 2).
class_subject_teacher_times('3c', bio, bio1, 1).
class_subject_teacher_times('3c', ph, fiz1, 2).
class_subject_teacher_times('3c', soc, soc1, 2).
class_subject_teacher_times('3c', lat, atvz1, 3).

class_subject_teacher_times('3d', deu, sjk1, 4).
class_subject_teacher_times('3d', mat, mat2, 4).
class_subject_teacher_times('3d', eng, anj3, 3).
class_subject_teacher_times('3d', nej, nej2, 3).
class_subject_teacher_times('3d', h, zgo2, 2).
class_subject_teacher_times('3d', geo, geo1, 2).
class_subject_teacher_times('3d', ch, kem2, 2).
class_subject_teacher_times('3d', bio, bio1, 1).
class_subject_teacher_times('3d', ph, fiz2, 2).
class_subject_teacher_times('3d', soc, soc1, 2).
class_subject_teacher_times('3d', lat, atvz2, 3).

class_subject_teacher_times('4a', deu, sjk1, 5).
class_subject_teacher_times('4a', mat, mat4, 5).
class_subject_teacher_times('4a', eng, anj1, 4).
class_subject_teacher_times('4a', nej, nej2, 2).
class_subject_teacher_times('4a', h, zgo1, 2).
class_subject_teacher_times('4a', fil, fil1, 2).
class_subject_teacher_times('4a', lat, atvz2, 3).

class_subject_teacher_times('4b', deu, sjk2, 5).
class_subject_teacher_times('4b', mat, mat1, 5).
class_subject_teacher_times('4b', eng, anj2, 4).
class_subject_teacher_times('4b', nej, nej1, 2).
class_subject_teacher_times('4b', h, zgo1, 2).
class_subject_teacher_times('4b', fil, fil1, 2).
class_subject_teacher_times('4b', lat, atvz1, 3).

class_subject_teacher_times('4c', deu, sjk3, 5).
class_subject_teacher_times('4c', mat, mat2, 5).
class_subject_teacher_times('4c', eng, anj1, 4).
class_subject_teacher_times('4c', nej, nej2, 2).
class_subject_teacher_times('4c', h, zgo1, 2).
class_subject_teacher_times('4c', fil, fil1, 2).
class_subject_teacher_times('4c', lat, atvz2, 3).

class_subject_teacher_times('4d', deu, sjk3, 5).
class_subject_teacher_times('4d', mat, mat3, 5).
class_subject_teacher_times('4d', eng, anj2, 4).
class_subject_teacher_times('4d', nej, nej1, 2).
class_subject_teacher_times('4d', h, zgo1, 2).
class_subject_teacher_times('4d', fil, fil1, 2).
class_subject_teacher_times('4d', lat, atvz1, 3).
class_freeslot('4d', 6).

room_alloc(r1, '1a', deu, 0).
room_alloc(r1, '1a', deu, 1).
room_alloc(r1, '4c', mat, 0).
room_alloc(r1, '4d', mat, 0).

teacher_freeday(ume1, 4).