WeekDaze

Execution-options

These define the details of the solution-algorithm. This part of the configuration is largely independent of the specific timetable-problem & completely independent of the presentation of the solution. Consequently it typically persists unaltered between problems, but because it's unrelated to anything directly relevant to the user, it's rather esoteric.

Fields

Random Seed:

This optional attribute takes an integer with which to seed the single pseudo-random number-generator used for all the application's random operations (this only affects the evolution of the timetable, since the Initial Deterministic Timetable, as it says on the tin, hasn't any random component). In its absence, the random-number generator will be seeded from the operating-system, an unpredictable pseudo-random sequence will result, & each time the same problem is posed, weekdaze may return a different answer.

The evolutionary lineage resulting from each choice of seed may differ, but since there are conceptually infinite possible seeds & a finite number of solutions to the configured problem, some must ultimately converge. Changing the seed can sometimes produce a radically different & potentially superior solution. Specification of a previously used seed, may be useful if one wants to either generate a similar timetable after a small change to the configuration, or to revisit a previous solution after failing to improve on it.

Even with the same seed, the pseudo-random sequence depends on the platform on which the application was compiled.

Permit Temporary Student-body Merger:

The configured student-bodies may not each represent many students, & can therefore be merged automatically by weekdaze into larger student-classes, to more efficiently use the available locations & teachers. Such transient mergers persist only for the tuition of a specific course, & those student-bodies may be merged differently or not @ all, during the tuition of another course; cf. Reduce Student-body Register, which persist for the duration of the problem.

Certain incompatible Lesson-criteria Weights are zeroed depending on the value of this option;

When the constraints imposed by the problem-configuration are tight, it may be necessary for the lessons of a single course, to be composed from different combinations of student-bodies; e.g. student-body A may combine with student-body B, to form a student-class to study a specific subject on one day, but may also combine with student-body C to form a different class, to study the same subject on another day. Whilst clearly undesirable, this scenario may be better than one student-body not learning that subject due to lack of resources. See Minimise Student-body Combinations.

This boolean switch allows such temporary mergers to occur.

Reduce Student-body Register:

The efficiency of the application is partially dependent on the number of student-bodies. When the similarity in the requirements of the students (as required of the members of a student-body) is driven by some common external process (e.g. a rigid curriculum involving limited subject-choice), one would typically model that by manually partitioning them into student-bodies during configuration, but if after configuration the requirements of some student-bodies are coincidentally identical, then this boolean switch enables their automatic discovery & merges them to increase efficiency. These merged student-bodies persist for the duration of this problem, & will be booked into the timetable as an atomic unit; cf. Permit Temporary Student-body Merger, which results in mergers which persist only for the tuition of a specific course.

If as a result, the class-size becomes infeasibly large, then this option can be unchecked, preserving the original configuration.

If Verbosity is greater than minimum, then any such automatic mergers will be logged.

Remove Redundant Courses:

By automatically removing courses from any teacher, which aren't required by any student, one can improve the accuracy of the measurement of certain criteria used to evolve the timetable & expose certain anomalies regarding synchronised courses.

If Verbosity is greater than minimum, then any such courses will be logged.

Remove Pointless Groups:

Whether to remove groups from the group-catalogue, for which zero meetings have been scheduled. This may allow additional student-bodies with identical requirements to be discovered & merged, which if undesirable can be prevented either by switching this option off or by changing the Stream-id of one of the student-bodies.

If Verbosity is greater than minimum, then any such groups will be logged.

Remove Unsubscribed Groups:

Whether to remove groups from the group-catalogue, to which neither student-bodies nor teachers have subscribed.

If Verbosity is greater than minimum, then any such groups will be logged.

Zero Inappropriate Options:

Where aspects of the execution-configuration lack relevance in the context of the specified problem-configuration, this option allows one to request automatic:

Problem-validation Switches

A set of boolean switches governing various runtime-checks on the problem-configuration. Should any of these obstruct the specification of unusual but intention requirements, they can individually be switched-off; the results cannot be guaranteed, but it may provide the required silver bullet. The names of these switches, prefix any error-message generated from the failure of the corresponding check.

Fields

Check Availability Of Any Group-member:

Check that @ least one member, can attend each Meeting-time of a group.

Check Capacity Of Locations For Meetings:

Check that any Location-id, specified for the meetings of a group, has adequate Capacity.

Check Courses For Synchronous Specified Times:

Check that no courses, required to satisfy a student-body's Knowledge-requirements, specify the same booking-time.

Check Duplicate Meeting-location Ids:

Check that when more than one group requires the same Location-id, that their Meeting-times are mutually exclusive.

