WeekDaze

Synopsis

This is the web-interface to weekdaze, a command-line application which searches for a solution to the configured school-timetable problem. It facilitates configuration of such problems, any of which can then be forwarded to weekdaze to search for a suitable solution. Configuration requires specification of all the available resources, the subjects taught by teachers & required by students, & any further constraints on the solution.

Video-tutorial

Video-tutorial Contents
Page-name Field-name or Operation Offset
mm:ss
User Create 01:06
Login-form Authenticate 01:31
Project
Create
02:37
Options 04:26
Lesson-criteria Weights 05:10
Timetable-criteria Weights 06:51
Style 08:33
Timeslot-id Bounds 09:12
Location-catalogue 10:02
Teacher-register 12:37
Student-body Register 14:32
Service 17:23
Student-body Membership 19:57
Knowledge-requirement 20:54
Project Run 22:45
Trial 1 23:38
Student-body Register Teaching-ratio 25:27
Project Trial 1.1 26:16
Style CSS URL 28:27
Generate Lesson-colour From 29:01
Execution-options Reduce Student-body Register 29:47
Stream Create 30:11
Student-body Register Stream-id 30:19
Project Trial 2 30:41
Teacher-register Maximum teaching-ratio 31:41
Project Trial 2.1 32:10
Evolution-strategies Create 37:03
Execution-options Random Seed 37:41
Project Trial 3 38:33
Timeslot-id Bounds Max 40:20
Location-catalogue Availability 40:30
Group-catalogue
Create
40:42
Meeting-time 41:22
Student Group-membership 41:52
Teacher Group-membership 42:02
Service Update & Create 42:33
Knowledge-requirement
Create
43:36
Facility-type 44:13
Facility 44:34
Required Facility 44:47
Specialty Topic 45:11
Specific Time Request 45:37
Project Trial 4 46:18
Student-body Register Teaching-ratio 46:58
Project Trial 4.1 47:24
Student-body Register Stream-id 49:18
Project Trial 4.2 49:45
Log-out 53:44
Documentation Overview 53:51
Example-results 55:37
Login-form Authenticate 57:25
Project List 57:40
Student-body Register List & Manage 57:49
Contact-form 58:16

Design

WeekDaze-IO
  • weekdaze can accept configuration either in relatively concise XML, or for greater relational integrity & slightly fewer features, from a SQL-database. The former is intended to be run from the command-line, & the latter via this web-interface.

  • 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. When used from the command-line, 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 several weeks of iterative manual adjustments, before the timetable for a moderately sized school, is acceptable, this solution permits sufficiently precise configuration that it can be left alone to complete the job.

  • The job can be easily re-run.

  • The configuration encapsulates the description of the whole problem, rather than being constrained by reams of free-format notes which must be assimilated before any attempt is made to alter it. A solution which involves manual intervention may additionally use the user's unwritten understanding of the problem, inhibiting hand-over to another user.

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

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

  • One can't realistically define a configuration which accounts for all the possible requirements that might be required; one can merely aim to address the important requirements of the majority of users.

  • A minor change to the requirements may result in a radically different solution, especially when used from the web-interface via which one can't currently import an initial solution. This might present a problem should one wish to re-run the job to account for the unexpected absence of a teacher.

Concluding from the all of the above, that it is probably better to configure the whole problem is advance of attempting to find a solution, an analysis of the requirements of this comprehensive configuration has been performed.

Besides these requirements, a case can be made for additional but currently unimplemented features.

Implementation

Though the subsequent explanation descends into esoteric details, some understanding of the wheels & levers behind the curtain is required to fine-tune the execution-configuration, when attempting to improve unsatisfactory solutions.

This explanation makes liberal use of jargon (in italics to facilitate identification), whose subtle nuances in the context of weekdaze may easily be missed. The precise meaning of these terms have been defined in a glossary, towards which it might occasionally be prudent to swivel one's glazed eye-balls. Those terms which correspond to specific configuration-fields have been quoted to facilitate identification (E.g. field-name), & those which correspond to whole configuration-pages use a seriffed font (E.g. Page-name).

Initial Deterministic Timetable

Starting with an empty timetable, whose x axis identifies each day, whose y axis identifies each time-slot, & whose z axis identifies each resource (one of student-bodies, teachers or locations), the meetings of groups are booked, since these occur @ configured coordinates.

A solution compatible with the remaining configuration is then constructed progressively, by raster-scanning over the three dimensions of the timetable. On visiting unbooked coordinates, when the student-body is available, 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 a given problem-configuration & 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 problem-configuration breaks symmetry, the resulting timetable isn't merely a mirror-image with bookings reflected around either the middle day of the week or the middle timeslot 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 timetable-criteria.

Timetable with example raster

The example timetable depicted has a height of five time-slots per day & is three student-bodies deep.

The data have been arranged so that one axis represents the student-bodies, though weekdaze can also present the data indexed by either teacher or location, if that is more appropriate to the observer.

The configuration to which it conforms, defines a single group Assembly, of which all student-bodies & three teachers are members.

