成组加工中带可分配工期的最大延误问题

研究成组加工中带可分配工期的最大延误问题的排序与工期分配,对于成组加工中带可分配工期的最大延误问题的不同模型,或给出其最优序．或证明其是NP-难问题．     

延误工件个数与最大加工时间压缩比例之和的可控排序

研究工件加工时间可控的排序问题，讨论的目标函数是延误工件个数与最大加工时间压缩比例之和，证明这一问题是多项式时间可解的。     

加工时间可控的单台机器排序问题的近似算法

本文研究加工时间可控的单台机器的赋权的总完工时间问题.它是一个NP 难问题.我们利用半定规划松弛的技巧给出它的一个1.2752-近似算法.     

成组加工中的加工全程和延误工件数问题

本文在同组工件连续加工的条件下考虑了单机加工中的二个排序问题,其目标函数分别为极小加工全程和延误工件数。文中在不同的条件下对它们给出了多项式时间算法。     

一台机器在加工时间相同准备时间可控时的Lmax问题

一组ｎ个工件需在一台机器上加工，工件ｊ所需的加工时间，应交工时间、准备时间分别为ｐｊ、ｄｊ、ｒｊ＾０，准备时间可压缩量为ｘｊ，０≤ａｊ≤ｒｊ＾０，压缩权因子为ωｊ由最大延误Ｊｍａｘ和压缩费用∑ωｊｘｊ可构成文中（Ｐ１）－（Ｐ３）三个排序问题，在ｄｊ＝０的条件下，引文「１」的作者证明了（Ｐ１）、（Ｐ３）为强ＮＰ－Ｃ的。本文在ｄｊ任意，ｐｊ＝ωｊ＝１的条件下，对（ｐ１）－（Ｐ３）给出了一个伪多项式时间     

单台机器E-T随机排序问题的多项式算法

本文研究排序问题中的E—T问题，工件在单台机器上加工，n个工件的加工时间都为整数P，相同的工期d为离散分布，满足∑i=1^mP（d=ξi）=1,其中ξ为整数，目标是使E（∑（Ei＋Tj））的期望值最小。应用贪婪算法和二分法思想，我们提出解决该问题的一个最优算法，并得出该算法的复杂性为O（nmlogp）。     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．     

线性规划问题的规范型算法

提出了线性规划问题的两种规范标准形式；证明了任意一个线性规划问题都可化为这两种形式之一；给出了不需引入人工变量的线性规划问题的求解算法。     

非线性加工时间单机排序问题

讨论工件加工时间是等待时间的非线性增加函数的单机排序问题,目标函数为极小化完工时间和与极小化最大延误.基于对问题的分析,对于一般非线性函数的情况,给出了工件间的优势关系.对于某些特殊情况,利用工件间的优势关系得到了求解最优排序的多项式算法.推广了文献中的结论.     

目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法

单台机器带一个维修时间段的排序问题,目标是最小化所有工件的运输时间和.在这篇文章里,重新研究了该问题,并给出了一个时间复杂性为O（n³）的近似算法,将性能比从3/2改进到5/4.     

分派问题的一个简单算法

本文给出了分派问题的一个新算法，这个算法是初等的，且便于使用和编程上机操作，尤其适合于较低阶分派问题．     

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

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

带核集分划问题的一个线性1／7近似算法

设有整数集Ｓ＝｛ｒ１，ｒ２；ｐ１，ｐ２，…，ｐｎ｝，这里ｒｉ≥０，ｐｊ＞０（ｉ＝１，２；ｊ＝１，２，…，ｎ），寻找一个Ｓ的最优分划Ｐ＝（Ｓ＊１，Ｓ＊２）使得：（１）ｒｉ属于不同子集，（２）Ｓ＊１与Ｓ＊２中元素总和较大者尽可能地小．这是一个ＮＰ－完备问题，本文给出一个线性时间近似算法，它的近似界为８７．     

一个宽容交货超前延误单机排序问题

此文考虑下述排序问题（P）：有n个工件需在同一台机器上加工,对各工件有一共同的宽容交货期。若一工件在此宽容期前完工则为一超前工件,若在此宽容期后完工则为一延误工件,要求适当安排一加工方式和宽容交货期的位置使加权超前延误工件数量小。文中证得（P）是NP-hard的,并给出一伪多项式时间的分枝状精确算法,这也就可以认为它是一般意义下的NP-hard问题而不是强NP-hard问题。     

THE EIGENVALUE PROBLEM EQUIVALENT TO MULTIVARIATE POLYNOMIAL SYSTEM

In this paper, the authors proved that finding all solutions of a given multivariate polynomial system is equivalent to solving a relative joint eigenvalue problem(Theorem 1) and in some cases one can find all solutions of the given system from the eigenvalues and vectors of one matrix or matrix pencil (Theorem 2). Especially the situation that the ideal generated by the given system is 0-dimensional is discussed.     

带约束的平行机排序的一个近似算法

讨论有资源约束和有机器准备时间的平行机排序问题,资源约束为每个机器至多可加工k个工件,在极小化makespan的上给出了一个匹配算法,证明其最坏情况最紧界是2-m^-1,并进一步给出了它的两个带参数的最坏情况界。     

稳定性判定与多项式求根算法

本文给出了一种判定多项式根是否全在单位圆内的简便方法．该方法可用于判定离散控制系统的稳定性和求多项式的全部根。     

二供应商经济批量问题的多项式时间算法

为了从采购费用结构不同的供应商中找到最佳补货策略,考虑一个零售商从两个供应商补货的二供应商经济批量问题.零售商在两个供应商处的采购费用结构分别为复合安装费用和全单位数量折扣费用结构.通过对问题结构性质的分析论证,将问题的可行解转化为一个有向网络,降低问题求解的计算复杂性.综合动态规划和Dijkstra最短路算法证明了该问题是多项式时间可解的.     

二元整系数多项式因式分解的一种理论和算法

我们发现可以把二元多项式盾成系数为一元多项式的一元多项式来进行分解，据此，本文建立了二元整系数多项式因式分解的一种理论，提出了一个完整的分解二元整系数多项式的算法。这个算法还能很自然地推广成分解多元整系数多项式的算法。     

ON CONVERGENCE OF NOUREIN ITERATIONS FOR SIMULTANEOUS FINDING ALL ZEROS OF A POLYNOMIAL

1. IntroductionSuppose thatn nf(t) = bait"--' = fi(t -- (i), ac = 1 (1)i=0 j=1is a monic polynomial of degree n with complex coefficients. Some authors have studiedthe parallel iterations without derivatives for simultaneous finding all zeros fi, (2,'. 5 (nof f(t) (see [1]--[10],[13], [14], [16]). The famous one is Durand-Kerner iteration withthe formxt ' = xo ~ ac i = 1,2,' ',n? k ~ 0, 1,' t (2)where xo is the k--th approximation of fi(1 5 i 5 n) andf(xf)ac = M, i = 1,' 'In, k ~ 0,1,..…