WeekDaze

Problem

School-timetables are more complicated than they initially appear. An individual merely sees a two-dimensional grid in each square of which they are required to coordinate with others at a specific location, but each individual's timetable may differ & must mesh with the others into a three-dimensional structure, in which conflict is avoided. This three-dimensional timetable schedules the use of resources (students, teachers & locations), such that no resource is double-booked; this is formally known as the school-timetable problem. It is a type of constraint-satisfaction problem, & other than performing an exhaustive search of the entire solution-space, there is no algorithmic solution; nor need there be any solution. This command-line application randomly searches for a solution to the specified problem.

Design

• Configuration requires specification of all the available resources, & any further constraints on the solution. weekdaze can accept configuration either in relatively concise XML, or for greater relational integrity & slightly fewer features, from a SQL-database. The database-schema has been structured so that this application can be run from a website, in that it caters for many isolated users, each with many independent timetable-problems. In either case, the configuration is split into three major sections (executionOptions, outputOptions & problemParameters) which are described in detail in section-5 of the packaged man-pages.

• In contrast to most commercially available solutions, the solution-process is non-interactive; if the final result is inappropriate, then the request must be re-configured to express the missing requirement, & then re-started. One can also feed a previously discovered solution described in XML, into weekdaze as the initial state from which to search for a similar solution. This feature permits one to make minor restricted changes to both the solution & the configuration.

Pros:

• Whereas an interactive solution may take weeks before guiding the user to a solution for the timetable-requirements of a moderately sized school, this non-interactive approach can be left alone to complete the job.

• The job can easily be re-run should the problemParameters be altered.

• The configuration encapsulates the description of the whole problem, neither free-format notes nor unwritten understanding need be communicated before hand-over to another user.

Cons:

• A large amount of tedious configuration is required before any results are seen.

• Deviation from a regular weekly routine, for example around public holidays or examinations, can't currently be configured & probably never will be.

• One can't realistically implement a configuration-grammar which is sufficiently general to account for all future requirements; one can merely aim to address the important requirements of the majority of users.

• A minor change to the problemParameters may result in a radically different solution. This might present a problem should one wish to re-run the job to account for the unexpected absence of a teacher, without unnecessary disruption to students' daily routine.

Implementation

Though the subsequent explanation descends into esoteric details, some understanding of the wheels & levers behind the curtain is required to fine-tune the executionOptions, when attempting to improve an unsatisfactory solution. The precise meaning of esoteric terms have been defined in a glossary, towards which it might occasionally be prudent to swivel one's glazed eye-balls.

Initial Deterministic Timetable

Starting with an empty timetable, whose x-axis identifies each day, whose y-axis identifies each timeslotId, & whose z-axis identifies a type of resource, the solution starts with the booking of the meetings of groups (since the configuration currently requires these to occur @ predefined times).

A solution compatible with the remaining problemParameters is then constructed progressively, by raster-scanning over the three dimensions of the timetable. On visiting unbooked coordinates, when a studentBody is available to be taught, the best lesson according to a fitness-function based on the lesson-criteria is booked. The aim of this procedure is to begin the subsequent evolution of the timetable from a reasonable starting-point in the solution-space. This initial procedure is deterministic; for given problemParameters & raster-scan, it will always produce the same result.

The pattern of the raster-scan dictates the order in which coordinates are visited & potentially booked. Because the three axes of the timetable represent different concepts, the order in which they're visited by the raster, results in solutions with different characteristics. Less obviously, the sense in which an axis is traversed by the raster, also makes a difference; because if the problemParameters break symmetry, the resulting timetable isn't merely a mirror-image with bookings reflected around either the middle day of the week or the middle time-slot of the day. One may specify the specific order & sense in which the axes of the timetable should be traversed, but since it can be difficult to guess in advance, which of the various raster-scans will result in the best timetable, normally one merely requests the default behaviour, which is to evaluate all permutations of raster-scan, & to select the best resultant timetable according to a fitness-function based on timetableCriteriaWeights.

Evolution