Check For Alternatives To Synchronised Courses:

Ensure that student-bodies can migrate easily between synchronised courses, by prohibiting any teacher from offering an alternative course outside the synchronised set, but with an identical subject to one of the member-courses.

Check For Idle Students:

Check for student-bodies who require zero subjects, but have allocated one or more time-slots for teaching.

Check For Idle Teachers:

Check for teachers who offer zero courses, but have allocated one or more time-slots for teaching.

Check For Multiple Courses Per Teacher Per Synchronisation-id:

Check that no teacher offers more than one course with the same Synchronisation-id.

Check For Non Existent Facilities:

Check for the existence in @ least one location, of all the Required Facilities for each course.

Check For Overloaded Students:

Check for student-bodies who have allocated zero time-slots for teaching, but have requested one or more subjects.

Check For Singleton Synchronised Courses:

Check for teachers offering a course which is a singleton synchronised set.

Check For Students Requiring Multiple Synchronised Subjects:

Check for any student-body requiring more than one subject from any one set of synchronised courses.

Check For Students With Unrealisable Free-period preference:

Check for any student-body whose Free-period Preference, can never be realised because of the Meeting-times" of groups of which they're members.

Check For Synchronised Courses With Different Ideal Time-slots:

Check that synchronised courses don't define different Ideal-timeslot requests.

Check For Synchronised Courses With Different Lessons-per-Week:

Check that synchronised courses don't define different Required Lessons-per-week.

Check For Synchronised Courses With Excess Lessons-per-Week:

Check that synchronised courses don't define a greater Required Lessons-per-week, than the number of time-slots when all the interested student-bodies & required teachers are simultaneously available.

Check For Synchronised Courses With Excess Specified Times:

Check that synchronised courses don't have fewer Required Lessons-per-week than the number of booking-times specified by the union of their Specific Time Requests.

Check For Synchronised Courses With Excess Timeslot-requests:

Check that synchronised courses don't specify both Ideal-timeslot requests & Specific Time Requests; these are intended to be alternatives.

Check For Synchronised Courses Without Suitable Locations:

Check for synchronised courses which lack sufficient locations offering the Required Facilities, which are simultaneously available to the teachers & all interested student-bodies.

Check For Synchronised Courses With Unavailable Specified Days:

Check for synchronised courses which specify times, on days when not all the interested student-bodies & required teachers, are available.

Check For Teachers With Unrealisable Free-period preference:

Check for any teacher whose Free-period Preference, can never be realised because of the Meeting-times of groups of which they're members.

Check Whether There Are Sufficient Teachers For The Number Of Student-bodies, On Each Day:

Check that there are sufficient teachers, for the number of student-bodies, available on each day.

Check Whether Each Student-body Can Be Accommodated Within The Largest Available Location:

Check whether each student-body can be accommodated within the largest available location.

Check whether All Student-bodies Can Be Accommodated Within The Available Locations, On Each Day:

Check whether all student-bodies can be accommodated within the locations, available on each day.

Check Independence Of Student Timeslots-requests And Meetings:

