权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

基于进化算法和禁忌搜索的请求排班方法研究

基本信息

批准号：
12680455
负责人：
TANAKA Masashiro
金额：
$ 1.22万
依托单位：
KONAN UNIVERSITY
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2002
项目状态：
已结题

项目摘要

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.

排课问题千差万别，存在着许多用户要求的约束条件。这个项目的第一步是简化问题并找到内在结构。我们从三种用户的角度来考虑这个问题：服务的接受者包括学生、观众和病人，服务的代理人包括教师、演讲者和医生，以及组织机构如学校、会议组织者或医院。因此，我们通过首先听取这些用户的请求来建立这个系统的概念，然后通过存在硬约束和软约束的元启发式方法使时间表自动化。这个项目的下一步是安排会议的时间表。问题是把演讲安排在平行的几天时间内。硬性约束是我们必须避免同一个人在同一时间段提交不同论文的作业。软约束包括避免在不同房间的同一时间段做类似的演讲，更喜欢在同一会议上发表类似的论文等。对于这个问题，我们提出了两种主要的方法。一种是采用Falkenauer的“分组遗传算法”，另一种是基于Kohonen的自组织映射。在GGA中，问题被分为会话构建和会话分配两个模块。在SOM中，我们提出使用SOM网格作为会话。在这个项目之后应该有一些问题，例如主席的待遇、有组织会议的待遇、会议的能力等。本研究将为基于请求的排课问题，特别是包括分组问题在内的排课问题提供良好的基础。