联合补充博弈的费用分摊

就一个仓库、多个零售商,对联合订货费用函数的模型进行分析,给出了一个求解最佳订货周期的多项式时间的算法,且算法的时间复杂性为O（nlogn）。利用文献[8]中的技巧,给出了该库存博弈的核。     

Scheduling parallel machines with inclusive processing set restrictions

We consider the problem of assigning a set of jobs to different parallel machines of the same processing speed, where each job is compatible to only a subset of those machines. The machines can be linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process. The objective is to minimize the makespan of the schedule. This problem is motivated by industrial applications such as cargo handling by cranes with nonidentical weight capacities, computer processor scheduling with memory constraints, and grades of service provision by parallel servers. We develop an efficient algorithm for this problem with a worst‐case performance ratio of + ε, where ε is a positive constant which may be set arbitrarily close to zero. We also present a polynomial time approximation scheme for this problem, which answers an open question in the literature. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

一类典型结构矩阵的WZ分解

WZ类矩阵分解是设计线性方程组求解中一类并行算法的数学理论基础。针对对称p-三对角矩阵,提出并证明该类典型结构矩阵的WZ分解式及其性质。进一步,当实对称p-三对角矩阵正定时,证明其WZ分解式中W因子具有元素均为实数的特点;当W因子对角线元素均为正实数时,分解式惟一。     

一种改进的旋转CRC数据校验设计方法

旋转CRC同时使用两个生成多项式产生校验数据。之前的方法校验能力弱,报文丢失后的检错失效率很高。提出了一种新的旋转CRC设计方法,通过比较,选取合适的更高次的生成多项式组合,并且修改了检验生成与检测机制,形成MR-CRC。FPGA实现结果表明,这种方法能够在较低逻辑复杂度的基础上提高校验能力,从而改善数据通信的可靠性,而且对系统性能影响甚小。通过比较16位MR-CRC与32位传统CRC的实现数据发现,前者在所用资源减少10%的情况下,频率提高了25%。     

The knapsack problem with a minimum filling constraint

We study a knapsack problem with an additional minimum filling constraint, such that the total weight of selected items cannot be less than a given threshold. The problem has several applications in shipping, e‐commerce, and transportation service procurement. When the threshold equals the knapsack capacity, even finding a feasible solution to the problem is NP‐hard. Therefore, we consider the case when the ratio α of threshold to capacity is less than 1. For this case, we develop an approximation scheme that returns a feasible solution with a total profit not less than (1 ‐ ε) times the total profit of an optimal solution for any ε > 0, and with a running time polynomial in the number of items, 1/ε, and 1/(1‐α). © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

机动目标状态估计的最小均方误差界

基于多项式模型的各种自适应滤波算法被广泛应用于机动目标跟踪领域,但尚没有统一的评估标准来衡量这些跟踪算法的优劣。由于存在确定的时变未知输入,机动目标的状态估计实际为有偏估计。基于状态估计均方误差最小的准则,推导了多项式模型滤波的最小均方误差界计算方法,获得了使状态估计均方误差最小的过程噪声方差变化规律。该方法给出了各种基于多项式模型的机动目标跟踪算法的估计均方误差下限,也为机动目标跟踪中最优过程噪声方差的设定提供了依据。仿真结果验证了算法的有效性。     

正切函数的契比协夫逼近及其系数的加速计算法

本文给出正切函数的有理展开和契比协夫展开式系数的加速计算方法;同时在YH-1机上进行了数值试验,结果表明:用现在的系数来计算正切函数,其精度比原来正切函数的精度可提高30%左右。     

判断实对称矩阵为正定、半正定、负定、半负定或不定的一个算法

给出判别实对称矩阵为正定、半正定、负定、半负定或不定的一个算法;采用选最大对角元的方法,可使数值计算稳定性好。讨论了该算法的运算量,得到乘除法和加减法总次数分别至多为ｎ（ｎ－１）（ｎ＋４）／６和ｎ（ｎ－１）（ｎ＋１）／６的结论。最后给出运行该算法的数值例子。     

Production scheduling with history‐dependent setup times

We consider a parallel‐machine scheduling problem with jobs that require setups. The duration of a setup does not depend only on the job just completed but on a number of preceding jobs. These setup times are referred to as history‐dependent. Such a scheduling problem is often encountered in the food processing industry as well as in other process industries. In our model, we consider two types of setup times—a regular setup time and a major setup time that becomes necessary after several “hard‐to‐clean” jobs have been processed on the same machine. We consider multiple objectives, including facility utilization, flexibility, number of major setups, and tardiness. We solve several special cases assuming predetermined job sequences and propose strongly polynomial time algorithms to determine the optimal timing of the major setups for given job sequences. We also extend our analysis to develop pseudopolynomial time algorithms for cases with additional objectives, including the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

偶变元MAI旋转对称布尔函数

代数免疫度是布尔函数的一个重要密码学指标.给出了具有最大代数免疫度的偶数元旋转对称布尔函数的两种构造方法.进一步地,研究了特殊情形时所构造的旋转对称布尔函数的非线性度,当n≥18时,构造3得到的MAI旋转对称布尔函数的非线性度优于已知构造的偶数元MAI旋转对称布尔函数的非线性度.