课程表问题的一种模拟退火超启发式算法

课程表问题是经典的组合优化问题,属于NP-hard问题.长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法.在此基础上提出了一种基于多个图染色启发式规则的模拟退火超启发式算法.在超启发式算法的框架中,用模拟退火算法作为高层搜索算法,多个图染色启发式规则为底层的构造算法.与现有的方法相比,该算法具有很好的通用性,可以很容易推广到考试时间表、会议安排.旅行商问题、背包问题等应用领域.实验表明,该算法是可行有效的,且无一例时间、空间冲突.     

基于演化算法的一类时间表问题的自动求解

本文给出了一种有效的基于演化算法的求解大学的时间表总理２（编排课程和考试）即在很强的资源约束条件下将一些事件（课程或考试）安排到时间段和空间位置的总理２的方法,此方法有杉直接的时间表编码表示和启发式深化算子,并通过惩罚函数保证对约束条件的满足,计算实验表明方法在求解大学考试时间表问题中是有效的。     

基于GENET的时间表问题自动求解算法

构造大学考试时间表自动生成系统是一个知名的问题．本文用约束满足问题模型来描述大学考试时间表问题,并提出了一个基于GENET的局部搜索算法来解该问题．该算法采用一些问题相关的策略来提高局部搜索效率．实验结果表明,将“强约束违反”转化为“弱约束违反”的方法能大大地提高算法性能,使该算法优于GENET和演化算法。     

基于关系着色图的Timetabling算法研究及其应用

考试自动安排系统在高校教务管理中处于重要位置,也是一个难题.提出一种基于关系着色图RCC(Relationship Coloring Chart)的Timetabling算法,探讨了该算法在考试时间安排中的应用,开发了某高校业余大学考试自动安排系统,并解决了较大数量学生补考的复杂安排问题.     

分组遗传算法优化大学考试时间表

大学考试时间表是一个多约束条件下的优化问题。传统遗传算法寻优的计算量是指数级的规模,而寻优的操作有可能会破坏时间表的硬约束条件,从而最终得到的解并不一定理想甚至不可行。该文从某高校的实际应用出发,对用图着色模型得到的已经满足了硬约束条件的初始考试时间表,用改进的分组遗传算法在既不破坏硬约束条件也不延长考试周的条件下扩大并平均分配了学生的复习时间,并且还大大减少了寻优的计算量。     

混合算法在大学课程表问题中的应用研究

大学课程袁问题是时间表问题之一,也是一个多因素的优化决策问题.文章提出的混合算法,基于动态规划的思想,对大学课程表问题进行分阶段求解,分别采用遗传算法分配时间,采用最佳适应算法分配场地.实验结果表明,这种方法既保证了课表的质量,又有利于工程上实现和扩展.     

资源分配算法的比较和研究

许多领域都涉及资源分配问题,怎样合理的把各种有限的经济资源分配给企业内各生产部门,使得本企业在相对较低的成本投入下得到较大利润是每一个企业所追求的目标。于是就产生了如何分配以使工程目标或生产目的达到最优的问题。本文针对这一类资源分配问题,阐述了用动态规划方法和多段图方法的求解思想,并通过实例比较了两种算法。     

基于任务-资源分配图优化选取的网格依赖任务调度

任务调度是网格应用系统获得高性能的关键.网格计算中一个大型的应用程序往往被分解为具有依赖关系的多个任务.在资源个体差异较大、广域互连的网格环境下任务间的依赖关系对传统的调度策略提出了新的挑战.任务调度的主要工作是为任务分配资源以及确定任务的执行次序,将依赖任务的可能的资源分配方案表示为任务-资源分配图（T-RAG）,在该图的基础上提出了基于T-RAG优化选取的依赖任务调度模型,将依赖任务调度问题转化为图的优化选取问题,解析最优任务-资源分配图可以同时确定资源分配方案和任务的执行次序即为最优调度方案.最后,实现了基于该模型的任务调度算法,该算法与ILHA算法的对比分析表明,在资源差异较大及任务间存在大量数据传输的情况下所提出的算法更优.     

柔性资源受限多项目调度的混沌粒子群算法研究

为解决柔性资源受限多项目的调度问题,有效实行资源分配和工作时间安排,采用混沌粒子群算法结合混合优先规则,形成优先规则序列。针对多项目问题,避免了传统方法将多个项目合并为一个项目,而是形成一个链表在项目的各工序间进行选择调度,并在初始化中嵌入混沌理论,在迭代过程中使用并行算法,有效避免了算法易陷入局部最优解的可能。改编标准库的多模式算例,对比多种算法下的结果,验证了该方法在求解该问题的可行性和有效性,对于项目管理中柔性资源受限问题具有实际应用价值。     

采用增强学习算法的排课模型

时间表问题是典型的组合优化和不确定性调度问题。课表问题是时间表问题的一种形式,分析了排课问题的数学模型，并研究了用增强学习(Reinforcement Leaming)算法中的Q学习(Q-Leaming)算法和神经网络技术结合解决大学课表编排问题，给出了一个基于该算法的排课模型，并对其排课效果进行了分析和探讨。     

基于边映射表连接的匹配算法

针对面向语义网络图匹配的特殊性, 在基于状态回溯搜索算法的基础上提出一种新的称为基于边映射表连接的匹配算法, 利用语义网络图的有向性, 将图匹配问题转换为对搜索路径的规划, 并采用深度优先算法形成搜索步, 同时对目标图的所有边建立索引, 加快以边匹配为中心形成边映射表的过程, 最后对边映射表进行连接形成结果集。在真实数据集上的实验结果表明, 该算法具有较高的执行效率。     

