The thesis investigates a new method of solution of the school timetable problem. It uses the description of the problem in which the school's requirements are expressed in terms of year group layouts. the ziethod starts with a complete but infeasible timetable and proceeds to convert it into a feasible timetable. The infeasibilitios are reduced by interchanging meetings between pairs of periods. The interchanges used are the optimal solutions to small integer programming problems. Various strategies are defined which control the constraints and. objective functions that are generated. These interchange problems are solved by a new dynamic programming branch and bound algorithm. This interchange process is called phase one and it rapidly produces a tinetable which is either feasible or only contains a few infeasibilitios. Phase one cannot be guaranteea to always produce a feasible timetable when one exists. A second longer process, phase two, is defined which either finds a timetable with less infeasibilities or shows that the problem is infeasible. Phase two generates problems of the same form as the original but with less perioäs. These are solved by the phase one / phase two algorithm. The phase one / phase two algorithm is extended to solve problems which contain fixed periods or variable staff availabilitios. The phase one algorithm is extended also to solve problems with double periods. The phase one / phase two algorithm has been tested on four layout problems. For two of the problems feasible timetables were produced s, nä for the other two problems, timetables with better than 98 ö completion viere produced.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:448389 |
| Date | January 1973 |
| Creators | Aust, R. J. |
| Publisher | University of Sussex |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.0016 seconds