Workload distribution of discrete‐time parallel queues with two servers

We study discrete‐time, parallel queues with two identical servers. Customers arrive randomly at the system and join the queue with the shortest workload that is defined as the total service time required for the server to complete all the customers in the queue. The arrivals are assumed to follow a geometric distribution and the service times are assumed to have a general distribution. It is a no‐jockeying queue. The two‐dimensional state space is truncated into a banded array. The resulting modified queue is studied using the method of probability generating function (pgf) The workload distribution in steady state is obtained in form of pgf. A special case where the service time is a deterministic constant is further investigated. Numerical examples are illustrated. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 440–454, 2000     

累积和检验算法应用于主动声纳检测时的性能

研究了一种基于瞬态信号检测的累积和序贯检测器,其检验统计量由归一化匹配滤波器输出决定,受到声纳方程估算的信噪比影响.从理论上分析了该算法的虚警和检测性能,并和归一化匹配滤波器作了比较.海试数据的验证结果表明,该算法检测性能优于归一化匹配滤波器,并且对混响有较好的抑制作用.     

带数据传输的光学卫星成像调度系统关键技术研究

针对光学小卫星成像调度系统设计需求,考虑侧视、存储容量、能量和数据传输等复杂约束,面向小规模问题应用,设计了问题求解流程.建立了顶点和边都带权的成像约束图模型,并提出了基于标记更新最短路算法的复杂约束成像卫星调度算法解决成像方案生成过程;对数传方案生成过程,给出背包模型并采用带回看策略的贪婪启发式方法进行问题求解.实验结果表明,该方法是可行和适用的.     

改进Dijkstra算法在大型城市轨道交通网计价系统中的应用

随着城市地铁建设的迅猛发展,国内众多城市地铁线路均已实现网络化运营。考虑到地铁票价制定的公益性,目前国内大部分城市均以最短路径或最少车站的方式计算线网两车站间的票价。以传统的Dijkstra算法为基准,对传统的Dijkstra算法进行改进,分别采用传统Dijkstra算法和改进Dijkstra算法对长沙地铁1～5号线线网最短距离行走路线进行测算。结果表明,改进后的Dijkstra算法不仅有效地提高了算法的时效性,克服了传统算法时间冗长的缺陷,在一定程度上消除了线路之间累积的误差且提高了线网的可延展性。     

Formulations for dynamic lot sizing with service levels

In this article, we study deterministic dynamic lot‐sizing problems with a service‐level constraint on the total number of periods in which backlogs can occur over a finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS‐SL‐I) and study the structure of its solution. We show that an optimal solution to this problem can be found in \begin{align*}\mathcal O(n^2\kappa)\end{align*} time, where n is the planning horizon and \begin{align*}\kappa=\mathcal O(n)\end{align*} is the maximum number of periods in which demand can be backlogged. Using the proposed shortest path algorithms, we develop alternative tight extended formulations for LS‐SL‐I and one of its relaxations, which we refer to as uncapacitated lot sizing with setups for stocks and backlogs. {We show that this relaxation also appears as a substructure in a lot‐sizing problem which limits the total amount of a period's demand met from a later period, across all periods.} We report computational results that compare the natural and extended formulations on multi‐item service‐level constrained instances. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013