Having created an initial deterministic timetable, an attempt is made to progressively evolve it, using a variety of evolutionStrategies. Each one involves depleting the current solution by selectively unbooking various lessons, & then reconstructing it in various ways to form a population of candidates in which there might be a superior solution.

Various depletion-strategies are used; most focus on bookings exhibiting some undesirable trait, whilst the remainder attempt to improve some desirable metric. Since some depletion-strategies (typically the former kind) don't liberate sufficient space in the timetable for any beneficial mutation to occur, depletion-strategies can be arbitrarily combined; though this feature is hard-coded rather than configurable.

Each depletion-strategy may identify many alternative sets of lessons to unbook, resulting in a population of candidate-timetables, the size of which is limited by its fecundity (configured independently for each evolution-strategy). By zeroing this fecundity, individual evolutionStrategies can be disabled.

Each depleted timetable is then reconstructed by visiting all unbooked coordinates in a random order, then booking either the fittest lesson now available (which may differ from the one recently removed), or one randomly selected from those which are viable.

After constructing a population of candidate-timetables in any one generation, the fittest few (even when less fit than their parent) are bred for several more generations to expand the population, before selecting the best (amongst all these generations) according to a fitness-function based on timetable-criteria, from which to proceed.

Runtime-information

Several examples have been defined, the results for which have been captured below.

The runtime-information recorded for each of the above examples, is composed from a list of warnings followed by three tables. The warnings typically refer to either:

• automatic cancellation of those parts of the executionOptions which lack relevance in the context of the specified problemParameters.
• automatic removal of irrelevant problemParameters.

Common Error-messages

checkStudentsLowerWorkloadBound: the workload associated with all subject-requirements, for some student-bodies, is insufficient to meet the tuition-time in their working-week; [(mnemonic,(x,y))]

weekdaze is complaining that no solution exists for the specified problemParameters, specifically, that the teaching the all the subjects currently required by the referenced studentBody, requires fewer lessons than the number required to be allocated to teaching in their working week. The number of lessons allocated to teaching, is defined by the field teachingRatio in the studentBodyRegister. The two integers in the error-message are:

x:

The number of lessons required to satisfy the specified knowledgeRequirements.

y:

The number of lessons (according to the teachingRatio) allocated to teaching.

For the specified studentBody/mnemonic, one can resolve this by:

• Adding subjects to their knowledgeRequirements.
• Increasing the requiredLessonsPerWeek of a course used to satisfy their knowledgeRequirements.
• Reducing their teachingRatio. It might be difficult to exactly match the number of lessons required to satisfy the specified knowledgeRequirements with the number of lessons allocated to teaching, but any knowledgeRequirements categorised as optional, are allowed to exceed this limit.
• Reduce their availability; though since this is a relatively course adjustment, it is unlikely to exactly match the required change.
• Unchecking checkStudentsLowerWorkloadBound probably a mistake.

checkStudentsUpperWorkloadBound: the workload associated with core subject-requirements, for some student-bodies, exceeds the tuition-time available in their working-week; [(mnemonic,(x,y))]

weekdaze is complaining that no solution exists for the specified problemParameters, specifically, that the subjects currently required by the referenced studentBody, require in total, more lessons than the number allocated to teaching in their working week. The number of lessons allocated to teaching, is defined by the field teachingRatio in the studentBodyRegister. The two integers in the error-message are:

x:

The number of lessons required to satisfy the specified knowledgeRequirements.

y:

The number of lessons (according to the teachingRatio) allocated to teaching.

For the specified studentBody mnemonic, one can resolve this by:

• Removing subjects from their knowledgeRequirements.
• Decreasing the requiredLessonsPerWeek of a course used to satisfy their knowledgeRequirements.
• Increasing their teachingRatio.
• Downgrading some of their knowledgeRequirements from core to optional.
• If there are currently any working days on which they're unavailable, increase their availability; though since this is a relatively course adjustment, it is unlikely to exactly match the required change.
• Unchecking checkStudentsUpperWorkloadBound; probably a mistake.

checkTeachersUpperWorkloadBound: the time associated with meetings, for some teachers, exceeds the non-teaching time available in their working-week; [(teacher-id,(x,y))]