改进后的D_时刻表算法及其在实际中的应用

为了处理现实生活中事件发生除了先后关系以外还客观存在的时间宽度问题，文中实现了一种可以实际操作的方法。该方法是以文献[1]中的求解D_时刻表的方法为基础，分析找到了其不足的地方并加以改进。文中利用改进后的算法对该校校园运动会项目进行安排，结果表明该方法取得了较好的效果，从而实现了对该类问题的一种新的解决方法，使得解决该类问题成为现实。     

FF现场总线系统调度问题的研究

FF现场总线系统(FCS)为典型的分布式实时系统，分布在不同设备（包括总线） 的功能块和通讯任务相互作用完成复杂的控制方案，除了实时性要求，还要考虑执行顺序和 资源约束，调度问题为一NP 完全问题．本文分析了FF控制系统的特点，提出了类比于作业 车间调度问题（JSSP）的调度模型，针对特殊的模型，设计相应的编码和解码规则以及性能 指标，用遗传算法在满足上述约束下构建调度表，实现无抖动调度，最后分析了该方法下系 统的可调度条件．     

使用遗传算法改进R_时刻表算法

给出了对于多成分R_时间表的解决办法。利用集合的性质把它看成是几个单成分时间关系约束的并集,采用算法I将多成分分解成单成分。使用遗传算法把问题的多成分的时间关系作为染色体的基因位,问题的所有的多成分的时间关系就构成了算法的染色体,以求解关系矩阵中求到的相容子集的个数作为染色体的适应度。算法的终止条件是根据关系矩阵求得的相容子集数等于事件的个数,利用算法II使用遗传算法求解多成分时间规划问题。对实际的问题进行了讨论,使用该算法在有穷次迭代后可得到可行解。     

基于LSOT的高速IP路由查找算法

由于因特网速度不断提高、网络流量不断增加、路由表规模不断扩大，IP路由查找已经成为制约路由器性能的重要原因，因而受到广泛重视。目前人们已经提出几种算法用于解决IP路由查找问题，但均不能完全满足核心路由器的要求。该文提出一种基于LSOT的IP路由查找方法，它使用可变大小段表和偏移量表，能适应SRAM和FPGA芯片内存储器容量的变化，具有查找速度高、更新时间快、存储代价低、易于实现等特点，使用FPGA设计能满足10Gbps端口速率核心路由器环境的要求，使用ASIC设计能满足40Gbps端口速率核心路由器环境的要求。     

基于模式匹配的大规模数据分析软件设计与实现

在分析模式匹配算法的基础上,提出了一种改进的模式匹配算法,并将该算法应用于大规模数据分析软件设计之中。在数据分析的初始阶段,通过该模式匹配算法建立一张数据索引表,随后分析软件借助于索引表和帧结构分布表,对原始数据进行分析和处理。该算法的应用,有效的解决了大规模数据处理过程中的难题,提高了大规模数据处理软件的效率。     

基于检测点设置依赖图和属性表的卷回恢复算法

为了解决检测点设置过程中的Domino效应问题及卷回恢复过程中的活锁问题,并最大限度地减小时间开销,提出了基于检测点设置依赖图和属性表的卷回恢复算法。同以前的算法相比较,该算法一方面节省了用于进程之间同步的时间开销,另一方面检测点设置及卷回过程中涉及少量的相关进程。对该算法的正确性进行了证明。     

时间规划问题中R_时刻表及其应用

为了处理实际生活中出现的对有时间先后关系约束的事件进行排序的问题,诸如学校排课问题、运动会会场安排问题等一系列资源分配问题,文中实现了一种解决该问题的算法。该算法以文献[1]中的关系矩阵的方法为基础,构造以时间关系约束为条件的时刻表———R-时刻表的一种算法。利用该算法对运动会会场项目进行安排,结果表明在仅为时间关系约束的前提下取得了较好的效果,从而实现了对该类问题的一种新的解决方法。     

NTC温度转换的无损压缩解压缩算法

提出一种NTC(负温度系数热敏电阻)温度转换的无损压缩解压缩算法,主要用于在使用单片机进行温度转换时,将调用的表格数据进行压缩,解决了单片机A/D转换时存在的表格数据量大、占用存储空间大的问题。本算法大大压缩了表格的数据量,减少了单片机的内存空间使用,提高了单片机的利用率,降低了系统运行的出错率,同时也节省了单片机的使用成本。     

Program graph visualization

Although there are many algorithms to draw hierarchical structures such as directed graphs and trees none specifically treat the problem of visualizing program graphs. This paper presents an algorithm and the underlying tool — ViewGraph — designed to visualize program graphs. The algorithm is divided in two parts: (1) determine node positions, and (2) assign routes to branches. The first part has three steps: level assignment, scope and position calculation. A modified algorithm used to assign levels to nodes in a tree is used to find Y coordinates; a concept called scope is used to define X coordinates. Scope is a prediction of the space required by a node and its descendants. A search on the available positions left by the placement of nodes is performed to route branches. A set of aesthetic aspects meant to help the development of program graph visualization algorithms is also proposed. The algorithm runs in an acceptable time making it useful even for interactive applications. © 1997 John Wiley & Sons, Ltd.