Towards The Construction Of Optimal Examination Schedules
George M. White, Pak–Wah Chan · INFOR Information Systems and Operational Research · 1979
Assume c courses to be examined in p e:samination periods. Let the c courses be the nodes (v1, v2,..., Vc) of a graph and let a student registered in both courses vi and vj be represented by an edge joining the node pair (vi, vj). Then the scheduling of the c courses into p periods is analogous to partitioning the nodes of the graph into no more than p disjoint sets (s1, s2, ...,sp) such that, in any given set, there is no edge joining any of its elements. An additional aim is to find the minimum closed path through an appropriate weighted undirected graph which traverses all nodes exactly once. The solution to this problem will provide an optimum timetable for students writing examinations. This paper describes one such solution which has been used for several years at the University of Ottawa.