The specified teacher has a maximumTeachingRatio, which may leave inadequate time for the meetings of groups of which they're members; though the actual ratio of their time required for teaching may be lower than the specified maximum in the resulting timetable. The two integers in the error-message are:

x:

The number of timeslots required for meetings in that teacher's week.

y:

The number of free periods available in that teacher's week.

For the specified teacher, one can resolve this by:

• Reducing their maximumTeachingRatio.
• Un-enrolling them from at least one group which specifies a meeting.
• If there are currently any working days on which they're unavailable, increase their availability.
• Unchecking checkTeachersUpperWorkloadBound; probably a mistake.

checkTeachingCapacityBySubject: the total demand for separate courses in some subjects exceeds that offered by teachers; [((topic,level),(x,y)),((topic,level),(x,y))]

The demand amongst student-bodies for the referenced subjects exceeds the total number of time-slots worked by those all teachers offering a compatible course. The two integers referenced for each subject are:

x:

The number of unmergeable student-bodies who require the subject.

y:

The total number of separate classes that the corresponding teachers can manage given their availability & the requiredLessonsPerWeek for the course.

For each of the specified courses, one can resolve this by:

• Increasing the maximumTeachingRatio of at least one of the corresponding teachers.
• Removing this subject from the knowledgeRequirements of one or more student-bodies.
• Decreasing the requiredLessonsPerWeek of the courses offering this subject.
• Permit weekdaze to merge some of the student-bodies (perhaps just for tuition in this subject) by making their stream identical.
• Add another teacher of the referenced subject to reduce the load on those currently offering it.
• Unchecking checkTeachingCapacityBySubject; probably a mistake.

Glossary

In the context of this application, the following terminology is employed. The terms have been coined as the need has arisen, & don't necessarily correspond to the jargon used by other solutions in this problem-domain.

Availability:

The whole days when a resource is available to be booked. Fractions of days can't be directly expressed, though if the resource is human, any unavailable portion of a day can be reserved artificially, using the meetings of a single-member group (which has no purpose & doesn't require a location).

Booking:

A rendezvous defined in the timetable, for a specific lesson @ a specific time. Similar to a meeting, but refers to a lesson, rather than a group. Though the booking-times of a lesson can be specified in the configuration, typically it is allocated @ run-time by weekdaze, which inserts it between the fixed meeting-times of groups.

Campus:

Defines a set of proximate locations, between which intraday migration is trivial. If the time required to migrate between locations is significant, then one may partition them into campuses to allow the application to minimise the number of such journeys.

Course:

A set of lessons in a common subject, offered by a single teacher. Though a subject would typically require many weeks of tuition, the requirements for just one arbitrary week are configured, on the assumption that those for other weeks are similar. A course springs into existence, when it is offered as part of a teacher's service, rather than existing as an independent part of the configuration to which teachers & student-bodies refer.

Day:

The working portion (rather than the full 24 hours), of a day of the week. The day forms one of the two temporal axes, from the three Cartesian coordinates used to describe the single-week timetable.

Depletion-strategy:

A method used by weekdaze to liberate space in the timetable, by selectively unbooking lessons. The lessons are selected; in order to reduce some undesirable trait; to re-cast any established routine; or arbitrarily, merely to permit exploration of an alternative region in the solution-space.

Evolution-strategy:

One of many methods used by weekdaze, in an attempt to evolve the timetable. Each is composed from a depletion-strategy & a reconstruction-strategy.

Facility:

An attribute of a location, which can in some way support a course.

Fecundity:

The size of the population of candidate-timetables, that weekdaze breeds in any one generation of the evolution of a solution.

Fitness-function:

Used either to quantify the:

• suitability of each member of a set of alternative lessons to book in the timetable @ a specific time, using a weighted-mean of lesson-criteria;

• value of each member of a set of alternative timetables, using a weighted-mean of a set of timetable-criteria.

Group:

A set of one or more people (teachers or student-bodies) with a common interest or duty. This is a more flexible structure than the single teacher & student-class used to define a lesson.

Knowledge-requirements:

The set of one of more subjects required by a student-body. It is partitioned into those personally considered (other student-bodies may categorise them differently) to be either core or optional.

