Research on timetabling methods based on request by evolutionary algorithm and tabu search

点击翻译按钮获取中文摘要

The problem of timetabling varies a lot, and there exist a lot of constraints which are the requests of the users. The first step of this project was to simplify the problems and find the intrinsic structures. We considered the problem from three kinds of users : recipients of the service including students, audience and patients, service agents including teachers, presenters and doctors, and the organization like a school, a conference organizer or a hospital. Hence, we established the concept of this system by first hearing the requests from these users, and next making the timetable automated by meta-heuristic methods where hard and soft constraints exist.The next step of this project was timetabling of conferences. The problem is assigning presentations into the time slots that run parallel through several days. The hard constraint is that we must avoid assignment where a same person must present different papers at the same time slot. The soft constraints include avoiding similar presentations at same time slots in different rooms, preferring similar papers in a same session, etc. We proposed two major methods for this problem. One is to apply "grouping genetic algorithm" by Falkenauer, and the other is based on Self Organizing Map by Kohonen. In GGA, the problem was divided into session construction and session allocation modules. In SOM, we proposed to use the SOM grid as the sessions.There are problems that should follow this project, for example, treatment of chairpersons, treatment of organized sessions, the capacity of the sessions, etc. However, the research will be a good basis for the timetabling using request, especially for timetabling problems including grouping problems.