带圆周约束的Steiner树问题

本文首先考虑了带圆周约束的Steiner树问题．设欧氏平面上有一圆，平面上有n个点，所成点集为N，该问题是要在圆周上找一点P，使NU{P}这n 1个点的Steiner树之长度达到最短．本文对干n=2的情形给出解．另一方面，鉴干问题的复杂性为NP-C，作者提出了一个近似解，并证明了近似解的性能比为（3的平方根）／2。     

工件带到达时间的两阶段柔性流水作业的近似算法

研究了工件带到时间的两阶段柔性流水作业的排序问题,基于求解流水作业和平行机问题的算法思想,提出两个相应的近似算法H(R)和H(MR(?)),证明了这两个算法的最坏情况性能比分别为3-1/m和2/5-1/m,讨论了界的紧性,并利用数值模拟以分析算法与最优值的近似性能比.     

总延误问题顺时安排法的性能比

给定一组工件的加工时间与工期，要求确定这些工件在一台机器上的加．工排列，使相应的总延误达到最小，这就是总延误问题．该问题在近年已被证明是NP困难的．由Wilkermn和Irwin（1971），林勋（1983）等所研究的顺时安排法能得到相邻交换意义下的局部解．在本文中，我们进一步证明该算法能得到前移邻域意义下的局部解，并确定了该算法的性能比．     

网格空间瓶颈斯坦纳树问题快速近似（英文）

指出了瓶颈斯坦纳树问题要求寻找一棵用至多k个斯坦纳点将n个点连接起来使得此斯坦纳树之最长边最短的斯坦纳树,该问题在VLSI、无线通讯网络和生命演化树重建等领域都有应用.Du和Wang证明网格空间瓶颈斯坦纳树问题是NP-Hard,不存在近似性能比低于2的多项式时间解决方案,并且提出一个近似性能比为2的多项式时间近似算法,算法的实际时间复杂度为O(nlog2n+kn+k2).通过引入二叉堆和斐波那契堆使算法的时间复杂度分别改进到了O(nlog2n+klog2n)和摊还时间O(nlog2n+klog2n).该改进可直接应用于欧几里得平面的瓶颈斯坦纳树2-近似算法.     

一类装配式流水作业排序问题的启发式算法及其性能比研究

根据Ｆ′２｜ｍ１≥２，ｍ２＝１｜Ｃｍａｘ排序问题是ＮＰ完全问题的论断，提出了ＡＦＳ问题的两个启发式算法，分别给出了应用启发式算法的实例，并证明了该启发式算法在最坏情况下的品性是２的结论     

关于一类表调度问题的浅析

调度问题在实际的社会、经济、生活领域有着非常重要的作用。举例说明：对于装配有多条流水线作业的企业而言，如何有效地利用现有机器设备以最小时间代价生产出尽可能多的产品，以期提高企业竞争力，扩大经济利润一直都是企业界关注的问题。本文主要介绍了一类由Graham提出的表调度问题以及启发式算法的最坏性能比。     

工件有到达时间的两机器自由作业稠密时间表

对于两机器自由作业加工总长问题，工件带有到达时间，我们证明了稠密时间表的性能比为1.5。     

带约束的平行机排序问题

讨论了带资源约束和机器准备时间的平行机排序问题，资源约束是指每个机器最多加工κ个工件．首先对一般情况下的同型机的PLPT排序进行了讨论；并首次对同类机排序进行了研究，给出了一个FLPT近似算法，同时对m=2时证明了PLPT排序的最坏情况紧界是2．     

物理学奖：玩出个未来

有一种材料，导电性能比所有金属都高出不少，强度比钢铁强上百倍，导热性能超过我们所熟知的一切物质。它的厚度只有百亿分之三米，是人们能够制造出来的最薄的材料。然而，只要仔细检查铅笔，就能找到它的痕迹。这就是石墨烯，由碳原子构成的二维结构，也许将会把人类带入全新的太空时代和更快的信息时代的超级明星。我们这颗星球上所有的生命的基础是碳，我们使用的电能有2／3来源于各种碳的沉积；     

平行机的实时到达on-line算法下界的改进

本文考虑了平行机实时到达的在线问题,模型中,工件是陆续到达的,工件的个数,到达时间是事先未知的,而且只有当工件到达,才知其加工时间,目标是使所有工件都加工完成的时间达到最小。