Check that student-bodies are members of groups which specify meeting-times (even those which don't mandate attendance), which match any of the specified booking-times of courses they must attend.

Check Independence Of Teacher Timeslots-requests And Meetings:

Check that teachers are members of groups which specify meeting-times (even those which don't mandate attendance), which match any of the specified booking-times of courses they must attend.

Check There Are Sufficient Locations For All Courses:

Check that there are sufficient locations, simultaneously available to at least one student-body & at least one teacher, to support the total number of time-slots required for the courses offered by all teachers.

Check Locations For Synchronous Specified Times:

Check there are enough locations in which to book the lessons of courses offered by different teachers, which specify the same booking-time.

Check Availability Of Meeting-locations:

Check that any location required for a group, is available @ all Meeting-times.

Check Null Location-catalogue:

Check whether the Location-catalogue is empty.

Check Null Student-body Register:

Check whether the Student-body Register is empty.

Check Null Teacher-register:

Check whether the Teacher-register is empty.

Check Availability Of Own Location:

Check for teachers who've got their own location, that it's simultaneously available on @ least one day.

Check Required Lessons-per-Week:

Check that no course is offered, which requires more lessons per week, than the teacher works.

Check Simultaneous Availability Of Group-members:

Check that all the members of each group which both meets & mandates attendance, are simultaneously available.

Check Availability Of Students For Mandatory Meetings:

Check that student-bodies are available for the Meeting-times of the groups of which they're members.

Check Availability Of Students For Specified Times:

Check that no course, required to satisfy a student-body's Knowledge-requirements, specifies a time, on a day when they're unavailable.

Check Students For Synchronous Meetings:

Check that student-bodies aren't members of groups with synchronous Meeting-times.

Check Lower Workload-bound Of Students:

Check that student-bodies request sufficient subjects to fill their working-week to the required extent.

Check Upper Workload-bound Of Students:

Check that student-bodies don't request more courses than can be booked in their working-week.

Check Suitable Locations for Knowledge-requirements:

Check for each student-bodies that there's a suitable location for each knowledge-requirement. To be suitable, a location must be large enough to accommodate the student-body, it must be simultaneously available with the student-body & a teacher offering a matching course, & must offer the facilities required by this course.

Check Availability Of Teachers For Mandatory Meetings:

Check that teachers are available for the Meeting-times of the groups of which they're members.

Check Teachers For Synchronous Meetings:

Check that teachers aren't members of groups with synchronous Meeting-times.

Check Upper Workload-bound Of Teachers:

Check that teachers don't commit to more meetings than they've time to attend.

Check Teaching-capacity By Subject:

Check that there's sufficient teaching-capacity, to satisfy the demand by student-bodies for each subject. CAVEAT: this check is very lax. To maximise the efficiency with which teachers are used, it is typically assumed that any student-body which can be temporarily merged into a student-class, (see Permit Temporary Student-body Merger); no subsequent account is taken of whether both teachers & locations, can cope with the size of the resulting student-class. Additionally, an error is raised only when the demand for a subject exceeds the total supply, without any account of whether some of the teachers, are simultaneously required to support the other courses in their Service.

Traversal Order

This optionally permits specification of the raster-scan used during the initial deterministic timetable. The required order of the three axes is specified as a triple. The first part of the triple defines the axis along which change is slowest, & the last part represents the axis along which change is most rapid. Each part of the triple defines either one or two fields.

Fields

Sense:

Optionally defines the direction of travels along the axis defined below, as either Positive or Negative. If unspecified, then both directions will be tried.

Axis:

Defines the axis to traverse, as one of; ObserverId, Day, or TimeslotId.

Since it can be difficult to guess in advance which permutation will result in the best solution (though the 2 permutations matching (+ObserverId,+TimeslotId,±Day) seems to perform slightly above average), one would normally accept the default for this, which is to perform all possible raster-scans & select the best timetable according to the weighted mean over the timetable-criteria. The additional time required, is typically small (especially where there's hardware to support parallel execution) compared to that required by the subsequent improvement of the solution using various Evolution-strategies.

Evolution-strategies

Within each generation of the evolution of the timetable, candidates are bred by randomly mutating their parent by partial depletion followed by reconstruction.

Evolution is implemented in the application using a variety of strategies applied sequentially. The order in which evolution-strategies are applied, is hard-coded & beyond the scope of configuration.

One can define the fecundity (i.e. how large a population of candidate-solutions to breed), for each evolution-strategy. The relative magnitude of the various fecundities governs the direction in which the evolution of the solution progresses.

Fields

Depletion-strategies:

NB: some of these will be irrelevant in the context of a given problem; e.g. Synchronised Course Mutation where no synchronised course have been defined; but under these circumstances, the irrelevant depletion-strategy takes a negligible time, so there's little to be gained from zeroing the corresponding fecundity (which the application will do automatically in most cases).

These depletion-strategies may be arbitrarily combined, which is useful where application in isolation doesn't liberate sufficient space, but this ability is hard-coded & beyond the scope of configuration.

Synchronised Course Mutation

This depletion-strategy tackles only synchronised courses, by unbooking all the lessons for courses sharing a Synchronisation-id, in turn. Because a typical student's timetable is almost fully booked, there are relatively few times remaining which are free to accept a booking, & even fewer which can accept the synchronised bookings required for the members of a set of synchronised courses. Consequently, the only solution typically accessible from this depleted state, is the original, & the probability of a beneficial change to the timetable, is therefore low. To improve the probability, a variety of coincidentally synchronised groups of lessons from non-synchronised courses, selected to ensure that all may easily be relocated, are unbooked first, to provide alternative coordinates @ which to book the awkward synchronised lessons of synchronised courses.

Synchronised Course By Day Mutation

This depletion-strategy tackles only synchronised courses, by selecting each synchronised course in turn, & then each day in turn, & unbooking all the corresponding lessons. As for Synchronised Course Mutation, alternative coordinates for the required lessons are created, to improve the probability of finding a superior solution.

Excess Runlength Mutation

This depletion-strategy focuses on the reduction in one particular undesirable trait in a timetable; excessively long unbroken sessions of identical lessons (& therefore with identical subjects). It finds all instances whose duration exceeds the corresponding course's Minimum Consecutive Lessons. Then for each session in turn; reduces its length by unbooking either of the terminal lessons; along with an arbitrary booking, on any other day, & @ a time to which the original lesson might be relocated.

CAVEAT: because Minimise Ratio Of Consecutive Equal Lessons is probably of lower importance than other lesson-criteria & therefore typically weighted lighter, the timetable may be improved by this depletion-strategy, whilst paradoxically increasing the number of long unbroken sequences of identical lessons. One could correct this anomaly by increasing the relative weight of this criterion, but that would merely result in a degradation of the solution in some arguably more important respect; the final solution is a compromise.

Homogeneous Student-View Lesson Mutation

The bookings in the timetable, are divided into groups composed from homogeneous lessons; actually, whether two lessons are considered to be identical, depends on the perspective from which they're viewed, but in this context, it's from the student-body's perspective (i.e. the same teacher, teaching the same subject, @ the same location, but to any student-class). Each set of lessons is unbooked & the timetable reconstructed, before proceeding to the next set.

Since each set of identical lessons must be taught by the same teacher in the same location, unbooking all of them, breaks any routine, allowing the timetable to be reconstructed with an alternative routine, & facilitating the transfer of workload between teachers whose Services intersect.

Incomplete Course Mutation

This depletion-strategy focuses on the reduction in one particular undesirable trait in a timetable; incompletely booked courses. Each course offered by a teacher requires a precisely defined number of lessons per week. Each student-body defines the courses they want to study. If the timetable for any one student-body hasn't booked the required number of lessons, then arguably they may as well not attend any of the lessons for that course. This depletion-strategy mutates the timetable, by unbooking all the lessons for each such incompletely booked course in turn, & for each student-body in turn.

It unbooks them even if; they're booked @ times specifically requested for the course of which they're a part, to permit alternative locations to be used, or for the student-body to associate with a different teacher offering a compatible course; the corresponding courses defines a non-trivial Minimum Consecutive Lessons, because given that all lessons for the course are unbooked, no inconsistent state remains.

Random Lesson Mutation

A small number of randomly selected lessons are unbooked & the timetable reconstructed.

lessons which have been booked @ times specifically requested for the course of which they're a part, are excluded from the random selection, because the probability of a beneficial change to the timetable is too low to justify the effort.

The number of trials used in "Random Lesson Mutation":

The number of random trials to use.

The number of time-slots unbooked in "Random Lesson Mutation":

The number of lessons to unbook in each random trial.

Singleton Student-class Mutation

This depletion-strategy focuses on promotion of one particular desirable trait in a timetable; the temporary merger of student-bodies into student-classes. lessons whose student-classes have been composed from a single student-body, are unbooked from the timetable, which is then reconstructed before proceeding to unbook singleton student-classes for another student-body.

lessons whose course is synchronised, or whose course defines a non-trivial Minimum Consecutive Lessons, or which have been booked @ times specifically requested for the course of which they're a part, are excluded from the selection because the probability of a beneficial change to the timetable is too low to justify the effort. The former are addressed separately by Synchronised Course Mutation.

Split Session Mutation

This depletion-strategy focuses on the reduction in one particular undesirable trait in a timetable; split sessions of identical lessons (& therefore with identical subjects). It finds all lessons which have been booked more than once in any day but with one or more time-slots between, then unbooks one contiguous session. Such split sessions are typically only introduced by the random constructor.

The probability of a beneficial change to sessions which either include a booking @ a specifically requested time, or whose lessons are for a course which is synchronised, is too low to justify the effort; consequently they're excluded.

Student-body Combination Mutation

This depletion-strategy focuses on the reduction in one particular undesirable trait in a timetable; those which contain lessons for any one course, attended by a student-class, which @ various booking-times has been composed from different combinations of student-bodies. So, if student-bodies A & B both require the same subject, one would probably prefer to consistently teach {AB} (or failing that, to teach singleton student-classes, composed from each student-body in isolation), rather than various different combinations of student-body; {A}, {B}, {AB}. Proliferation of student-body combinations, amongst the lessons booked for a course, can be discouraged by applying a relatively large weighting to the lesson-criterion Minimise Student-body Combinations & to the timetable-criterion Minimise Mean Student-body Combinations-per-lesson, but unless all instances of a specific student-body combination for a course, are unbooked simultaneously, a better weighted mean of the timetable-criteria is unlikely to result, & therefore the resulting timetable probably won't be selected as the basis of the next generation. This depletion-strategy mutates the timetable, by finding instances where different student-classes have been booked for any one lesson, then for each student-class in turn, unbooks all the corresponding lessons.

Student-view Timetable-for-day Mutation

For each student-body in turn, then for combinations of the specified number of days, all lessons are unbooked & the timetable reconstructed. In the absence of any specification, then combinations of any number of days will be tried.

Lessons whose course is synchronised or which have been booked @ times specifically requested for the course of which they're a part, are excluded because the probability of a beneficial change to the timetable is too low to justify the effort.

This creates the contiguous space required to book courses which specify a non-trivial Minimum Consecutive Lessons, & when the specified number of days exceeds one, the ability to relocate them to another day.

The number of days used in "Student-view Timetable-for-day Mutation":

The number of days to simultaneously unbook when deploying the Student-view Timetable-for-day Mutation depletion-strategy. In the absence of any specification, then combinations of any number of days will be tried.

Student-View Timetable-for-week Mutation

Similar to Random Lesson Mutation, but the student-bodies are mutated independently. A small number of randomly selected lessons are unbooked from the timetable of one student-body & the timetable reconstructed, before proceeding to the next student-body.

lessons which have been booked @ times specifically requested for the course of which they're a part, are excluded from the random selection, because the probability of a beneficial change to the timetable is too low to justify the effort.

The number of trials used in "Student-View Timetable-for-week Mutation":

The number of random trials to use when deploying the Student-View Timetable-for-week Mutation depletion-strategy.

The number of time-slots unbooked in "Student-View Timetable-for-week Mutation":

The number of lessons to unbook in each random trial when deploying the Student-View Timetable-for-week Mutation depletion-strategy.

Synchronous-lesson Mutation

The bookings in the timetable, are divided into synchronous groups of otherwise arbitrary lessons. Each set of lessons is unbooked & the timetable reconstructed, before proceeding to the next set. This is a rather arbitrary procedure, neither specifically addressing an undesirable trait, nor attempting to promote some desirable metric, but it is useful when deployed in combination with depletion-strategies which do address specific problems, which in isolation typically don't liberate sufficient free space to be effective.

lessons which have been booked @ times specifically requested for the course of which they're a part, & lessons forming a consecutive sequence whose minimum length has been configured, are excluded from each group, because the probability of a beneficial change to the timetable is too low to justify the effort.

Reconstruction:

The reconstruction-phase can (for any depletion-strategy) be performed by the application using either of two constructors;

Deterministic Constructor:

Uses the weighted mean of a set of lesson-criteria in an attempt to select the best lesson to place in each time-slot.

Random Constructor:

Merely selects a lesson randomly, from those which are viable.

The former is far more effective, but the optimum timetable might only be reached by means of some sub-optimal lesson-selections, which can only be taken by the random constructor.

Fecundity-decay Ratio:

The factor (in the closed unit-interval [0,1]), by which the fecundity of the breeding-program for future generations is multiplied (& therefore reduced), when the population-diversity ratio falls beneath Minimum Population-diversity Ratio.

Each generation of the evolution of the timetable, involves breeding a population of candidate-solutions (of size fecundity), then sparking multiple threads, to evaluate the fitness of each. This scales well on a multi-core machine, but if too many candidates are generated, inefficiency begins to creep in (even if CPU-cores are available to support them); either because more superior solutions are found, than are selected as parents for a subsequent generation; or because some mutations are identical, resulting in duplication of effort. Consequently, the initial fecundity is reduced by a feedback-loop, which monitors the population-diversity ratio of the candidates, & should it be observed to fall beneath a critical threshold, the fecundity of the breeding-program for future generations, is decreased by the specified factor.

Minimum Population-diversity Ratio:

The population-diversity ratio (in the closed unit-interval [0,1]), beneath which a reduction in the fecundity of the breeding-program for future generations is triggered, by a factor of Fecundity-decay Ratio.

The number of Initial Scouts:
The evolutionary process

To understand the process of evolving the timetable, it helps to imagine the solution-space as a misty mountainous terrain in which one is attempting to find the highest point. We can peer around the current location & select the direction of greatest positive gradient, but may become trapped by this simple procedure @ the top of a small hill; even though a higher point exists, there is no path of monotonically increasing height that leads there. A better strategy might be to dispatch scouts in many directions, & on their return, relocate to the highest place found. One might further improve this strategy by implementing it recursively, i.e. by allowing the scouting-groups to fragment after exploring some distance & dispatch their own smaller scouting-groups.

Translating this concept back to the problem in hand, each generation of the evolution of the timetable, involves breeding a population of candidate-solutions using the current solution as a seed, from which the best (even when less fit than their parent) few are selected. Each selected scout is used independently to seed the breeding of a sub-generation of candidates from which one fewer scouts are then selected. The resulting family-tree, sprouts fewer branches with each successive generation, & so eventually withers. The best from all the scouts (nodes) in this family-tree, is then compared with the fitness of the original parent; & is either found to be fitter, & consequently used to re-start this process (i.e. this paragraph), or is found to be less fit, & the evolutionary process is terminated.

Number of Initial Scouts Number of Inferior Generations Tolerated Breeding-sessions Total number of Scouts Behaviour
unspecified 0 variable variable

A variable number of scouts is used. Each candidate comparing equal best, & also better than their parent, is selected. This results in monotonically increasing fitness (equivalent to a hill-climbing algorithm), has the disadvantage that it can become trapped in a local maximum solution & may result in a very wide search, but is typically quite effective.

1 0 1 1

Only the best child is selected from the single breeding-session & compared with the parent; no inferior candidates can propagate to subsequent generations. This results in monotonically increasing fitness (equivalent to a hill-climbing algorithm), & has the disadvantage that it can become trapped in a local maximum solution.

2 1 3 4

The best two scouts are selected from the breeding-session in the first generation; & from each independently bred second generation, the single best scout is selected. This differs conceptually in that one generation of inferior children is tolerated; though to be successful, @ least one of the four scouts (two children & two grandchildren), must be fitter than the original parent.

3 2 10 15

The best three scouts are selected from the breeding-session in the first generation; & from each independently bred second generation, the best two scouts are selected; & from each independently bred third generation, the single best scout is selected. Two inferior generations are tolerated; though to be successful, @ least one of the fifteen scouts (three children, six grandchildren & six great-grandchildren), must be fitter than the original parent.

n n − 1 Xn = 1 + n × Xn−1 Yn = n × (1 + Yn−1)

Execution-time is approximately proportional to (Xn ÷ n), which is approximately (n - 1) !. Though the best scout is never worse than that found from fewer initial scouts, the improvement doesn't typically justify the additional effort; except that it makes the evolutionary process less prone to premature termination than when using a smaller number of scouts, where there's a greater chance that none are better than their parent. Such levels result in a wider search of the solution-space, & may be employed in desperation when tackling timetable-problems which have resisted one's initial solution-attempt.

Lesson-criteria Weights

When constructing a timetable, the solution-algorithm determines the set of all possible lessons, which may be booked @ a specific time-slot, then selects the best according to the weighted mean of various criteria. These criteria are merely an ad-hoc heuristic, used to construct a timetable which matches user-requirements as closely as possible.

One can vary each fractional weight within the closed unit-interval [0,1], which @ the lower bound (the default value) disables the associated criterion. Even when the maximum weight is applied to any criterion, the solution algorithm may still trade it off against other criteria, & in this respect, each criterion is merely a soft constraint; cf. hard constraints like the subjects a student-body wants to study.

Lesson-criteria

Are Resources Reused:

A lesson is preferred, if the required resources (locations & teachers) are shared with other student-bodies, by temporarily merging them into a single larger student-class.

Greatest Minimum Consecutive Lessons:

A lesson is preferred, if the course's Minimum Consecutive Lessons is larger, since this makes it harder to book later, into the smaller spaces remaining.

Greatest Remaining Course-lessons:

A course is preferred, if it has greater unbooked lessons, since a course requiring only one lesson can be booked on any day.

Greatest Synchronised Course Set-size:

A course is preferred, if it is a member of a larger set of synchronised courses; it seems prudent to book the most constrained course's lessons, early.

Is Core Knowledge-requirement:

A subject is preferred, if it is categorised by the student, as a core Knowledge-requirement.

Is Specialist In Topic:

A teacher is preferred, if their Specialty Topic matches the proposed Topic.

Match Course Class-size To Location-capacity:

A location is preferred, the closer its Capacity matches the course's optional Maximum Class-size; provided it's sufficient.

Maximise Relative Facility-utilisation:

A location is preferred, the more its facilities are used; cf. Minimise Waste Of Scarce Facilities, which tries to make a distinction based on the type of the wasted facility.

Maximise Student Class-size Over Course Class-size:

A course is preferred, the more its Maximum Class-size is filled by the proposed student-class.

Maximise Student Class-size Over Location-capacity:

A location is preferred, the more its Capacity is filled by the proposed student-class.

Minimise Booking At Another Course's Specified Time:

A booking-time is preferred, if there's minimal probability that courses for the student-body's other Knowledge-requirements, will require that specific time; the probability becomes a certainty for those Knowledge-requirements which can only be satisfied by one course.

Minimise Booking Of Location By Other Teachers:

A location is preferred, when booked by the fewest other teachers.

Minimise Deviation From Timeslot-request:

A course is preferred, if it is booked closer to any Ideal-timeslot request

Minimise Inter-campus Migrations of Students:

A course is preferred, if inter-campus migrations of students are minimised.

Minimise Inter-campus Migrations of Teachers:

A course is preferred, if inter-campus migrations of teachers are minimised.

Minimise Student-body Combinations:

A lesson is preferred, when the number of student-body combinations is minimised.

Minimise Teachers' Locus Operandi:

A location is preferred, if the size of teacher's locus-operandi is minimised; based merely on the number of distinct locations booked, rather than the distance between them.

Minimise Waste Of Scarce Facilities:

A lesson is preferred, if the location's unused facilities, are commonly available elsewhere; cf. Maximise Relative Facility-utilisation, which treats all facilities equally.

Optimise Lesson-criteria Weights

Because the concepts various lesson-criteria aim to measure are rather esoteric, appropriate weights are hard to assign, & therefore one has the option to attempt to optimise them automatically. These fields govern repeated random mutation of the specified Lesson-criteria Weights, to maximise the weighted mean over the values of heterogeneous timetable-criteria, when evaluating the Initial Deterministic Timetable.

  • No change is made to Lesson-criteria Weights which were originally set to 0.
  • If Traversal Order has been specified, then the optimisation will be performed on the specified subset of rasters.
  • The resulting weights could be copied to other similar problems, where they may be reasonable initial values.
  • This optional procedure can only work when it is possible to improve the resulting solution by changing Lesson-criteria Weights; if the solution-space is too small to allow the weights of lesson-criteria to drive the solution towards a better place, then this process will merely take a long time.
  • It's also necessary that the weights of timetable-criteria are well chosen, otherwise the weights of lesson-criteria will evolve towards the wrong target.
  • The basis for this optimisation-process is rather flimsy.

Fields

nTrials:

The number of random trials to use when attempting to improve the specified Lesson-criteria Weights. The required number of trials typically depends on how good the specified weights are. More trials will typically result in a greater improvement, but the returns diminish, & for a large problem each trial is computationally expensive.

changeMagnitude:

The magnitude of the random change applied independently to each lesson-criterion weight. This positive number permits an increase or decrease by a factor of up to (1 + x) in the weight of a lesson-criterion.

reductionFactor:

The factor in the closed unit-interval [0,1], by which changeMagnitude is multiplied after each success, resulting in an exponential decline in the magnitude of the mutations to which the Lesson-criteria Weights are subjected.

useMeanOverRasterScans:

Whether to accept a proposed set of Lesson-criteria Weights on the basis of the mean (as opposed to the maximum) over the specified raster-scans, of the weighted mean over all heterogeneous timetable-criteria. Use of the mean over the raster-scans reduces the chance that weighted mean over heterogeneous timetable-criteria for the initial deterministic timetable was a freak result, & as such an inappropriate set of Lesson-criteria Weights with which to attempt to evolve the solution. Use of the maximum over the raster-scans will result in a good initial deterministic timetable, but it may not perform well during the subsequent evolution.

Timetable-criteria Weights

The various Evolution-strategies, are from any parent timetable, used to breed a population of alternative candidate-solutions, from which the best according to a weighted mean over various criteria, can be selected. These criteria are merely an ad-hoc heuristic, used to select a timetable which matches user-requirements as closely as possible.

One can vary each fractional weight within the closed unit-interval [0,1], which @ the lower bound (the default value) disables the associated criterion. Even when the maximum weight is applied to any criterion, the solution algorithm may still trade it off against other criteria, & in this respect, each criterion is merely a soft constraint.

Timetable-criteria

Maximise Compliance With Free-period Preferences:

A timetable is preferred, when it complies with any Free-period Preference of student-bodies & teachers.

Maximise Mean Ratio Of Student Class-size To Location-capacity:

A timetable is preferred, when the mean over all bookings, of the ratio of the size of the student-class to the location's Capacity, is greatest.

Maximise the Mean Size of Student-classes:

A timetable is preferred, when the mean size of student-classes, is greatest.

Maximise Synchronisation Of Synchronised Courses:

A timetable is preferred, when the lessons of synchronised courses are consistently synchronised.

Maximise Weighted Mean Student-body Utilisation-ratio:

A timetable is preferred, when the mean over all student-bodies, of the ratio of the time currently booked to the total time in their working-week, is maximised. It doesn't distinguish between core & optional Knowledge-requirements like Minimise Mean Ratio Of Incompletely Booked Core Knowledge & Minimise Mean Ratio Of Incompletely Booked Optional Knowledge, but it does value partially booked courses.

Minimise Average Absolute Deviation From Ideal Timeslot-request:

A timetable is preferred more, the closer lessons are booked to any Ideal-timeslot request for their course.

Minimise Dispersion Of Student Free-periods per day:

A timetable is preferred, when each student-body's free periods are spread evenly across their working-week.

Minimise Dispersion Of Teacher Free-periods per day:

A timetable is preferred, when each teacher's free periods are spread evenly across their working-week.

Minimise Dispersion Of Teacher-workload:

A timetable is preferred, when the relative workload between all teachers, is similar.

Minimise Mean Inter-Campus Migration Of Students:

A timetable is preferred, when the average over all students, of the number of inter-campus migrations in a week, is minimised.

Minimise Mean Inter-Campus Migration Of Teachers:

A timetable is preferred, when the average over all teachers, of the number of inter-campus migrations in a week, is minimised.

Minimise Mean Location-changes Of Teachers:

A timetable is preferred, when the average over all teachers, of the number of changes in their location during the week, is minimised; cf. Minimise Mean Locus Operandi Of Teachers, which merely counts the number of distinct locations used.

Minimise Mean Locus Operandi Of Teachers:

A timetable is preferred, when the average over all teachers, of the size of their locus-operandi, is minimised; based merely on the number of locations, rather than the distance or the number of changes, between them.

Minimise Mean Ratio Of Incompletely Booked Core Knowledge:

A timetable is preferred, when the average over all student-bodies, of the ratio of incompletely booked core Knowledge-requirements, to all requirements, is minimised. All incomplete courses are valued equally, regardless of the extent; cf. Maximise Weighted Mean Student-body Utilisation-ratio.

Minimise Mean Ratio Of Incompletely Booked Optional Knowledge:

A timetable is preferred, when the average over all student-bodies, of the ratio of incompletely booked optional Knowledge-requirements, to all requirements, is minimised. All incomplete courses are valued equally, regardless of the extent; cf. Maximise Weighted Mean Student-body Utilisation-ratio.

Minimise Mean Student-body Combinations-per-lesson:

A timetable is preferred, when the average number of combinations of student-body per lesson-definition, is minimised; ideally a student-body always studies a subject, in a class composed from the same other student-bodies.

Minimise Ratio Of Consecutive Equal Lessons:

A timetable is preferred, when blocks of consecutive identical lessons are booked, whose length least exceeds the course's Minimum Consecutive Lessons.

Minimise Ratio Of Separated Equal Lessons Within Any Day:

A timetable is preferred, when the lessons of any course, are on any day, booked in one contiguous session.

The evolution-algorithm uses the weighted mean of these criteria, to select from candidate timetables, in a search for the optimum. This raises the question of whether it's valid to compare the observed value of criteria which represent utterly different concepts; how can a criterion which has the dimensions of time, meaningfully be included in a weighted mean with another criterion which has dimensions of length ? To make these criteria comparable, they're all represented as dimensionless quantities, mapped into the closed unit-interval [0,1]; e.g. by dividing by their maximum theoretical value. This should reduce the question of what weight to apply to each, to the simple question of their relative significance to the user, in the context of the current problem; the most important could be set to 1, & the others proportionately less.

Regrettably this seldom results in the desired outcome, because within a typical population of candidate-solutions, the observed value of some criteria may range across the entire unit-interval, while the observed value of others may be constrained to a minuscule portion. Consequently, within the domain of this population of candidates, relatively large gains are possible for some criteria, typically @ the expense of others, irrespective of the user-defined significance of the corresponding concepts. The same parasitic effect may also result between criteria, even when the values typically found in the candidate population, range across spans of similar length, but do so in different profiles, creating zones of sensitivity to the underlying concept they measure. Whilst one may compensate for the former effect, by adjusting the weight applied to specific criteria, that regrettably decouples the weight, from the user-defined significance of the concept being measured; compensating for the latter effect would require a more complex mechanism that a single weight, & so far this hasn't been addressed. Some criteria may result in contrary views on the fitness of a timetable; e.g. Minimise Ratio Of Consecutive Equal Lessons downgrades a timetable when the number of consecutive equal lessons exceeds the course's Minimum Consecutive Lessons, whereas Minimise Mean Location-changes Of Teachers prefers the lack of a change to the teacher's location & Minimise Mean Inter-Campus Migration Of Students prefers the lack of any requirement to migrate to another campus.