模糊最短路的一种算法

模糊最短路问题在许多领域有着广泛的应用,研究这一问题具有重要意义。根据多准则决策理论求非被支配路径集合,求最大效用模糊最短路以及利用模糊数排序方法求模糊最短路是常用的三种研究方法,本文利用OERI排序原理,使网络模糊边长具有线性可加性,对具有三角模糊数边权的网络给出了一种标号算法,该算法简单高效,且易于在计算机上实现,算法的时间复杂度为O(n^2)。     

关于《偏序集上的一种拓扑排序》一文的几点意见

就文献《偏序集上的一种拓扑排序》一义提出了几点看法，探讨了文献中给出的祖先数算法、支配排序算法中的问题，并就其中的dominate函数、函数的时间复杂度的计算以及文献中给出的定理2的正确性进行了分析和论证，并指出了文献中所举例子中存在的差错．最后，对拓扑序列的合理性做了简单的讨论．     

机器和工人都有加工资质约束的平行机排序问题研究

研究一类新型的平行机排序问题, 即在机器和工人都是必需的加工资源并且都有加工资质约束的情况下, 如何在一组平行机上进行工件排序(或称调度)以最小化时间表长C_max. 将研究工件加工时间均为单位时间的情况, 通过建立网络流模型以及采用二分搜索技术, 可以在多项式时间内精确地求解上述问题, 算法复杂度为O(n^{3}logn). 同时提供了一种基于双重动态柔性选择\,(DDFS)\,策略的启发式算法,可以获得较好的排序效果, 算法复杂度为O(n^{2}).     

处理机具有不同开始加工时间的可中断排序问题

本文对处理机具有的不同开始加工时间的可中断排序问题进行讨论，得到下面结论：若处理机具有相同开始加工时间的可中断排序问题存在最优排序算法，则相应的处理机具有不同开始加工时间的可中断排序问题也存在最优排序算法。     

具有时间与位置相关的两类平行机排序问题

研究带有维修时间限制的时间和位置效应平行机排序问题,涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响,且机器具有维修限制.目标函数由机器负载,总完工时间与总等待时间组成.非同类机情形下,通过将排序问题转化为指派问题,给出多项式时间算法,其算法的时间复杂度为O（n^k+2/（k-1）!）.同型机情形下通过转化目标函数,使用匹配算法得出排序问题的多项式时间解,其时间复杂度为O（（2n+m+n log n）n^k-1/（k-1）!）.     

具有优先约束的不完全恒速机排序问题

讨论了任务具有优先约束的可中断不完全恒速机排序问题,若处理机具有不同开始加工时间的可中断排序问题存在最优算法,则相应的不完全恒速机排序问题也有最优算法。     

基于消费者多维度偏好的个性化评论排序方法研究

海量评论数据导致了信息过载,基于消费者的偏好对评论进行个性化排序尤为必要。本文考虑消费者多维偏好,即产品特征偏好、评论情感偏好和评论浏览数量偏好,提出了评论排序的消费者偏好满意度量化方法,将排序问题转化为最大化满意度的优化问题,鉴于问题的复杂度无法精确求解,提出了一个基于改进贪婪算法的近似求解算法。采用美团网酒店的评论数据进行实验,结果显示本文提出的算法与其他相关算法相比有效性显著提高,且具有较高的敏感度。研究结果对消费者提高决策效率,以及电商平台获取消费者偏好、改进评论系统,有着重要的现实指导意义。     

具有指数和位置学习效应的机器排序问题

本文考虑指数学习效应和位置学习效应同时发生的新的排序模型.工件的实际加工时间不仅依赖于已经加工过工件正常加工时间之和的指数函数,而且依赖于该工件所在的位置.单机排序情形下,对于最大完工时间和总完工时间最小化问题给出多项式时间算法.此外某些特殊情况下,总权完工时间和最大延迟最小化问题也给出了多项时间算法.流水机排序情形,对最大完工时间和总完工时间最小化问题在某些特殊情形下给出多项时间算法.     

极小化最大提前完工费用的可中断排序问题

讨论了带截止期限的$n$个工件在单机上加工,工件间存在优先约束,在允许机器空闲的条件下,确定一个工件的可中断排序,极小化最大提前完工费用.首先考虑两种特殊情形:(1)截止期限相同,存在优先约束;(2)截止期限任意,不存在优先约束.针对两种情形分别给出了时间复杂度为$O(n^2)$的算法.在此基础上,考虑普遍情形,即截止期限任意,存在优先约束,也给出了一个时间复杂度为$O(n^2)$的算法.由于工件不允许延迟,问题可能会无可行排序,需先对问题的可行性进行讨论.     

处理机具有准备时间的Qm,aj｜pj=1｜Cmax排序问题

讨论了处理机具有准备时间的Qm,aj|pj=1|Cmax排序问题,通过这一问题的一个下界,给出了一个最优算法,算法的复杂性为O（m^2）。     

基于代数曲线上具有高广义联合线性复杂度的多重序列

