An Introduction to Job Shop Scheduling to Model the Timetabling Scheduling Problem

Abstract

The Timetabling Scheduling Problem (TTSP) is proposed as a schedule of a sequence of events between actors (teachers, students, workers, etc.) in a predefined period (typically hours), satisfying a set of constraints. TTSP has been traditionally considered in the operational research field and recently has been tackled with different Artificial Intelligence techniques. The proposed solutions to TTSP are in the range of traditional techniques (linear programming, whole programming, manual solution, network flow, etc.) and metaheuristic methods (simulations of human way, graph colouring, tabu search, genetic algorithms, simulated annealing, etc.). Job Shop Scheduling Problem (JSSP) is one of the best known combinatorial optimization NP-hard problems. There are many solutions to JSSP from a broad spectrum of researchers: management scientist, computational researcher, production experts, etc., from different individual areas and multidisciplinary areas. This article aims to model the TTSP in terms of JSSP in order to expand the possible solutions to this problem. We considered TTSP as JSSP because there are similarities at the mathematical model and the objective function. TTSP is modelled as JSSP where jobs represent the relation professor – signature – group and machines constitute the academic spaces.