Fuzzy Integer Linear Programming Mathematical Models for Examination Timetable Problem

Abstract

Examination Timetable Problem (ETP) is NP–Hard combinatorial optimization problem. It has received tremendous research attention during the past few years given its wide use in universities. ETP can be defined as assignment of courses to be examined, candidates to time periods and examination rooms while satisfying a set of constraints which may be either hard or soft. Several methods have been proposed most of which are based on heuristics like Search techniques, Evolutionary Computation etc. In this Paper, we develop three mathematical models for Netaji Subhas Open University, Kolkata, India using Fuzzy Integer Linear Programming (FILP) technique. In most real life situations, information available in is not exact, lacks precision and has an inherent degree of vagueness. To deal with this we model various allocation variables through fuzzy numbers expressing lack of precision the decision maker has. The solution to the problem is obtained using Fuzzy number ranking method. Each feasible solution has fuzzy number obtained by Fuzzy objective function. The different FILP technique performance are demonstrated by experimental data generated through extensive simulation from Netaji Subhas Open University, Kolkata, India in terms of its execution times. The proposed FILP models are compared with commonly used heuristic viz. Integer Linear Programming approach on experimental data which gives an idea about quality of heuristic. The techniques are also compared with different Artificial Intelligence based heuristics for ETP with respect to best and mean cost as well as execution time measures on Carter benchmark datasets to illustrate its effectiveness. FILP paradigm takes an appreciable amount of time to generate satisfactory solution in comparison to other heuristics. The formulation thus serves as good benchmark for other heuristics. The experimental study presented here focuses on producing a methodology that generalizes well over spectrum of techniques that generates significant results for one or more datasets. The performance of FILP model is finally compared to the best results cited in literature for Carter benchmarks to assess its potential.