0160-5682/90 $3.00 + 0.10 Copyright © 1990 Operational Research Society Ltd
J. Opl Res. Soc. Vol. 41, No. 1, pp. 39--47, 1990
Printed in Great Britain. All rights reserved
Timetabling University Examinations DAVID JOHNSON Department of Management Studies, Loughborough University The problem of timetabling examinations is one which is faced by most educational institutions, with the problem becoming particularly acute in institutions ofhigher education. The situation may be formulated generally as a 0--1 integer programming problem but, in common with a number of other timetabling problems which have been reported, a heuristic approach is more practical and produces an acceptable solution. The procedure described takes account of the obvious constraints imposed by examinationroom availability and capacity, and the need to avoid clashes between common examination papers. In addition, the examinations are scheduled such that the students are faced with a minimum number of occasions when two papers have to be taken in the same day and, for ease of marking, the larger courses are examined early. A computer program to implement the heuristic was developed and was found to produce a better timetable than the previous manual procedure as well as a considerable saving in clerical effort. Key words: annealing, heuristics, integer programming, timetabling
INTRODUCTION In virtually all educational institutions students must sit examinations periodically, those examinations being set either by the institution itself or by some external body. With external examinations, the examination timetable is devised by the relevant examining body, and because the examinations are usually taken by large numbers of candidates on an area or national basis, there would generally be just one examination paper being sat at any one time. The main question that arises in scheduling such examinations is the order in which the various papers shall be taken, an issue which is usually dictated by educational and, to some extent, administrative considerations. In any event, once the most appropriate sequence has been decided, that same sequence can probably be used on subsequent occasions with little or no change. In the case of internally set examinations, it is often possible to economize on the use of resources such as examination rooms and invigilators by taking advantage of the fact that not all students will be taking each paper. In secondary school, the amount of choice that students have in the subjects they take is limited and so there may be little opportunity to 'double up' on examination papers. However, as students progress through the educational system, the amount of choice that they have tends to increase, and it becomes increasingly possible to schedule more than one subject at one time. The fact that no students are taking both Biology and French, for example, means that those two subjects can be examined at the same time, possibly in the same examination room and with just one invigilator. However, even in the sixth form, the scheduling of school examinations is not a particularly difficult task because the number of pupils in any one year, and the number of subjects that they take, will be relatively small. In contrast, the problem becomes much more formidable in a higher educational institution because of the much greater number of students and courses, and the degree of choice available to the students. In a typical university, for example, there will be hundreds of courses and thousands of students to be examined at least once, and perhaps twice, a year. In this situation, it is absolutely essential that the examinations are scheduled efficiently if the whole examination process is to be completed in a relatively short period of time. THE SITUATION AT USP The University of the South Pacific (USP) is a relatively small university serving 11 countries of the South Pacific. The University operates from two campuses, one in Fiji and the other in Western Samoa. The main Fiji campus houses the three large schools of Pure and Applied Science, Social and Economic Development, and Education and Humanities. The fourth school (Agriculture) is based in Western Samoa and operates largely independently, with very little interaction of either students or courses between the two campuses. The University has about 2500 full-time (internal) students, of which about 95% are based in Fiji. In addition, the University provides distance education packages for part-time students 39
Operational Research Society is collaborating with JSTOR to digitize, preserve, and extend access to Journal of the Operational Research Society. ® www.jstor.org
Journal of the Operational Research Society Vol. 41, No.1
studying in their own countries. There are about 5000 'extension' (or external) students on a range of degree, diploma, certificate and continuing education programmes. These students make up what is, in effect, the University's fifth school (Extension Studies), which is also administered from the Fiji campus through local centres in each country. The University has, therefore, three essentially distinct groups of students, namely: internal (Fiji) internal (Western Samoa) external (Regional)
2350 150 5000.
The only real link between these three groups is that internal students in Fiji occasionally take extension courses if they wish to include in their programme of study a course which does not fit on the timetable with their other on-campus courses. This mainly arises when previously failed courses have to be repeated. The same situation does not occur in Western Samoa, however, because no Agriculture courses are offered by extension. The University operates on a semester system, with two semesters of 18 weeks in each year. Virtually all courses offered by the University are completed in one semester and examined during the last two weeks of that semester. Examinations are therefore held twice a year, in June and November, with two examination sessions each day (morning and afternoon) for 10 days, making a total of 20 sessions on each occasion. In a typical semester, there are about 150 on-campus courses and as many as 70 or 80 extension courses offered from the Fiji campus, all of which must be examined during the 20 available sessions. There are therefore about 11 different examination papers per session on average, with as many as 20 on some occasions. Most full-time students take either three or four courses per semester, whereas part-time students typically take only one course, or occasionally two. The scheduling of the extension examinations is therefore less of a problem because not only are there fewer courses offered, but also there are fewer potential conflicts caused by students taking more than one course. However, the extension examinations cannot be scheduled independently of the on-campus examinations because of those students who are taking both on-campus and extension courses. In addition, the same course is occasionally offered both on-campus and by extension, and in such cases there · would usually be a common examination paper for the two courses. Such examinations must therefore be scheduled concurrently, and for practical purposes can be considered as one combined course. In summary, around 200 examinations have to be scheduled on the Fiji campus at the end of each semester. This will involve about 2350 full-ti:--1e students as well as those part-time students living in Suva, where the Fiji campus is located. EXAMINATION CONSTRAINTS The preparation of the examination timetable each semester is essentially a routine task, albeit a rather time-consuming one. A number of factors/constraints must be considered when drawing up the timetable: 1. The timetable must avoid all conflicts, so that no student is faced with having more than one examination at the same time; otherwise special invigilation arrangements would have to be made. In practice this is not difficult to achieve if enough examination-room capacity is available. 2. All examinations should be completed in at most 2 weeks (20 sessions). This is an important consideration because time has to be allowed for marking scripts and processing the results before the beginning of the next semester or the end of the academic year. The university administration is firmly of the view that the examination period cannot easily be extended. 3. It must be possible to accommodate all the candidates in the various examination rooms available. In theory, many examination rooms can be made available, but in practice only the larger rooms tend to be used, for ease of administration and to avoid excessive invigilation requirements. The use of smaller rooms is more difficult to organize and administer, and involves a proportionately larger number of invigilators. The University has one large hall (a gymnasium), which can accommodate 400 students under examination conditions. Other large lecture rooms are used, mainly for extension studies examinations, but the aim is to confine the full-time students to the gymnasium if at all possible. 40
D. Johnson- Timetabling University Examinations
4. Those examinations with a larger number of candidates should come earlier in the examination period to allow the maximum time for marking. The number of students per course varies from as many as 400 for certain common first-year courses, down to four or five for some final-year options. To allow sufficient time to process the results through the various boards and committees, all scripts must be marked by the middle of the week following the examinations. For those examinations coming at the end of the period, only 4 days (including the weekend) are available for marking, and it would therefore be unrealistic to expect (say) 400 scripts to be marked in so short a time. Lecturers with large courses expect their examinations to be as early as possible, and certainly within the first week. 5. Where a student is taking more than one examination, these should be spread out throughout the 2 weeks if at all possible so that there is some time for preparation before each examination. In practice this is virtually impossible to achieve for all students, but at the very least they should not have to take two examinations on one day, and perhaps also an examination on the morning after one on the previous afternoon. Again, given enough examination-room capacity, these 'same day' examinations can usually be eliminated, but with limited capacity it becomes more of a problem. Clearly the first three constraints are 'necessary', or essentially so, whereas the last two constraints are 'desirable' from a lecturer (in the case of 4) or a student (in the case of 5) point of view. Unfortunately, however, constraints 4 and 5 are to a large extent conflicting in that many students are (by definition) taking the larger courses which we wish to schedule at the beginning of the period (during the first week). Their examinations will therefore be compressed into a 1-week period, rather than being spread out over the full 2 weeks. Obviously some compromise between lecturer and student convenience has to be found.
THE CURRENT EXAMINATION-SCHEDULING PROCESS The scheduling of examinations is done by an administrative assistant in the University's academic office. The whole process usually involves 2 or 3 weeks' work, mainly spent cross-checking combinations of examinations against a 'clash list' produced by the student registration/record system. This clash list shows the number of students (if any) taking all combinations of courses and is a routine output from the University's computer system. It is usually possible to schedule the examinations to avoid all known clashes, although problems do sometimes arise if a student changes course after the start of the semester and the computer record has not been appropriately updated, so that the clash list is out of date. If necessary, extra rooms are used in addition to the gymnasium to enable the larger courses to be fitted into the first week, so that a schedule is obtained which essentially meets the first four constraints listed above. What is not explicitly taken account of is the last constraint, and there are frequent student complaints about examinations being bunched into 2 or 3 days. It is seldom possible to do anything about such cases because of the problems of rearranging an already complicated timetable. More realistically, however, the person responsible for the examination timetable does not want to create a precedent whereby students think that the timetable can be rearranged for their convenience. As a result, the only changes which are usually made to the initial draft are as a result of unforeseen examination clashes and, occasionally, to accomm'bdate a lecturer's request for an alternative examination date for a particular course. It would clearly be unrealistically time-consuming routinely to check the spread of every single student's examinations. However, as an indication of the performance of the manual approach, the number of instances of consecutive examinations was determined for the semester I, 1988 examination timetable, that being the last occasion on which a totally manual approach was used. The results were as follows: Consecutive examinations a.m.-p.m. (i.e. same day) p.m.-a.m. (i.e. next morning) 41
Number 209 477 686
Journal of the Operational Research Society Vol. 41, No.1
The next-morning situation does not include the intervening weekend, i.e. Friday afternoon of week 1 followed by Monday morning of week 2. This is clearly a less important case than the same-day situation as the students have an evening (and perhaps all night!) to prepare for their next examination. It is at least reassuring to see that there are fewer same-day examinations which probably indicates that some attempt is being made to avoid this situation. Nevertheless, almost 10% of full-time students were faced with two examinations on the same day, and in one or two unfortunate cases, that may have occurred twice. A LINEAR PROGRAMMING MODEL In common with a number of similar cases which have been reported (for example, Eglese and Rand/ Gosselin and Truchon 2 and Wilson 3 ), the problem can be formulated as an integer linear programming model. Let X 1,. be a (0, 1) variable such that X 1,.
= 1 if course i is allocated to room r in sessions, 0 otherwise,
where there are K courses, R rooms and 20 sessions; i.e. i = 1, ... , K, r = 1, ... , R and s = 1, ... , 20. If we assume that there is a room available which can accommodate the largest course so that no course has to be allocated to more than one room, then the following constraints must be satisfied. (i) Each course must be allocated to one particular room in a particular session; i.e.
R
20
L LX
r= 1 s= 1
irs
= 1
for all i.
(ii) The courses allocated to each room must not exceed the room capacity (Q,) in any session; i.e.
K
L
i=1
for all r, s,
N 1 X 1,.:::;; Q,
where N 1 is the number of students on course i. (iii) There may be an upper limit (Lr) on the number of courses which can be allocated to a particular room in any session. For example, it may be administratively inconvenient to have more than 10 courses being examined simultaneously in a given room. This leads to constraints of the form K
}:X1,,:::;; L,
for all r, s.
i=1
(iv) No courses which have common students can be examined simultaneously. If the number of students taking both courses i andj is denoted by Cii (the clash matrix), then R
L (X irs + Xjrs} :::;; 2 -
r= 1
bij
for all i < j, s,
where b;j = 1 if cij > 0,
= 0 otherwise, so that the left-hand side is limited to either 1 or 2, depending on whether courses i and j clash or not. As an objective function, we could minimize the overall number of consecutive examinations (i.e. same day and next morning) or we could take either of these individually, the approach being essentially the same in each case. To do this, it is necessary to introduce an additional set of variables Y;i•, where
Y;i•
=
1 if courses i and j are examined in sessions s and s + 1 respectively,
= 0 otherwise. 42
D. Johnson- Timetabling University Examinations The total number of consecutive examinations is then given by K-1 K 19 }: }: }: cij Y;j. (MINIMIZE) i=1 j=2 s=1 (i
•* 10)
whereas the number of same-day examinations is K-1 K L L C;iY;j1 + Y;j3 + + Y;j(19)) (MINIMIZE) i=1 j=2 (i are equal to 1 for any r. It is therefore necessary to introduce additional constraints of the form 0
(v)
R
L (X;,.+ xjr(s+1))::::; Y;j. +
r=1
1
0
0
fori
R
L (X;,.+ xjr(s+1)) ~ 2Y;j.
fori
(vi)
A HEURISTIC APPROACH The construction of examination timetables by computer based on appropriate heuristics was first reported in the 1960s by Cole4 and Broder, 5 and subsequently developed for application in particular university environments by, for example, Wood 6 and Foxley and Lockyer. 7 The early papers were primarily concer-ned with computing efficiency on what were, by today's standard, relatively primitive machines. Later papers, particularly Wood, 6 began to introduce more realistic considerations, such as the need to space out each student's examinations and avoid, if possible, the occurrence of two examinations within a 24-hour period. The information from which examination timetables are constructed typically comes from two distinct sources. First there is the basic information about course registrations which comes from the student record/registration system. This provides (i) the 'class counts' list, which gives the number of students (N;) registered for each course. (ii) the 'clash matrix', which gives the number of students (C;) taking all possible combinations of courses. Logically, the class counts should constitute the diagonal terms of the clash matrix (C;J However, as a result of the way in which the student registration system at USP has been designed, the clash matrix is produced as a list of the non-diagonal elements of the matrix, with the class counts being obtained from a separate file. The first task is therefore to combine these two lists into one composite clash-matrix file where C;i = N;. The second source of information is that provided by the person producing the timetable. In particular, (i) which courses are not to be included in the examination timetable, as some of the courses appearing in the clash matrix may not have an end-of-semester examination; 43
Journal of the Operational Research Society Vol. 41, No.1 (ii) which courses are examined in special rooms, such as drawing offices or laboratories; although these. courses have to be timetabled, they do not take up any space in the main examination rooms and so, for timetabling purposes, the number of students is effectively zero; (iii) how many examination rooms are available and their capacities in terms of both the number of seats available (Q,) and the number of distinct courses which can be accommodated (L,); (iv) the maximum number of examination sessions which are to be used; this will generally be 20, but occasionally there may be a need to use less than this number if, for example, a public holiday were to occur during the examination period. The procedure developed at USP involves two main stages similar to the procedure described by Eglese and Rand. 1 First an initial feasible solution is sought by assigning the courses in a predetermined order to the available examination sessions. Secondly, if an initial feasible solution has been found, improvements to the timetable are sought by re-ordering the sessions to reduce the number of same-day examinations and to ensure that the larger examinations come early on. The order in which the courses are initially assigned is determined by a 'difficulty' factor. The two things which tend to make a course difficult to timetable are the size of the course and the extent to which that course clashes with other courses. In general, it is more difficult to timetable a large course (because of space constraints) or one which clashes with many other courses, and so the 'difficulty' of course i was defined as where M; is the number of other courses with which course i clashes, and a is a weighting factor to reflect the relative importance of the two components. Alternatively Z; = aC;;
+
K
L bii•
where bij = 1 if cij > 0, = 0 otherwise.
j=l
U*il
Changing the value of the weighting factor a will cause the courses to be assigned in a different order and hence produce a different initial timetable. In fact, quite small changes in a can produce markedly different timetables, and as a result any number of distinct timetables can be generated simply by varying a. Experimentation showed that increasing a from 0 to 0.5 in steps of 0.025 usually produced a good range of timetables from which to choose. In practice, however, the most appropriate range of values for a will depend on the size of the courses involved and the overall extent to which they clash. Having determined the order in which the courses are to be allocated, each course is assigned in turn to a particular room and session. For each course, those sessions which can accommodate that course are identified, these being the ones where there is sufficient capacity remaining and where those examinations that have already been assigned do not clash with the current one. The session chosen is the one which leads to the smallest increase in the number of same-day examinations, with the first available session being used in the event of a tie. The room chosen is the one with the least number of available seats, subject to its being able to accommodate the course in question. Each course is assigned to a single room wherever possible, but if necessary a course may be split between two or more rooms. This will tend to occur only in unavoidable cases as the courses which need to be split will be the larger ones, and these will generally be ,6lSsigned first when there is most choice of rooms available. There is, of course, no guarantee that an acceptable timetable will always be found. If a particular course cannot be allocated to any session so as to avoid clashes with other courses, then the current value of a does not produce a feasible timetable and another value of a is tried. The result of the first stage is therefore a feasible timetable which assigns each course to one of the 20 sessions. The second stage of the procedure is to try and improve this timetable by altering the order in which the sessions take place. The problem has therefore been reduced to one of having 20 defined sessions which have to be arranged in a particular order to minimize the chosen criterion, i.e. the number of same-day examinations. The first step of this second stage is to calculate the session clash matrix (as opposed to the course clash matrix), which gives the number of students having examinations in any given pair of
44
D. Johnson- Timetabling University Examinations
sessions. In theory it would be possible to determine the minimum number of same day examinations for all 20! possible permutations of the 20 sessions, but a more practical (i.e. less timeconsuming) approach is to use some sort of search process to move towards an optimum permutation. The search procedure used is a type of annealing algorithm as described by Kirkpatrick et a/. 8 The algorithm works by moving from one solution (i.e. permutation) to a neighbouring solution, which in this case is generated by interchanging a randomly chosen pair of sessions. If. this change leads to an improvement in the chosen objective (i.e the number of same-day examinations), then the change is accepted. If the change does not lead to an improvement, it may be accepted provided that the new solution is only 'marginally' worse than the present one. . This acceptance of moves which do not necessarily lead to an immediate improvement is the distinguishing feature of annealing algorithms, and is designed to enable the search to overcome local optimum solutions and move towards a global optimum. Specifically, if the new solution results in an increase of d in the objective (which we assume is being minimized), then the new solution is accepted with probability e- dfT, where T is a control parameter which decreases monotonically with each successive iteration. In common with the application described by Eglese and Rand,l the value ofT is determined iteratively, as suggested by Lundy and Mees, 9 i.e. at iteration i:
I;= J;_tf(1
+ bTi_ 1).
This means that the probability of accepting a change which leads to an increase in the number of same-day examinations will decrease with each iteration until effectively only changes which decrease the number of same-day examinations will be accepted. To implement this algorithm, it is necessary to specify the initial value of T (i.e. T0 ), the value of b and the number of iterations to be performed. Lundy and Mees 9 suggest that T0 ~ U, where U is an upper limit on the change in the objective function between neighbouring permutations, and b ~ U - 1. Experimentation with a range of values of T0 and b showed that T0 = 5000 and b = 0.0001 produced satisfactory convergence in reasonable time for a set of trial problems where the true optimum had been determined for all possible permutations. Furthermore, convergence had effectively occurred after about 3000 iterations, after which little change to the objective function was observed. The 'optimum' solution was therefore taken as the permutation of sessions which had produced the least number of same-day examinations throughout the 3000 iterations, which was not necessarily the final solution obtained. The final step is to arrange the 10 days of the examination period into an appropriate order. Rearranging the days would obviously not affect the number of same-day examinations (although it would alter the number of next-morning examinations). At this stage it would be possible to arrange the days such that th~ number of next-morning examinations is minimized as a secondary objective, but it was decided that a more important consideration was to ensure that the larger examinations came first to allow more time for marking. Accordingly, the days were finally arranged in order of the largest course scheduled for each day. This then gives a final examination timetable where each course is allocated to a morning or afternoon session over a 10-day period. The details of this timetable are output in terms of the total number of same-day examinations and the largest course being examined on each of the 10 days. The timetable planner now has a chance to save the timetable to a file if it appears to be worthy of more detailed consideration, after which the program moves on to create another feasible timetable for a different valu't: of the weighting constant a. RESULTS The procedure was programmed in BASIC to run on a DEC MicroVax system, that computer being chosen rather than a desk-top computer largely because it runs the student registration system which provides the two basic data files which are required to set up the clash matrix. The program generally takes about 5 minutes to run, and each run produces up to 20 feasible timetables corresponding to values of a = 0.025(0.025)0.5. Not all of these timetables would be worthy of detailed consideration, and the timetable planner would typically end up saving between five and 10 of them to look at in more detail. 45
Journal of the Operational Research Society Vol. 41, No.1
As an indication of how good a timetable could be produced, the program was run for semester I, 1988. This was the most recent set of examinations which had been timetabled manually, and the only previous semester for which a computerized record of student registrations and clashes was still available. On this occasion there were 125 full-time courses to be examined in a 10-day period, and two large examination rooms with capacities of 200 and 350 had been used rather than the gymnasium. Altogether a total of 6229 sittings were involved, and so there was a reasonable amount of space available, with the examination rooms being used, on average, at (200
6229
+ 350)
X
20
X
100 = S?%
capacity. In fact, during the second week of the examination period, only the larger room was used on a number of occasions, and so the effective capacity utilization was about 65%. However, even with such a relatively large number of seats available, there were, as mentioned earlier, 209 instances of students having to sit two examinations in one day. Using a computer-produced timetable, it would have been possible to schedule the examinations over a 2-week period with as few as 11 same-day examinations. As the number of examination sessions decreases, the number of same-day examinations necessarily increases, but even if the examination period was reduced to 7 days, there would still be only 105 instances of same-day examinations produced by the computer. From a student point of view, it would be politically unwise for the University to be seen to be reducing the examination period by 30%, even though this could have resulted in half as many same-day examinations as actually occurred. A much more relevant outcome is that the number of same-day examinations could be reduced by about 95% if a computerized schedule was used covering the full 10-day period. Discussions with the administrative assistant who was responsible for examination timetabling revealed that there were at least three or four timetables produced by the computer which could have formed the basis for an actual timetable. Inevitably there will always be some modifications which have to be made to any computer-generated timetable in order to accommodate specific requirements which a computer program could not easily take into account. However, it would typically take only an hour or two to check through the chosen timetable and incorporate any special requirements that may have arisen. As a result of the perceived success of the trial run made for semester I, 1988, the program was used to create the actual examination timetable in semester II, 1988. A computer-generated timetable was issued to staff and students early on in the semester once the student registrations had been finalized. Inevitably, there were a few comebacks, mainly from staff about the timing of the examination for their particular course, but there was ample time to make any necessary modifications. At this stage, an additional, and hitherto unanticipated, benefit of a computerized timetable was revealed. It was now possible for the administrative assistant to 'blame it on the computer' and more easily dismiss those requests for a change to the timetable which were not deemed to be substantial. When the job was done manually, the timetable was seen as the creation of the administrative assistant, who was therefore 'responsible' for any difficulties that people perceived. Accordingly, there was more pressure for these difficulties to be resolved, all of which meant extra work. Now that the timetable was generated on a computer, it was accepted as more objective, and people were, perhaps surprisingly, less inclined to complain that they had been unfairly treated. Modifications to the timetable were still made, but now they became the exception rather than the rule. CONCLUSIONS From the point of view of the timetable planner, the program was a definite advance over the previous, manual, system. Working from a class counts list and clash list, both of which were available from the existing student-registration system, the computer program could produce a selection of examination timetables in a matter of minutes. As well as avoiding clashes between courses having students in common, the program takes account of examination-room availability and capacity to schedule the necessary examinations over no more than 2 weeks such that as few students as possible have two examinations on the same day. In addition, the schedule is arranged 46
D. Johnson-Timetabling University Examinations such that the larger examinations are timetabled early so as to avoid a marking bottleneck at the end of the examination period. For the one occasion when a direct comparison with the previous manual approach was possible, the computer timetable was demonstrably better in terms of the number of same-day examinations. This is probably because the timetable planner previously made no real attempt to spread out the examinations for the majority of students. The one exception to this was for the pre-degree students at the 'foundation' level, whose programme of courses was essentially fixed and for whom the examination timetable could be planned accordingly. The foundation programme typically involves five distinct courses, and it was usual to timetable the examinations for these courses on different days throughout the first week. The reason why they were not spread out over the full 2-week period was that foundation courses usually have over 200 students and it was felt to be necessary to allow at least a full week for marking. Interestingly, with a computer-produced timetable, the foundation courses are still scheduled regularly over the first week and in the early part of the second week, and so the program seems to be taking the same view as the timetable planner regarding the timing of the foundation examinations. It therefore appears that the job of examination timetable planning has been greatly simplified by using the computer program. Most of the tedious work of cross-checking student examination combinations has been removed, and the administrative assistant responsible is able to produce a draft timetable much earlier than previously, and one which is almost certainly more acceptable from a student point of view. REFERENCES 1. 2. 3. 4. 5. 6. 7. 8. 9.
R. W. EGLESE and G. K. RAND (1987) Conference seminar timetabling. J. Opl Res. Soc. 38, 591-598. K. GossELIN and M. TRUCHON (1986) Allocation of classrooms by linear programming. J. Opl Res. Soc. 37, 561-569. J. M. WILSON (1981) The scheduling of magistrates to courts. J. Opl Res. Soc. 32, 121-124. A. J. COLE (1964) The preparation of examination timetables using a small-store computer. Comp. J. 7, 117-121. S. BRODER (1964) Final examination scheduling. CACM 7, 494-498. D. C. Wooo (1968) A system for computing university examination timetables. Comp. J. 11, 41-47. E. FoxLEY and K. LOCKYER (1968) The construction of examination timetables by computer. Comp. J. 11, 264-268. S. KIRKPATRICK, C. D. GELATI and M.P. VEccm (1983) Optimisation by simulated annealing. Science 220,671-680. M. LUNDY and A. MEES (1986) Convergence of an annealing algorithm. Mathemat. Prog. 34, 111-124.
47