Lesson:

An arrangement between a single teacher & a student-class, to teach a course for one period @ a specific location & time-slot. A lesson as depicted in the results, always specifies the course's subject, but only two of the three types of resource, the third being implied by the coordinate @ which it is booked on the observer-id axis of the timetable.

Lesson-criteria:

The metrics used by weekdaze when constructing a solution, to quantify & therefore to facilitate selection, of the best lesson from those which are permissible @ specific coordinates. The value of each criterion is typically neither dependent on what has already been booked elsewhere, nor does it change as further bookings are made. Though the semantics of each criterion are hard-coded, they have an associated configurable weight, which allows one to change its significance relative to other lesson-criteria.
cf. timetable-criteria which are used to quantify & therefore select the best from a population of candidate-timetables.

Level:

The level @ which a topic is taught, or the personal academic capability or year of a student.

Location:

A generalisation of a class-room, to encompass any space available to support either a booking or a meeting. It is described by:

• its availability,
• its capacity,
• the campus in which it is located,
• the facilities it offers to support courses.

Meeting:

A rendezvous defined in the timetable, between group-members @ a specific time. Similar to a booking, but refers to a group, rather than a lesson. The meeting-times of a group are configured, & are therefore reserved by weekdaze, forcing lessons to float around them.

Observer:

The target audience for a timetable, which may be any type of resource. Bookings may be tailored to any of these types of observer, by enumerating observer-identifiers along one axis of the timetable (the remaining two axes are always the day & the timeslotId), thus permitting all observers of that type to rapidly access their personal timetable for the week.
NB. since a location is clearly incapable of observing anything, one may more correctly consider the timetable indexed by locationId, to be ideally organised for observation by maintenance-staff.

Period:

Similar to time-slot but refers more to a duration than to a position on the time-axis.

Population-diversity Ratio:

The ratio of distinct members to all the members, in a population of candidate-timetables.

Resource:

Either a location, a studentBody or a teacher. Since each lesson requires one of each type of resource, the most basic function of weekdaze is to avoid scheduling-conflicts between them; no individual can be booked @ more than one location @ any time, & no location can host more than either one class or one meeting @ a time.
cf. Observer.

Routine:

The relationship established between resources, when teaching the lessons of a course. It is considered desirable that such routines are preserved, so that for any one subject, a student-body isn't taught either @ more than one location or by more than one teacher.

Service:

The set of courses offered by a teacher.
N.B.: a teacher who offers no service directly to students, may still exist in the timetable @ the meetings they attend.

Stream:

This is the personal academic capability or year of a studentBody. The requirement for a studentBody to have a explicit stream isn't obvious, since it can be inferred from the level of the topics in their knowledgeRequirements, but it can be used to prevent the various student-bodies studying a subject from being merged into a single student-class (should that be undesirable).

Student:

An individual, whose requirements are described by the studentBody of which they're a member.

Student-body:

A set of students with identical requirements (availability, stream, knowledgeRequirements, group-membership). These sets are typically manually configured, but additional or larger sets, may optionally be automatically discovered by weekdaze; it can also relax the requirement that the students belong to the same groups, if the groups for which memberships differ, never actually meet.

Student-body Combinations:

Student-body Combinations

Teacher	Student-body	Time
		t1	t2	t3
T1	S1	C1		C1
	S2	C1	C1
	S3		C1	C1

This refers to an undesirable trait in a timetable, where the set of student-bodies, who're temporarily merged into a student-class for the tuition of a course, changes throughout the lessons booked in a week. E.g. where three student-bodies, S1, S2, S3, are enrolled on course C1, taught by teacher T1, which requires two lessons per week;

• S1 may be merged with S2 to form a student-class @ time t1,
• S2 may be merged with S3 to form a student-class @ time t2,
• S3 may be merged with S1 to form a student-class @ time t3.

The undesirable consequence is that teacher T1 must synchronise progress through the course, between these student-classes.

Student-class:

A set of student-bodies, which are temporarily merged during the tuition of a single course.

Student-class Combinations:

Student-class Combinations

Teacher	Student Class	Time
		t1	t2	t3	t4
