基于遗传算法的高校教室调度问题  

Genetic Algorithm for the Timetabling Problem in Universities

作　　者：曹策俊[1] 杨琴[1] 梁红燕[1] 袁玲玲[1] 

机构地区：[1]四川师范大学商学院,四川成都610101

出　　处：《工业工程》2012年第3期130-135,共6页Industrial Engineering Journal

基　　金：国家自然科学基金资助项目(70672013);四川省哲学社会科学"十二五"规划项目(SC11C042);四川省教育厅科研资助项目(10ZC004)

摘　　要：对高校教室调度问题进行研究,能使教室和课程达到一种合理的优化配置。类似问题的研究在制造业或生产系统中都占有非常重要的地位。研究首先采用三元组方式,将教室调度问题描述为一类具有机器适用限制的并行多机问题,以最小化Cmax(即集中时间提高教室利用效率)和滞后时间总和为调度目标,建立了对应的数学模型。根据问题的特性,设计了包含分派规则和遗传算法的启发式调度算法求解该类问题。研究结合问题特性在编码,个体适应度函数,交叉及变异等方面进行了设计。以实例分析验证了所设计算法的可行性和有效性。The timetabling problem in universities is to assign the classrooms into classes. This problem is somehow similar to that of assigning machines into jobs in manufacturing systems to minimize the makespan and tardiness. With this observation, the timetabling problem is described by a triplet as a parallel ma- chine scheduling problem with machine eligibility restrictions. Then, a mathematical model is developed for the problem. By analyzing the features of the model, a heuristic that combines dispatching rules and genetic algorithm is proposed to solve the problem. Techniques for coding, individual fitness, crossover, and mutation are presented to implement the genetic algorithm. The proposed method is tested by using a practical case problem and it is shown to be effective and feasible.

关 键 词：教室调度 并行机调度 分派规则 遗传算法 

分 类 号：F406.2[经济管理—产业经济]