文章基本信息

标题：A GRASP+VND HEURISTIC FOR THE SCHOOL TIMETABLING PROBLEM
其他标题：A GRASP+VND HEURISTIC FOR THE SCHOOL TIMETABLING PROBLEM
本地全文：下载
作者：Janio Gloria De Oliveira ; Dalessandro Soares Vianna ; Marcilene de Fátima Dianin Vianna 等
期刊名称：Sistemas Gestão
印刷版ISSN：1980-5160
出版年度：2012
卷号：7
期号：3
页码：326-335
DOI：10.7177/sg.2012.V7.N3.A3
语种：Portuguese
出版社：Universidade Federal Fluminense
摘要：This work proposes an hybrid GRASP metaheuristic using, in the local search phase, the VND technique to solve the timetabling problem. It is considered to review data of Escola Agrotécnica Federal of Alegre-ES-Brazil in the years of 2006 and 2007 and other instances generated at this work for testing, for scheduling two rounds of education high school. The method proposed intends to satisfy the restrictions of timetable of the institution, such as: to meet teachers on the amount of days that their classes are distributed within hours of its availability; to minimize the number of consecutive classes in the same discipline; to prevent the occurrence of teaching vacancies; to minimize the occurrence of “windows” at the timetable of the teacher; to avoid overlapping of classes from the same teacher; to avoid that exists a classroom lecture with the same time with more than one teacher and other restrictions that bring quality to the timetable. The computational results demonstrated the feasibility of its use generates timetable that serve all restrictions of feasibility and a percentage above 85% for restrictions of quality of the solution.↓Este trabalho propõe uma heurística GRASP que utiliza, na etapa de busca local, a técnica VND para solucionar o Problema de Horário Escolar. Consideraram-se, para programação de dois turnos do ensino médio, os dados da Escola Agrotécnica Federal de Alegre (ES, Brasil) nos anos de 2006 e 2007 e outras instâncias geradas neste trabalho para testes. O método proposto tem como objetivo satisfazer as restrições de formação do horário da instituição, tais como: satisfazer aos professores quanto à quantidade de dias em que suas aulas são distribuídas e respeitar seus horários de indisponibilidade; minimizar o número de aulas consecutivas da mesma disciplina; evitar a ocorrência de aulas vagas; evitar a sobreposição de aulas de um mesmo professor; minimizar a ocorrência de “janelas” no horário do professor; evitar que uma turma esteja com aula no mesmo horário com mais de um professor e outras restrições que trazem qualidade ao horário definido. Os resultados computacionais obtidos demonstraram a viabilidade de sua utilização gerando horários que atendem a todas as restrições de viabilidade e um percentual acima de 85% para as restrições de qualidade da solução.
其他摘要：This work proposes an hybrid GRASP metaheuristic using, in the local search phase, the VND technique to solve the timetabling problem. It is considered to review data of Escola Agrotécnica Federal of Alegre-ES-Brazil in the years of 2006 and 2007 and other instances generated at this work for testing, for scheduling two rounds of education high school. The method proposed intends to satisfy the restrictions of timetable of the institution, such as: to meet teachers on the amount of days that their classes are distributed within hours of its availability; to minimize the number of consecutive classes in the same discipline; to prevent the occurrence of teaching vacancies; to minimize the occurrence of “windows” at the timetable of the teacher; to avoid overlapping of classes from the same teacher; to avoid that exists a classroom lecture with the same time with more than one teacher and other restrictions that bring quality to the timetable. The computational results demonstrated the feasibility of its use generates timetable that serve all restrictions of feasibility and a percentage above 85% for restrictions of quality of the solution.
关键词：Engenharia;Metaheurística; GRASP; VND; Problema de Horário Escolar;Metaheuristics; GRASP; VND; School timetabling problem
其他关键词：Metaheuristics; GRASP; VND; School timetabling problem