One of the 48 possible rasters has also been depicted, in this case scanning in order of increasing frequency;

  1. student-bodies in a positive sense.
  2. days in a positive sense,
  3. time-slots in a negative sense,

lessons are booked as the raster scans the coordinates of the timetable, each one defining:

  • the subject,
  • the location,
  • the teacher,
  • implicitly the student-body, from its coordinates in the timetable,
  • any student-bodies with whom it is temporary merged to form a student-class.

Evolution

WeekDaze Control-flow

Having created an initial deterministic timetable, an attempt is made to progressively evolve it, using a variety of Evolution-strategies. Each evolution-strategy 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 different 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 reducing the fecundity to zero, individual evolution-strategies can be disabled.

Each depleted timetable is then reconstructed by visiting all unbooked coordinates in a random order, then booking either the fittest lesson, 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. This is described further in the explanation of the configuration-option The number of Initial Scouts.


Configuration … getting started

WeekDaze-configuration

User

The first step is to create a User-account, which requires an Email-address & a Password. The Email-address is used both to ensure that each account is unique & to email solutions to you; it is not shared with any 3rd-party. On creation, the User-account can be observed to be both Executable allowing Projects to be run & Mutable allowing changes to be made; these fields which may only be changed by the site's administrator.

Project

Once authenticated, one can create any number of independent Projects. Each Project requires considerable configuration, & to clarify the process it has been partitioned into:

These subsections have been depicted in the flowchart to the right, & during configuration of a Project they're reflected in the subsections of the menu on the lower right-hand side of the page. Items in this menu have been ordered so that the definition of a Project can progress smoothly from top to bottom, though a less rigid progression is permissible.

The three subsections of the documentation referenced above, are better suited to ad-hoc reference than reading from top to bottom, so you may prefer to leap into the configuration before looking, & open a separate browser-tab for the corresponding documentation using the Contextual Help-button.

Running a Project

Once the configuration for any Project is complete, it can be fed to weekdaze, which runs without any subsequent requirement for input. There is no need to run a Project immediately; your configuration should persist between login-sessions; though currently no regular backup-procedure has been implemented. To execute a Project, navigate to the Project page, select one, & then select the Run menu-item. The weekdaze-executable runs on the server, so no requirements are made of your local machine. If while waiting for a solution, you should discover some misconfiguration, then the execution of the Project can be terminated using the Abort page, which is visible from the Run page.

weekdaze can be run in either of two modes:

Synchronous:

One will need to keep the browser-tab open until it terminates, which could be a long time. This option is therefore only appropriate for very small problems, or when debugging (since reading error-messages from a sequence of emails may become tedious). If you accidentally close the browser-tab, then you should abort the execution of the Project, since you can never retrieve the results & it reduces unnecessary load on the server.

Asynchronous:

The solution will be emailed to the registered Email-address, as an attachment which can be opened in a web-browser. Though one could in principle execute more than one Project simultaneously, this is not currently permitted because of the high CPU-demand.

weekdaze will then perform further checks on the configuration, & will typically reject it having proved that a solution doesn't exist; If it can't, it will attempt to find one.

Since the solution is progressively evolved, the quality depends on the time available. Regrettably, weekdaze can't in general, prove in advance, that all the configured criteria can be satisfied, & consequently it can't guarantee that a completely satisfactory solution for a specific problem can be found regardless of the time devoted to it; though it will always return the best solution found. In this respect, it is incumbent on the user to understand the ramifications of their choice of constraints. One is recommended to define a simple Project first, to understand the available features & their cost, before configuring a real problem.

The time-complexity of the problem is known to be exponential, which is bad news if you're hoping to find the optimal solution. If the solution takes an unacceptably long time, then perhaps one may reduce it by partitioning the day into fewer longer time-slots, or by coercing the students into a more rigid curriculum & consequently fewer larger student-bodies, or by dividing the problem if it can be seen that the locations, student-bodies & teachers can be partitioned into mutually exclusive sub-problems.

The quality of the final solution returned within a given time, depends on the ease with which the evolutionary algorithm can navigate the solution-space. The timetable can become grid-locked by; courses which demand a large Minimum Consecutive Lessons, or which are synchronised, or which have Specific Time Requests; teachers who are fully booked; or locations which are fully utilised.

CAVEAT: the solution isn't currently stored on the server, but is presented on one page of XHTML, which one can save. The XHTML references CSS & images which are located on the server, so the saved document will only be viewable when online. It is recommended that the original XHTML-format be preserved (rather than converting to an image-format), because it defines hidden information which the user can access using a web-browser, by hovering their cursor over various elements.

Diagnostics

Example-results

Several examples have been defined, the configuration for which can be seen by authenticating with Email-address=example@bogus.tld; a Password is neither required nor permissible. The results for each example (named according to the number of time-slots per day) have been captured below.

The Features Used & the Results for Example-projects
Project-name
Click to view results.
Features
Location-catalogue Facility-type Student-body Register Teacher-register Style Service Specialty Topic Specific Time Request Student Group-membership Teacher Group-membership
Campus Free-period Preference Free-period Preference Generate Lesson-colour From Maximum Class-size Minimum Consecutive Lessons Synchronisation-id Group-id
example_01
example_02
example_03
example_05
example_08
example_13

