Implementación de un algoritmo GRASP para el problema de coloración de grafos aplicado a la calendarización de exámenes en una institución educativa

Abstract

One  of  the  tasks  facing  educational  institutions  each  year  is  planning  class  schedules  and  exams.  His  difficulty  is  that  various  operational constraints arise at the time of planning. Given the nature of the problem described above, the test scheduling belongs to the set of  combinatorial  optimization problems  categorized  NP-Hard,  making  it  complex  to  solve  by  exact  methods.  The  advantage  is  that  the scheduling of examinations is an operational problem it would be sufficient to obtain high quality feasible solutions, not necessarily optimal, in reasonable computational times. One of the tools used for this purpose is the construction of metaheuristics based heuristics for intelligent exploration strength  in  the  solution  space.  Based  on  the  above,  in  this  paper  we  develop  a  heuristic  algorithm  based  on  the  GRASP  methodology the same as it applied in the preparation of test schedules subject to a set of constraints of various kinds.