T1	S1		C1	C1
	S2	C1			C1
T2	S3	C2		C2
	S4		C2		C2

This refers to an undesirable trait in a timetable, in which lessons for a set of synchronised courses have been booked. Though the courses which share a synchronisationId, may have been booked without any undesirable student-body combinations, each lesson may be synchronised with different student-classes in the other courses of the set.

E.g. take two synchronised courses, C1 taught by teacher T1, & C2 taught by teacher T2, each of which requires two lessons per week. Student-bodies S1 & S2 are enrolled on C1, while student-bodies S3 & S4 are enrolled on C2. Whilst these four student-bodies could be merged into two student-classes {S1, S2} & {S3, S4} under these circumstances no undesirable student-body combinations can arise, but should their availability dictate that they must form four singleton student-classes, different pairs of singleton student-classes may be synchronised @ various times throughout the week.

The consequence of this only becomes apparent, when any one of these student-bodies decides to migrate to the other course in this synchronised set; which, as required, is possible without reorganising the timetable, but results in a student-body combination. E.g. should S1 decide to migrate from C1 to C2, a student-class is then formed between S1 & S4 @ t2, but between S1 & S3 @ t3.

Subject:

A combination of a topic & the level @ which it is taught. It is a component of both a studentBody's knowledgeRequirement & teacher's service, & can only be required by the former, when offered by the latter.

Synchronised courses:

A set of courses, whose respective lessons must be synchronised. The member-courses;

• may have different subjects;
• must define the same requiredLessonsPerWeek;
• can in aggregate only define either one ideal timeslot, or specify precise booking-times the union of which is limited in size by requiredLessonsPerWeek;
• must be offered by teachers whose availabilities intersect.

The image (extracted from the output of weekdaze) depicts the scheduling of three synchronised courses:

Geography/History:

Day	Time-slot	Geography	1	History	1
Monday	3	Body_1 & Body_3		Body_2
Wednesday
Thursday	4
Friday	0

Maths:

Day	Time-slot	Maths	Applied 1	Maths	Pure 1
Monday	1	Body_1 & Body_3		Body_2
Tuesday
Wednesday
Thursday	1	Body_1 & Body_3		Body_2
Friday

Physics Streams:

Day	Time-slot	Physics	1.A	Physics	1.B
Tuesday	3	Body_1		Body_2 & Body_3
	4
Wednesday	0
	1

Since the structure of the timetable is largely independent of precisely which of these member-courses is selected by a student-body, migration of a student-body between them (should their initial choice prove hasty), is relatively easy. The use-cases for this concept fall into two categories;

Different topics @ the same level.

Permits student-bodies to select only one of the topics offered, as required to implement an elective line.

Different levels of the same topic.

Permits student-bodies to migrate to a similar course, but which caters for students with a different ability.

Whilst the flexibility exists to synchronise the bookings for courses whose topic and level differ, this concept is hard to justify.

Teacher:

A description of an individual's:

• availability,
• the proportion of their working-week devoted to teaching,
• the service they offer to students,
• the groups of which they're members.

Time-slot:

The partitions into which each day is similarly divided, each one of which is available for the booking of a lesson or meeting.

Similar to a period, but refers more to a position on the time-axis than to a duration.

Timetable:

Conceptually a cuboid, whose three Cartesian axes are indexed by; day, timeslotId, & observer-id. The observer-id axis can be any resource-type, depending on the target-audience; there's no change to the data, they're merely re-indexed.

The timetable depicted is five time-slots per day high, & is indexed by student-bodies of whom there are three. Were it re-indexed so that the intended observer was a teacher, then the depth may change.

Timetable-criteria:

The metrics used by weekdaze, to quantify the degree to which a timetable meets the specified problemParameters. These allow it to select amongst alternative solutions, while searching for the optimum. Though the semantics of each criterion are hard-coded, each has an associated configurable weight, which allows one to change its significance relative to other timetable-criteria.
cf. lesson-criteria which are used to quantify & therefore select the best amongst alternative lessons to book at specific coordinates.

Topic:

The component of a subject which is independent of the level @ which it is taught.