摘要：尝试性地将设计结构矩阵应用于业务流程优化设计中的拓扑排序问题,提出了基于设计结构矩阵(DSM)的拓扑排序新方法,并设计了邻接矩阵方法运算规则.与传统方法比较,它不仅克服了传统算法对环路的限制,而且由于其从两个方向同时搜索,设计思路简单、效率高,为设计结构矩阵在业务流程优化中的应用进行了积极的探索.

摘要：针对实际装配环境中存在多人协同装配和共站的情况,研究了考虑工序复杂程度与工人能力差异的多人协作共站装配线平衡问题。首先,考虑到装配工序的复杂程度需指派不同规模和类型的工人组,建立了以最小化工作站数量和工人数量为目标函数的多目标优化数学模型;在此基础上,提出一种改进的离散水波优化算法,对算子进行了离散化改造,并设计了基于拓扑排序的编码方案和启发式的解码方案,同时引入扰动个体和路径重连的搜索策略来增加解的多样性,进而提高解的质量;最后,通过求解两类测试用例,以线效率和平滑指数作为性能指标,验证了改进离散水波算法在求解复杂多人共站装配线平衡问题上的可行性与有效性,并将算法应用到动车装配线平衡优化中。

摘要：针对工艺设计中的工艺路线优化问题,归纳了工步间的基本优先级约束关系。基于约束关系,将整个工艺活动过程转化为工步有向图,工步节点间的拓扑关系以约束矩阵的形式存储。提出了约束矩阵判错的检测方法;建立了工步图的拓扑排序模型。设计了一种随机的深度优先搜索算法对工步图进行拓扑排序,得到全部可行的一定数目初始工艺计划作为遗传算法的初始种群。算法中,提出了基于车间动态资源的加工序列编码策略;定量分析了工艺计划评价准则,采用罚函数的方法将目标函数和约束条件建立成一个无约束的优化目标函数,由此确定了染色体的适应度函数;设计了遗传操作算子(选择、交叉、变异),并通过基于模拟退火机制的精英策略加速算法收敛。最后,通过实例证明了该算法的有效性。

摘要：本文基于异步通讯的分布式计算模型,对AOE 网的拓扑排序问题,提出了一个分布式算法。设计此算法的关键是使用了一种动态生成树结构。算法的通讯复杂性是O(dm),时间复杂性为O(d^2)。这里d 是网络的直径,m 是网络的通讯链数目,n 是网络中处理机数目(d<n)。

摘要：针对网格工作流调度、生产和施工计划的制订等领域的特殊需求,引入了一类顶点带层次的AOV网络-LAOV网络。本文对AOV网络、层次、LAOV网络进行了严格的定义,并对顶点层次取值的几种情形作了详细的讨论。然后针对其中一种合理情形的LAOV网络提出了拓扑排序算法,讨论了栈或队列的选择、有向回路的判定等问题,并分析了算法的复杂度。最后对LAOV网络及拓扑排序算法进行实验分析。因为算法输出的解不唯一,在实验分析时设计了评判程序对算法输出进行验证。实验分析结果表明算法是正确的,时空效率也比较好。

摘要：目的利用元胞自动机的特性,找到一种新的拓扑排序算法。方法将AOV网构造成一个元胞自动机模型,采用经过改造的邻接链表作为元胞的数据结构,并在其中引入随机编号项,所有元胞依据随机编号顺序地遵守演化规则进行演化,实现拓扑排序。结果利用元胞自动机的时空局部规则和并行计算特性,设计并验证了拓扑排序算法。结论与传统算法相比本算法在时间、空间复杂性上都有较大改善,并且在应用元胞自动机理论解决图的问题方面有所贡献。

摘要：文章对AOV网首次提出了一种基于层次的混合数据结构,按分层处理的方法实现并行拓扑排序算法PTSA,求得了AOV网中顶点的所有拓扑序列,克服了以往基于栈结构只能求得一种拓扑序列的缺陷。PTSA算法为工程中各子工程的串行或并行安排提供了确定的选择,提升了拓扑排序算法的实用价值。

摘要：拓扑排序是用来检查AOV网中是否存在回路,从而确定AOV网所表示的工程是否能够实现的程序设计方法。现有拓扑排序的结果只是一个线性序列,在每个阶段只能进行一种活动,在实际应用中有一定的局限性。本文给出对拓扑排序功能进行扩展的一种程序设计方法,从而可以确定不同阶段同时进行多个活动的方案设计。

摘要：本文讨论了伴随链置换和固定交换次数置换化归为传统的拓扑排序的问题,并给出了相应的算法.本文的结果还体现了经典拓扑排序算法的一种应用.

摘要：为了提高现有OpenModelica软件对DAE系统的预处理模块中求强连通分量与拓扑排序部分的性能,提出了基于Ko-saraju算法实现的策略。阐述了Modelica软件的实现原理,叙述了拓扑排序相关算法在其中的重要性,分析了现有Modelica软件中使用的求强连通分量与拓扑排序部分的算法,比较了Tarjan算法的实现方案与Kosaraju算法实现方案。对两种方案进行了比较和分析结果,表明了Kosaraju算法方案的可行性和有效性。