×

zbMATH — the first resource for mathematics

An introduction to timetabling. (English) Zbl 0553.90059
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.

MSC:
90B35 Deterministic scheduling theory in operations research
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berge, C., Graphes, (1983), Gauthier-Villars Paris · Zbl 0213.25702
[2] Bloomfield, S.D.; McSharry, M.M., Preferential course scheduling, Interfaces, 9, 24-31, (1979)
[3] Brélaz, D., New methods to color the vertices of a graph, Communications of the ACM, 22, 251-256, (1979) · Zbl 0394.05022
[4] Carter, M., A decomposition algorithm for practical timetabling problems, ()
[5] Carter, M., A survey of practical applications on examination timetabling, ()
[6] Clementson, A.T.; Elphick, C.H., Continuous timetabling problems, Journal of the operational research society, 33, 181-183, (1982) · Zbl 0475.90045
[7] Dempster, M.A.H.; Lethridge, D.G.; Ulph, A.M., School timetabling by computer — A technical history, (1973), Oxford University
[8] Dutton, R.D.; Brigham, R.C., A new graph coloring algorithm, Computer journal, 24, 85-86, (1981) · Zbl 0445.05046
[9] Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multicommodity flow problems, SIAM journal on computing, 5, 691-703, (1976) · Zbl 0358.90021
[10] Ferland, J.A.; Roy, S., Course scheduling and classroom assignment in a university, ()
[11] Ford, L.R.; Fulkerson, D.R., Flows in networks, (1962), Princeton University Press Princeton · Zbl 0139.13701
[12] Gans, O.B. de, A computer timetabling system or secondary schools in The Netherlands, European journal of operational research, 7, 175-182, (1981)
[13] Garey, M.R.; Johnson, D.S., Computers and intractability, a guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[14] Gotlieb, C.C., The construction of class-teacher timetables, (), 73-77 · Zbl 0143.18802
[15] Hilton, A.J.W., School timetables, Annals of discrete mathematics, 11, 177-188, (1981) · Zbl 0493.90043
[16] Johri, A.; Matula, D.W., Probabilistic bounds and heuristic algorithms for coloring large random graphs, (1982), Dept. of Computer Science Engineering, Southern Methodist University Dallas Texas
[17] Junginger, W., Zurückführung des studenplanproblems auf ein dreidimensionales transportproblem, Zeitschrift für operations research, 16, 11-25, (1972) · Zbl 0236.90042
[18] Junginger, W., Zum aktuellen stand der automatischen studenplanerstellung, Angewandte informatik, 1, 20-25, (1982)
[19] Krarup, J., Chromatic optimisation: limitations, objectives, uses, references, European journal of operational research, 11, 1-19, (1982) · Zbl 0482.90066
[20] Lawrie, N.L., An integer programming model of a school timetabling problem, Computer journal, 12, 307-316, (1969)
[21] Leighton, F.T., A graph coloring algorithm for large scheduling problems, Journal of research of the national bureau of standard, 84, 489-506, (1979) · Zbl 0437.68021
[22] Mahadev, N.V.R.; de Werra, D., On a class of perfectly orderable graphs, () · Zbl 0654.05032
[23] Mehta, N.K., The application of a graph coloring method to an examination scheduling problem, Interfaces, 11, 57-64, (1981)
[24] Mulvey, J.M., A classroom/time assignment model, European journal of operational research, 9, 64-70, (1982) · Zbl 0471.90061
[25] Ostermann, R.; de Werra, D., Some experiments with a timetabling system, OR spektrum, 3, 199-204, (1982)
[26] Peemöller, J., A correction to brelaz’s modification of Brown’s coloring algorithm, Communications of the ACM, 26, 595-597, (1983)
[27] Randall Brown, J., Chromatic scheduling and the chromatic number problem, Management science, 19, 456-463, (1972) · Zbl 0247.90028
[28] Romero, B.P., Examination scheduling in a large engineering school: A computer-assisted participative procedure, Interfaces, 17-23, (1982)
[29] Schmidt, G.; Ströhlein, T., Timetable construction — an annotated bibliography, The computer journal, 23, 307-316, (1979)
[30] Silver, E.A.; Vidal, R.V.; de Werra, D., A tutorial on heuristic methods, European journal of operational research, 5, 153-162, (1980)
[31] Smith, G.; Sefton, I.M., On lion’s counter example for Gotlieb’s method for the construction of school timetables, Communications of the ACM, 17, 197, (1974)
[32] Smith, G., Computer solutions to a class of scheduling problems, ()
[33] Thomson Leighton, F., A graph coloring algorithm for large scheduling problems, Journal of research of the national bureau of standards, 84, 489-506, (1979) · Zbl 0437.68021
[34] Tripathy, A., A Lagrangean relaxation approach to course timetabling, Journal of the operational research society, 31, 599-603, (1980) · Zbl 0434.90046
[35] Vlach, M., On the three planar sums transportation polytope, ()
[36] Welsh, D.J.A.; Powell, M.B., An upper bound for the chromatic number of a graph and its application to timetabling, Computer journal, 10, 85-86, (1967) · Zbl 0147.15206
[37] Werra, D. de, A few remarks on chromatic scheduling, (), 337-342
[38] Werra, D. de, Some comments on a note about timetabling, Infor, 16, 90-92, (1978) · Zbl 0385.90053
[39] White, D.J., A note of faculty timetabling, Operations research quarterly, 26, 875-878, (1975) · Zbl 0312.90031
[40] White, G.M.; Chan, P.W., Towards the construction of optimal examination schedules, Infor, 17, 219-229, (1979)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.