Minimizing sums and products of linear fractional functions over a polytope

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999     

Coordinated replenishments from multiple suppliers with price discounts

In this study we present an integer programming model for determining an optimal inbound consolidation strategy for a purchasing manager who receives items from several suppliers. The model considers multiple suppliers with limited capacity, transportation economies, and quantity discounts. We propose an integrated branch and bound procedure for solving the model. This procedure, applied to a Lagrangean dual at every node of the search tree, combines the subgradient method with a primal heuristic that interact to change the Lagrangean multipliers and tighten the upper and lower bounds. An enhancement to the branch and bound procedure is developed using surrogate constraints, which is found to be beneficial for solving large problems. We report computational results for a variety of problems, with as many as 70,200 variables and 3665 constraints. Computational testing indicates that our procedure is significantly faster than the general purpose integer programming code OSL. A regression analysis is performed to determine the most significant parameters of our model. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 579–598, 1998     

Scheduling deteriorating jobs to minimize makespan

We consider a single-machine problem of scheduling n independent jobs to minimize makespan, in which the processing time of job J_j grows by w_j with each time unit its start is delayed beyond a given common critical date d. This processing time is p_j if J_j starts by d. We show that this problem is NP-hard, give a pseudopolynomial algorithm that runs in time and O(nd) space, and develop a branch-and-bound algorithm that solves instances with up to 100 jobs in a reasonable amount of time. We also introduce the case of bounded deterioration, where the processing time of a job grows no further if the job starts after a common maximum deterioration date D > d. For this case, we give two pseudopolynomial time algorithms: one runs in O(n²d(D − d) time and O(nd(D − d)) space, the other runs in p_j)²) time and p_j) space. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 511–523, 1998     

Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem

Scheduling a set of n jobs on a single machine so as to minimize the completion time variance is a well‐known NP‐hard problem. In this paper, we propose a sequence, which can be constructed in O(n log n) time, as a solution for the problem. Our primary concern is to establish the asymptotical optimality of the sequence within the framework of probabilistic analysis. Our main result is that, when the processing times are randomly and independently drawn from the same uniform distribution, the sequence is asymptotically optimal in the sense that its relative error converges to zero in probability as n increases. Other theoretical results are also derived, including: (i) When the processing times follow a symmetric structure, the problem has 2^{⌊(n−1)/2⌋} optimal sequences, which include our proposed sequence and other heuristic sequences suggested in the literature; and (ii) when these 2^{⌊(n−1)/2⌋} sequences are used as approximate solutions for a general problem, our proposed sequence yields the best approximation (in an average sense) while another sequence, which is commonly believed to be a good approximation in the literature, is interestingly the worst. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 373–398, 1999     

面向多星观测调度的分层迭代算法

提出一种基于分治策略的多星观测分层调度框架,在该框架下,用蚁群优化算法把任务分配至各轨道圈次上,并利用自适应模拟退火算法求解各轨道圈次的调度问题。根据各轨道圈次调度结果的反馈情况,再调整任务分配方案,重复上述过程直到达到算法终止条件。为了提高算法的性能,在设计蚁群算法的启发式信息模型时,应充分考虑卫星调度问题的领域知识;在模拟退火算法中设计两个邻域结构,采用动态选择策略在优化过程中确定最佳邻域搜索结构。仿真实验表明,该方法有效地降低了问题求解的复杂度,尤其在求解大规模多星观测调度问题时表现出优异的性能。     

SpaceWire网络混合路由机制设计

针对星上系统总线多元性导致的星载网络接口和协议不能标准化的发展瓶颈,基于SpaceWire总线协议,通过将静态路由(时间触发)与动态路由(事件触发)机制结合,实现了控制数据和载荷数据共用网络。静态路由完全遵循SpaceWire-D协议,在保证确定性传输的同时,通过启发式调度算法首次实现了多时间窗并行调度,并提出利用最大公约数法设计时间窗,以提高网络吞吐量;动态路由通过对随机事件和载荷数据分配优先级,实现传输路径冲突时对紧急任务的优先处理。在OPENT中搭建网络系统仿真模型,对所提出的路由机制进行了仿真。实验结果表明,静态路由时段网络吞吐量较现有调度算法有明显提高,动态路由实现了紧急事件优先传输。     

低地球轨道卫星网络节能方法

通常卫星的唯一能源来源是太阳能,因此星上网络设备的能源供应问题比地面网络的更加严峻。通过修改和扩展链路容量受限的最小代价多商品流模型来适应卫星网络这一特殊的体系结构,并基于低轨道卫星网络的多重覆盖机制和流量分布模型,改进现有的启发式算法来关闭冗余的卫星节点、星地链路和星间链路。在满足链路利用率和路由跳数增加比例约束的条件下,仿真实验中关闭上述三种参数的比例分别可达59%、61%和72%,卫星网络的总体节能比例可达65%。     

多输入多输出雷达恒模稳健波形联合优化算法

针对目标冲激响应及杂波冲激响应分布特性先验知识不准确导致的多输入多输出雷达检测性能下降的问题,提出恒模稳健波形与接收机滤波器联合优化算法。将目标冲激响应及杂波冲激响应分布特性先验知识不准确时的优化问题建模为一个极大极小化问题。运用迭代优化算法将联合优化问题分解为两个子优化步骤:将波形固定时的接收机滤波器权值优化问题建模为广义瑞利商模型,求解得到相应的接收机滤波器权值矢量;利用半正定松弛技术对权值固定时的波形优化问题进行求解,获得对应的波形矩阵,并根据得到的波形矩阵,通过高斯随机化的方法获得所需的恒模波形。对所提算法的收敛性进行了证明,仿真结果表明所提算法有效。     

火箭-双燃烧室冲压组合循环发动机概念研究

临近空间高超声速飞行器近年来获得了广泛关注,本文提出一种以基于火箭发动机和双燃烧室冲压发动机的多模态火箭-双燃烧室冲压组合循环发动机作为飞行器的动力系统,并进行了性能分析研究。该飞行器在海拔10 km左右高度以0.8马赫的速度投放,在重力和发动机推力的联合作用下,能够在海拔5～8 km处加速到2马赫;然后加速爬升进入临近空间,发动机工作在引射亚燃或者双燃烧室亚燃模态下。可以根据实际选择高推重比、较低推进剂比冲效率的引射亚燃模态,或是较低推重比、高推进剂比冲效率的双燃烧室亚燃模态。最终飞行器加速到6马赫(26 km),进入双燃室超燃模态。针对空中发射模式和地面发射模式进行了轨道优化,仿真结果表明:在加速爬升到6马赫(26 km)的过程中,空中发射模式相比较地面发射模式可以节省37%的推进剂;空中发射模式存在一个负的最优初始飞行角度使得剩余质量与初始质量的比值达到最大。     

采用遗传算法的弹托迎风窝结构设计

针对一体化弹丸弹托易分离性和轻质化的设计要求,构建弹托迎风窝参数化外形模型,基于激波和膨胀波理论建立弹托气动力计算模型;以弹托分离加速度和弹托质量综合最优为目标函数,采用遗传算法对弹托迎风窝的外形参数进行优化设计,从而得到弹托迎风窝的优化外形。以中口径尾翼稳定脱壳穿甲弹的弹托设计为例,采用提出的优化设计模型对其迎风窝结构进行优化设计,并采用基于动网格技术的弹托分离仿真模型验证其最优性。仿真结果表明：所提优化模型能够得到最优的弹托迎风窝结构;针对现有的中口径尾翼稳定脱壳穿甲弹,可进一步对其弹托结构进行优化,以提高其分离快速性。