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

摘要/Abstract

摘要： 对高校教室调度问题进行研究，能使教室和课程达到一种合理的优化配置。类似问题的研究在制造业或生产系统中都占有非常重要的地位。研究首先采用三元组方式，将教室调度问题描述为一类具有机器适用限制的并行多机问题，以最小化Cmax（即集中时间提高教室利用效率）和滞后时间总和为调度目标，建立了对应的数学模型。根据问题的特性，设计了包含分派规则和遗传算法的启发式调度算法求解该类问题。研究结合问题特性在编码，个体适应度函数，交叉及变异等方面进行了设计。以实例分析验证了所设计算法的可行性和有效性。

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

Abstract: 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 machine 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.

Key words: timetabling, parallel machine scheduling, dispatching rules, genetic algorithm

曹策俊，杨琴, 梁红燕，袁玲玲. 基于遗传算法的高校教室调度问题[J]. 工业工程, 2012, 15(3): 130-135.

Cao Cejun，Yang Qin, Liang Hongyan, Yuan Lingling. Genetic Algorithm for the Timetabling Problem in Universities[J]. Industrial Engineering Journal , 2012, 15(3): 130-135.

参考文献

［1］Pinedo M. Scheduling:theory,algorithms,and systems. Englewood Cliffs［M］. 2nd Edition. NJ: Prentice Hall, 2002. ［2］景学琴，朱玉芳，杜栋，等.从排课表到教室调度表的设计与实现［J］.计算机应用与软件, 2004,21(2):123-124. Jing Xueqin,Zhu Yufang,Du Dong，et al.Designing and accomplishing classroom dispatching table on the basis of curriculum schedule［J］.Computuer Applications and Software, 2004,21(2):123-124. ［3］陈春华.基于NET的教室调度与管理信息系统的设计与实现［J］.网络财富,2009(7):30-32. Chen Chunhua.Designing and accomplishing of classroom scheduling and management information systems based on NET［J］.Internet Fortune, 2009(7):30-32. ［4］Perry Fizzano,Steven Swanson. Scheduling classes on a college campus［J］. Computational optimization and applications,2000,16(3): 279-294. ［5］刘民，吴澄，尹文君.带特殊工艺约束的并行机器生产线调度问题的一种遗传算法［J］.自动化学报,2001，27（3）：381-386. Liu Min,Wu Cheng,Yin WenJun.Solving identical parallel machine production line scheduling problem with special procedure constraint by genetic algorithm［J］.Acta Automatica Sinica, 2001，27（3）：381-386. ［6］廖远，黄勤，曹培霞.基于三维编码的自适应遗传算法在排课系统中的应用［J］.计算机与现代化，2008（12）：23-24. Liao Yuan,Huang Qin,Cao Peixia. Application of selfadaptive genetic algorithm based on three dimesion coding in curriculum scheduling system［J］.Computer and Modernization,2008（12）：23-24. ［7］杨琴，周国华，林晶晶，等. 应急事件中瓶颈环节的实时优化调度［J］. 系统工程,2010，28(7):74-78. Yang Qin,Zhou Guohua,Lin Jingjing,et al.Realtime optimized scheduling of the bottleneck in emergency［J］.Systems Engineering, 2010，28(7):74-78. ［8］Hendizadeh S H, Faramarzi H, Mansouri S A,et al. Metaheuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times［J］．International Journal of Production Economics, 2008,111(2):593-605. ［9］AlAnzi F S, Allahverdi A. A selfadaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times［J］．European Journal of Operational Research,2007,182(1):80-94. ［10］Chtourou H, Haouari M. A two-stage priority-rule-based algorithm for robust resource constrained project scheduling［J］. Computers & Industrial Engineering, 2008,55(1):183-194. ［11］Senthilkumar P,Shahabudeen P.GA based heuristic for the open job shop scheduling problem［J］.International Journal of Advanced Manufacturing Technology,2006,30(3):297-301. ［12］Geoffrey Vilcot,JeanCharles Billaut.A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem［J］.European Journal of Operational Research,2008,190(2):398-411. ［13］Jie Gao,Linyan Sun,Mitsuo Genb.A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems［J］.Computers & Operations Research,2008,35(9): 2892-2907. ［14］Valls V.Perez A Quintanilla S.Skilled wo workforce scheduling in service centres［J］. European Journal of Operational Research, 2009,193(3):791-804. ［15］Fei H,Meskens N,Chu C.A planning and scheduling problem for an operating theatre using an open scheduling strategy［J］. Computers & Industrial Engineering,2010,58(2):221-230.

[1]	张正敏, 管在林, 岳磊. 基于Lévy Flight的混合GA在柔性作业车间调度问题中的性能分析[J]. 工业工程, 2021, 24(4): 83-92.
[2]	王晓军, 王博, 晋民杰, 杨春霞, 白新利. 改进多种群遗传算法的AutoStore系统多AGV调度优化[J]. 工业工程, 2021, 24(4): 112-118,167.
[3]	王莹莹, 吴立云. 基于改进NSGA-II的多项目多技能人力资源调度研究[J]. 工业工程, 2021, 24(3): 130-138.
[4]	曾创锋, 刘建军, 陈庆新, 毛宁. 求解一类无关并行机调度的遗传迭代贪心算法[J]. 工业工程, 2021, 24(2): 110-118.
[5]	黄露, 纪延光. 考虑顾客延误损失的配送中心选址双层规划问题研究[J]. 工业工程, 2021, 24(2): 141-147.
[6]	王冰怡, 张锦. 考虑网点共享与变更的多级快递网点选址问题[J]. 工业工程, 2021, 24(2): 155-165.
[7]	马跃如, 文铮, 易丹. 考虑老年人满意度的多目标居家养老护理员路径优化[J]. 工业工程, 2021, 24(1): 74-81,103.
[8]	王玖河, 高辉, 刘欢. 基于遗传算法的共享助力车调度问题研究[J]. 工业工程, 2021, 24(1): 90-96.
[9]	吴斌, 宋琰, 程晶, 董敏. 基于密度峰值聚类的VRPTW问题研究[J]. 工业工程, 2020, 23(5): 58-66,74.
[10]	王苏林, 邱菲尔, 陈凡, 刘川昆, 鹿腾, 王芷芸. 基于贪心遗传的地下物流节点选择规划研究[J]. 工业工程, 2020, 23(5): 88-95.
[11]	侯艳, 黄康焕, 张亿仙, 伍乃骐. 原油一次加工过程的多目标调度优化[J]. 工业工程, 2020, 23(4): 131-139.
[12]	王泽, 杨信丰, 刘兰芬. 考虑电量消耗的车辆调度优化研究[J]. 工业工程, 2020, 23(4): 140-147.
[13]	曾垂飞, 刘建军, 陈庆新, 毛宁. 装配作业车间分批调度问题的算法对比[J]. 工业工程, 2020, 23(4): 174-182.
[14]	张巍, 李鹏翔, 仝自强, 岳毅蒙. 基于损坏车辆分布预测与损益阈值分析下的共享单车回收研究[J]. 工业工程, 2020, 23(3): 132-137.
[15]	张国辉, 胡一凡, 孙靖贺. 改进遗传算法求解多时间约束的柔性作业车间调度问题[J]. 工业工程, 2020, 23(2): 19-25,48.