A parallel machine replacement model

This paper considers a finite horizon parallel machine replacement problem where a fixed number of machines is in operation at all times. The operating cost for a machine goes up as the machine gets older. An older machine may have to be replaced by a new one when its operating cost becomes too high. There is a fixed order cost associated with the purchase of new machines. Machine purchase prices and salvage values may depend on the period in which they were purchased. The objective is to find a replacement plan that minimizes the total discounted cost over the problem horizon. We believe that the costs in our model are more commonly observed in practice than those previously used in the literature. The paper develops properties of optimal solutions and an efficient forward‐time algorithm to find an optimal replacement plan. A dominance property is developed that further limits the options to be considered, and a simple forecast horizon result is also presented. Future research possibilities are mentioned. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 275–287, 2002; Published online in Wiley InterScience (http://www.interscience.wiley.com). DOI 10.1002/nav.10012     

A model of supply-chain decisions for resource sharing with an application to ventilator allocation to combat COVID-19

We present a stochastic optimization model for allocating and sharing a critical resource in the case of a pandemic. The demand for different entities peaks at different times, and an initial inventory for a central agency are to be allocated. The entities (states) may share the critical resource with a different state under a risk-averse condition. The model is applied to study the allocation of ventilator inventory in the COVID-19 pandemic by FEMA to different U.S. states. Findings suggest that if less than 60% of the ventilator inventory is available for non-COVID-19 patients, FEMA's stockpile of 20 000 ventilators (as of March 23, 2020) would be nearly adequate to meet the projected needs in slightly above average demand scenarios. However, when more than 75% of the available ventilator inventory must be reserved for non-COVID-19 patients, various degrees of shortfall are expected. In a severe case, where the demand is concentrated in the top-most quartile of the forecast confidence interval and states are not willing to share their stockpile of ventilators, the total shortfall over the planning horizon (until May 31, 2020) is about 232 000 ventilator days, with a peak shortfall of 17 200 ventilators on April 19, 2020. Results are also reported for a worst-case where the demand is at the upper limit of the 95% confidence interval. An important finding of this study is that a central agency (FEMA) can act as a coordinator for sharing critical resources that are in short supply over time to add efficiency in the system. Moreover, through properly managing risk-aversion of different entities (states) additional efficiency can be gained. An additional implication is that ramping up production early in the planning cycle allows to reduce shortfall significantly. An optimal timing of this production ramp-up consideration can be based on a cost-benefit analysis.     

具有吞吐量和时延约束的软件无线电波形部署决策算法

针对当前具有吞吐量和时延约束的软件无线电波形部署决策算法在内存开销方面考虑的不足,提出一个更为通用的波形部署决策系统模型,将波形的处理开销、内存开销和通信带宽开销都纳入到波形部署决策过程中,并设计了一种基于动态规划的波形部署决策算法以最小化波形对平台各种计算资源的占用总和。仿真结果表明,内存对波形部署决策具有重要影响,与未考虑内存开销的解决方案相比,平台支持的平均最大波形数目和平均处理资源利用率均下降40%左右。     

A decomposition heuristic for the twin robots scheduling problem

This article provides an efficient heuristic based on decomposition for the twin robots scheduling problem (TRSP). TRSP concerns two moving robots executing storage and retrieval requests in parallel along a shared pathway. The depots are located at both ends of the line and a dedicated robot is assigned to each of them. While moving goods between their respective depots and some storage locations on the line, noncrossing constraints among robots need to be considered. Our heuristic uses a dynamic programming framework to determine the schedule of one robot while keeping the other one's fixed. It finds near‐optimal solutions even for large problem instances with hundreds of jobs in a short time span. © 2014 Wiley Periodicals, Inc. 62:16–22, 2015     

Modeling and solution for the ship stowage planning problem of coils in the steel industry

We consider a ship stowage planning problem where steel coils with known destination ports are to be loaded onto a ship. The coils are to be stowed on the ship in rows. Due to their heavy weight and cylindrical shape, coils can be stowed in at most two levels. Different from stowage problems in previous studies, in this problem there are no fixed positions on the ship for the coils due to their different sizes. At a destination port, if a coil to be unloaded is not at a top position, those blocking it need to be shuffled. In addition, the stability of ship has to be maintained after unloading at each destination port. The objective for the stowage planning problem is to minimize a combination of ship instability throughout the entire voyage, the shuffles needed for unloading at the destination ports, and the dispersion of coils to be unloaded at the same destination port. We formulate the problem as a novel mixed integer linear programming model. Several valid inequalities are derived to help reducing solution time. A tabu search (TS) algorithm is developed for the problem with the initial solution generated using a construction heuristic. To evaluate the proposed TS algorithm, numerical experiments are carried out on problem instances of three different scales by comparing it with a model‐based decomposition heuristic, the classic TS algorithm, the particle swarm optimization algorithm, and the manual method used in practice. The results show that for small problems, the proposed algorithm can generate optimal solutions. For medium and large practical problems, the proposed algorithm outperforms other methods. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 564–581, 2015     

随机布阵条件下同时数字多波束干扰优化设计方法

针对现有方法普遍存在的波束形成算法效率低、难以形成多频点多方向的同时多波束干扰、不适用于随机布阵条件下的波束形成等缺点,提出了一种基于二阶锥规划(SOCP,Second-Order Cone Programming)理论的同时数字多波束干扰形成方法。首先,给出了在随机布阵条件下干扰多波束优化设计问题的数学描述;其次,以范数准则为例,将随机布阵条件下干扰多波束设计问题的解析形式转化为相应的SOCP形式;再次,利用现有的原-对偶内点算法工具箱Se Du Mi或者CVX进行快速求解。最后,仿真结果表明该方法可以较好地解决随机布阵条件下的多频率多方向雷达目标同时多波束干扰优化设计问题。     

基于Virtools的洞库工程维护管理虚拟训练系统

为了解决洞库工程教学训练缺乏直观性和实践性的难题,利用Revit,Sketch Up和3D Max软件进行三维模型构建,以漫游中的基本图形变换和位置实时显示技术为例介绍了相关数学原理及Virtools编程实现过程,实现预定功能后发布了洞库工程维护管理虚拟训练系统。该虚拟训练系统具有功能演示、虚拟漫游、虚拟施工、维护管理虚拟训练和考核评估等功能,可以让学员身临其境地学习洞库工程维护管理的相关知识,有效地提高了教学效果。     

Balancing stability and efficiency in team formation as a generalized roommate problem

The assignment of personnel to teams is a fundamental managerial function typically involving several objectives and a variety of idiosyncratic practical constraints. Despite the prevalence of this task in practice, the process is seldom approached as an optimization problem over the reported preferences of all agents. This is due in part to the underlying computational complexity that occurs when intra-team interpersonal interactions are taken into consideration, and also due to game-theoretic considerations, when those taking part in the process are self-interested agents. Variants of this fundamental decision problem arise in a number of settings, including, for example, human resources and project management, military platooning, ride sharing, data clustering, and in assigning students to group projects. In this article, we study an analytical approach to “team formation” focused on the interplay between two of the most common objectives considered in the related literature: economic efficiency (i.e., the maximization of social welfare) and game-theoretic stability (e.g., finding a core solution when one exists). With a weighted objective across these two goals, the problem is modeled as a bi-level binary optimization problem, and transformed into a single-level, exponentially sized binary integer program. We then devise a branch-cut-and-price algorithm and demonstrate its efficacy through an extensive set of simulations, with favorable comparisons to other algorithms from the literature.     

搜索路径给定时的搜索对策问题及其应用

搜索路径给定时的最优搜索方案问题,也可以理解为是关于搜索者和目标的二人对策问题,主要讨论了当搜索路径给定时的单个搜索者和单个目标的搜索对策问题。首先根据问题的特点,利用动态规划和迭代的方法,确定关于目标逃逸路径混合策略的最优分区,证明该分区是多面体凸集;针对目标不同逃逸路径的分区,求出搜索者的最大期望收益,再将问题转化为二人有限零和对策,计算出搜索者的支付矩阵,确定最优搜索策略。最后结合海军护航行动,对我舰载直升机搜索小型海盗船进行分析和计算,说明搜索路径给定时的最优搜索对策对于双方的资源分配和提高搜索效率具有一定的应用价值。     

Single‐commodity stochastic network design under demand and topological uncertainties with insufficient data

Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single‐commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst‐case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst‐case cost using budgeted uncertainty sets. We develop cutting‐plane algorithms for solving the mixed‐integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real‐world networks. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 154–173, 2017