Modelling different aspects of final exam scheduling problems for a graph-based state space reduction method

Abstract

Final exam scheduling is a subtopic of scheduling where various special requirements with different levels of strictness should be managed. The formalisation of these requirements can be a challenge in itself. The number of possible schedules that should be examined is usually large, so the state space is vast. However, many of these schedules can be excluded completely at an early stage based on their inconsistency with the hard requirements, thus reducing the state space. The modelling approach for different aspects of final exam scheduling problems is presented in this paper through the modelling of an actual, complex problem. The created model was used as the basis for a state space reduction method. The results show that the method could handle all the hard and soft constraints of the problem and reduce the state space significantly based on them. The modelling approach can be used for formalising the requirements of various final exam scheduling and similar problems.