An introduction to timetabling
European Journal of Operational ResearchPublished 1 February 1985
D. de Werra
Citations573
SJR quartileQ1
SJR score2.24
SNIP2.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A huge variety of timetabling models have been described in the OR literature; they range from the weekly timetable of a school to the scheduling of courses or exams in a university.
Abstract
A huge variety of timetabling models have been described in the OR literature; they range from the weekly timetable of a school to the scheduling of courses or exams in a university. Graphs and networks have proven to be useful in the formulation and solution of such problems. Various models will be described with an emphasis on graph theoretical models.
Keywords
Computer ScienceDecision SciencesEngineering
Flows in networks
4,080 Citations1962D. R. Ford, D. R. Fulkerson
Communications of the ACMNew methods to color the vertices of a graph
1,564 Citations1979Daniel Brélaz
An exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs and the new heuristic methods, the classical methods, and the exact method are compared.
SIAM Journal on ComputingOn the Complexity of Timetable and Multicommodity Flow Problems
1,049 Citations1976Shimon Even, Alon Itai +1 more
The Computer JournalAn upper bound for the chromatic number of a graph and its application to timetabling problems
751 Citations1967Dominic Welsh
Journal of Research of the National Bureau of StandardsA graph coloring algorithm for large scheduling problems
486 Citations1979Frank Thomson Leighton
A new graph coloring algorithm is presented and shown to exhibit O(n 2) time behavior for most sparse graphs and thus is found to be particularly well suited for use with large-scale scheduling problems.
Management ScienceChromatic Scheduling and the Chromatic Number Problem
138 Citations1972James R. Brown
European Journal of Operational ResearchA tutorial on heuristic methods
132 Citations1980Edward A. Silver, René Victor +2 more
This paper defines a heuristic method as a procedure for solving a well-defined mathematical problem by an intuitive approach in which the structure of the problem can be interpreted and exploited intelligently to obtain a reasonable solution.
The Computer JournalAn integer linear programming model of a school timetabling problem
78 Citations1969N. L. Lawrie
European Journal of Operational ResearchA classroom/time assignment model
73 Citations1982John M. Mulvey
A network-based optimizing approach to the classroom/time model which rapidly approximates the solutions is devised which combines the insight of the scheduler with combinatorial and searching ability of a computer via a transshipment optimization network model.
INFORMS Journal on Applied AnalyticsThe Application of a Graph Coloring Method to an Examination Scheduling Problem
65 Citations1981Nirbhay K. Mehta
The accessories used in deriving and compressing the schedule and in rearranging the time frames to make the solution acceptable for the spring semester of 1980 are described.
Communications of the ACMA correction to Brelaz's modification of Brown's coloring algorithm
50 Citations1983Jürgen Peemöller
Brelaz's modification of Brown's exact coloring algorithm contains two errors as demonstrated in two examples and Brown's look-ahead rule is built into this algorithm.
Journal of the Operational Research SocietyA Lagrangean Relaxation Approach to Course Timetabling
42 Citations1980Arabinda Tripathy
A study of mathematical programming approaches to time-tabling resulted in the development of an algorithm based on Lagrangean relaxation embedded in a branch and bound procedure, which is applied to a more modest-sized problem based on published real data.
INFOR Information Systems and Operational ResearchTowards The Construction Of Optimal Examination Schedules
40 Citations1979George M. White, Pak–Wah Chan
This paper describes a solution to find the minimum closed path through an appropriate weighted undirected graph which traverses all nodes exactly once which will provide an optimum timetable for students writing examinations.
European Journal of Operational ResearchA computer timetabling system for secondary schools in the Netherlands
40 Citations1981Onno B. de Gans
The Dutch school organization will be outlined and a data structure can be derived that makes it possible to handle most curriculum requirements and the main idea underlying this construction procedure will be exposed.
INFORMS Journal on Applied AnalyticsPreferential Course Scheduling
30 Citations1979Stefan D. Bloomfield, Michael M. McSharry
Recent work by Dyer and Mulvey has addressed the problem of assigning faculty members to specific classes or course sections by developing a network flow model that was successfully used to assign faculty member to course sections at the Graduate School of Management at UCLA.
European Journal of Operational ResearchChromatic optimisation: Limitations, objectives, uses, references
29 Citations1982Jakob Krarup, D. de Werra
This paper addresses anvone concerned with real-world scheduling problems as well as anyone interested in the use of diserete models in decision-making as such by means of modest-sized scheduling problems.
A Few Remarks on Chromatic Scheduling
29 Citations1975D. de Werra
A property of colorings related to the so called good schedules is established for some hypergraphs and for multigraphs.
OR SpectrumSome experiments with a timetabling system
18 Citations1982Roman C. Ostermann, D. de Werra
T timetables for some public schools in Switzerland have been successfully constructed with a computer and the various types of constraints are described and practical experiments are reported.
INFORMS Journal on Applied AnalyticsExamination Scheduling in a Large Engineering School: A Computer-Assisted Participative Procedure
17 Citations1982Bernardo Prida Romero
This procedure has the advantage of coping with the objectives of the decision makers without the necessity of formally defining any objective function, in order to permit the choice of an acceptable solution from the feasibility set.
INFOR Information Systems and Operational ResearchSome Comments On A Note About Timetabling<sup>*</sup>
11 Citations1978De Werra
Communications of the ACMOn Lion's counter example for Gotlieb's method for the construction of school timetables
10 Citations1974Graham Smith, Ian M. Sefton
The timetable problem is an essentially discrete problem, for which the nondiscrete solution can be interpreted as a set of timetables, differing from week to week, which together satisfy the long-term requirements of the timetable problem.
Mathematical Methods of Operations ResearchZurückführung des Stundenplanproblems auf ein dreidimensionales Transportproblem
10 Citations1972Werner Junginger
This paper contains an additional approach of mathematical treatment by formulating a timetable problem as a multi-index transportation problem through that the special algorithms for the solution of this transportation problem can be used to solve the timetable problem.
Educational ResearchSchool Timetabling by Computer a Technical History
9 Citations1975Maggie Dempster, David Lethbridge +1 more
An outline of the nature of the timetabling problem is suggested, suggesting the kind of requirements that arise in practice and the criteria used to evaluate timetables.
Journal of the Operational Research SocietyA Note on Faculty Timetabling
6 Citations1975D. J. White
The note deals with the problem of finding which combinations of classes and how many times each combination will occur in a given week to meet requirements on the number of times each class has to occur throughout the week.
Journal of the Operational Research SocietyContinuous Timetabling Problems
2 Citations1982A. T. Clementson, Clive Elphick
A conjecture concerning a continuous formulation of timetabling problems is discussed and an alternative discrete formulation is proposed.