多重序列的联合线性复杂度是衡量基于字的流密码体系安全的一个重要指标. 由元素取自F_q上的m 重序列和元素取自F_q^m 上的单个序列之间的一一对应, Meidl 和Özbudak 定义多重序列的广义联合线性复杂度为对应的单个序列的线性复杂度. 在本文中, 我们利用代数曲线的常数域扩张, 研究两类多重序列的广义联合线性复杂度. 更进一步, 我们指出这两类多重序列同时具有高联合线性复杂度和高广义联合线性复杂度.     

基于熵算法的股票指数高频数据复杂度测算与评价

在日内高频环境下检验基于兼容法的柯尔莫哥洛夫熵、样本熵和模糊熵等复杂度测算方法对我国沪深300股票指数的测算效率,并运用筛选后的有效算法分阶段研究和比较了序列复杂度的变化过程与变化幅度.结果表明,模糊熵算法是一种更适用于我国沪深300股票指数的有效复杂度测算方法,其对相似容忍度的敏感性更低,测度值连续性更好.随时间推移,我国沪深300股票指数复杂度整体呈上升趋势,而相较于发达市场甚至周边新兴市场其复杂度偏低.     

Applying and assessing two methods for measuring complexity in manufacturing

Previous work in manufacturing has identified complexity as a relevant topic in this field. However, there is a high diversity of opinions on what complexity is, why it should be measured and how this can be done. This paper aims to contribute to a better understanding of manufacturing complexity and of the relationship between the system's complexity and its performance. Firstly, we identify the various aspects of manufacturing complexity highlighted in the literature. Secondly, we describe two complementary methods for measuring complexity, and the adaptation and application of these methods in a case study. The issues involved in applying the methods and the insights gained are also discussed. The main criteria considered in assessing the two methods are: methodology, costs, feasibility, type of information required, and the type of results they provide. We conclude by outlining the requirements that a complexity assessment method must meet in order to address all the complexity issues identified.     

Pendants-median支撑树及其一个相关问题:复杂性和算法

The complexity status of Pendants-median spanning tree problem is an open problem. Using the complexity of the X3C problem, the paper proves that Pendants-median spanning tree problem is NP-complete. Global-median spanning tree problem is a related problem. Using the complexity of 3SAT, the paper proves that this problem is also NP-complete, and a polynomial -time algorithm to this problem is given, whose time complexity is O(n^3).     

Stability and complexity in ecological systems

The paper attempts to answer an outstanding question in theoretical ecology whether structural complexity is essential for dynamical complexity to exist. Advances in dynamical systems theory and their application to ecosystem analysis has enabled us to have a better grasp of the concept of dynamical complexity. Our basin boundary calculations indicate that structural complexity is not necessary for dynamical complexity to exist. Very simple ecosystems can display dynamical behaviour which is unpredictable in certain situations. In certain cases, when riddled basins are found, even qualitative predictability is denied.     

Monte Carlo Complexity of Global Solution of Integral Equations

The problem of the global solution of Fredholm integral equations is studied. This means that one seeks to approximate the full solution function (as opposed to the local problem, where only the value of the solution in a single point or a functional of the solution is sought). The Monte Carlo complexity, i.e., the complexity of the stochastic solution of this problem, is analyzed. The framework for this analysis is provided by information-based complexity theory. The investigations complement previous ones on the stochastic complexity of the local solution and on deterministic complexity of both local and global solutions. The results show that even in the global case Monte Carlo algorithms can perform better than deterministic ones, although the difference is not as large as in the local case.     

Behavior of the extended complexity of irreducible 3-manifolds

We construct the extended complexity of irreducible 3-manifolds; unlike the usual complexity [1] it is not an integer, but an ordered tuple of five integers. The benefit of extended complexity is that it always decreases when a manifold is cut along some incompressible boundary incompressible surface.     

The complexity of social groups and social systems described by graph structures

This paper presents methodology which permits the complete ranking of nondirected graphs (NDG's) on an attribute labelled ‘complexity.’ The technique applies to both small and large systems as might arise in studies of group or organization behavior. The methodology extends to cover the complexity of directed graphs (DG's) and permits the detailed specification of individual and group behavior.For the NDG an abstract automaton representing the participants' interaction or communications function is sited at each node. Each automaton is constructed so its internal complexity is sufficient to realize the minimal social action (e.g. transmission of a rumor and the path followed by the rumor) within the framework of the NDG. It is shown that the complexity of each node automaton depends upon the order of the graph, the degree of the node and the longest path parameter of the graph. The combined complexity of node automata constitutes the complexity of the NDG. The complexity of a DG is specified as a composition of complexities computed for the associated NDG and logical devices which produce the observed behavior. Illustrative examples pertaining to the committee-subcommittee problem and to organizational structures are presented.     

Generating Functions for Computing the Myerson Value

The complexity of a computational problem is the order of computational resources which are necessary and sufficient to solve the problem. The algorithm complexity is the cost of a particular algorithm. We say that a problem has polynomial complexity if its computational complexity is a polynomial in the measure of input size. We introduce polynomial time algorithms based in generating functions for computing the Myerson value in weighted voting games restricted by a tree. Moreover, we apply the new generating algorithm for computing the Myerson value in the Council of Ministers of the European Union restricted by a communication structure.