Runtime-information

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:

The tables contain the following information:

The Weighted Mean over the values of Heterogeneous Timetable-criteria, of the Deterministic Timetable resulting from each Raster-scan.

This table depicts the search over various raster-scans, for the best initial deterministic timetable according to the weighted mean over all timetable-criteria. The results of this search are listed, with the selected raster highlighted. If the raster-scan was either fully defined or partially defined by a specification in the Traversal Order page, then fewer traversals will be attempted & itemised, but lacking any specification all 48 raster-scans will be tried.

This data is largely of academic interest, but it also illustrates improvements resulting from any specifications in the Optimise Lesson-criteria Weights page.

Statistics gathered for the values of each Lesson-criterion in isolation, Evaluated over each of the Lessons of the best Deterministic Timetable.

This table depicts statistics gathered about the values of lesson-criteria, during construction of the initial deterministic timetable.

Inspection of these statistics can help one optimise their weights. Initially one might be tempted to adjust their relative weights to make their mean values approximately equal, but a better strategy is probably to initially adjust their relative weights to make their standard-deviations approximately equal, so each has an equal influence on the weighted mean over all lesson-criteria, before tweaking them to reflect the relative importance of each criterion.

The Improvement in the value of each Timetable-criterion, resulting from each Evolution-strategy.

This table depicts the subsequent evolution of the solution. Each row refers to the implementation of an evolution-strategy. For each evolution-strategy, the solution is evolved over a number of generations until no improvement in the weighted mean over timetable-criteria is found within the population of candidate solutions. In each generation, the evolution-strategy is implemented using firstly a depletion-strategy to make space in the current solution, followed by reconstruction using a random-generator to breed a population of candidates, from which the best few, according to the weighted mean over timetable-criteria, are selected.

One can use these results to determine whether any timetable-criteria which weren't satisfied to an acceptable extent, were sacrificed to excessively improve others, & to adjust their relative weights accordingly.

One can also see whether the initial fecundity applied to various Evolution-strategies was excessive & was reduced to increase the diversity in the resulting population of candidates, but otherwise, if the evolution-strategy proved effective, then there may be scope to increase the initial fecundity in order to discover better solutions.

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 problem-parameters, specifically, that teaching the subjects currently required by the referenced student-body, require fewer lessons than the number allocated to teaching in their working week. The number of lessons allocated to teaching, is defined by the field Teaching-ratio in the Student-body Register. The two integers in the error-message are:

x:
The number of lessons required to satisfy the specified Knowledge-requirements.
y:
The number of lessons (according to the Teaching-ratio) allocated to teaching.

For the specified student-body Mnemonic, one can resolve this by:

  • Adding subjects to their Knowledge-requirements.
  • Increasing the Required Lessons-per-week of a course used to satisfy their Knowledge-requirements.
  • Reducing their Teaching-ratio. It might be difficult to exactly match the number of lessons required to satisfy the specified Knowledge-requirements with the number of lessons allocated to teaching, but any Knowledge-requirements 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 Check Lower Workload-bound Of Students; 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 problem-parameters, specifically, that the subjects currently required by the referenced student-body, require more lessons than the number allocated to teaching in their working week. The number of lessons allocated to teaching, is defined by the field Teaching-ratio in the Student-body Register. The two integers in the error-message are:

x:
The number of lessons required to satisfy the specified Knowledge-requirements.
y:
The number of lessons (according to the Teaching-ratio) allocated to teaching.

For the specified student-body Mnemonic, one can resolve this by:

  • Removing subjects from their Knowledge-requirements.
  • Decreasing the Required Lessons-per-week of a course used to satisfy their Knowledge-requirements.
  • Increasing their Teaching-ratio.
  • Downgrading some of their Knowledge-requirements 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 Check Upper Workload-bound Of Students; 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 Maximum teaching-ratio, 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 Maximum teaching-ratio.
  • 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 Check Upper Workload-bound Of Teachers; 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 Required Lessons-per-week for the course.

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

  • Increasing the Maximum teaching-ratio of at least one of the corresponding teachers.
  • Removing this subject from the knowledge-requirements of one or more student-bodies.
  • Decreasing the Required Lessons-per-week 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-ids identical.
  • Add another teacher of the referenced subject to reduce the load on those currently offering it.
  • Unchecking Check Teaching-capacity By Subject; probably a mistake.
'ssh' exited abnormally.
ssh: connect to host IP-address port 22: Connection timed out.

Configuration is recorded by the web-server, but attempts to find a solution to it are delegated to a compute-server … which isn't responding.

Your configuration will persist & can be resubmitted when this has been resolved. Please send a support-request.

Failed to read all the required configuration from the database.
weekdaze: user error (incorrect "databasePassword" for databaseUserId=Email-address; database-access denied)

Your configuration is held in a database, access to which is password-protected. The wrong Password has been specified when attempting to run a Project.

Try running the Project again, specifying the Password previously used to authenticate.