多目标的分布式协同进化MDO算法

通过引入非优超排序和排挤的多目标处理机制 ,将分布式协同进化MDO算法的能力扩展到多目标的多学科设计优化问题。多目标的分布式协同进化MDO算法在保持各学科充分自治和各学科并行设计优化协同的基础上 ,通过一次运行即可获得具有良好分布的多个Pareto最优解 ,逼近整个Pareto最优前沿。应用于导弹气动 /发动机 /控制三学科两目标设计优化问题 ,与约束法计算结果的对比表明算法能够有效逼近该问题的Pareto最优前沿 ,为设计决策提供了丰富的信息     

滑翔飞行器多目标弹道优化的进化-配点混合求解策略

针对高超声速滑翔飞行器弹道多目标优化问题,综合考虑计算效率和精度,结合分解进化算法与配点法提出一种混合求解策略。根据滑翔飞行器动力学模型和弹道设计中需要考虑的约束条件,建立飞行器多目标弹道优化模型。利用控制量离散化方法将多目标弹道优化问题转化为带约束的多目标参数优化问题,并采用罚函数法处理约束条件,随后利用分解多目标进化算法进行求解。为了提高弹道优化的精度,将椭球聚合法与配点法相结合,以多目标进化算法得到的Pareto解作为初始解进行迭代求解。通过典型的复杂约束多目标弹道优化的算例表明,所提出的混合求解策略能够获得满足复杂约束要求的Pareto最优解集,实现有效的多目标弹道优化。     

Shortest path interdiction problem with arc improvement recourse: A multiobjective approach

We consider the shortest path interdiction problem involving two agents, a leader and a follower, playing a Stackelberg game. The leader seeks to maximize the follower's minimum costs by interdicting certain arcs, thus increasing the travel time of those arcs. The follower may improve the network after the interdiction by lowering the costs of some arcs, subject to a cardinality budget restriction on arc improvements. The leader and the follower are both aware of all problem data, with the exception that the leader is unaware of the follower's improvement budget. The effectiveness of an interdiction action is given by the length of a shortest path after arc costs are adjusted by both the interdiction and improvement. We propose a multiobjective optimization model for this problem, with each objective corresponding to a different possible improvement budget value. We provide mathematical optimization techniques to generate a complete set of strategies that are Pareto‐optimal. Additionally, for the special case of series‐parallel graphs, we provide a dynamic‐programming algorithm for generating all Pareto‐optimal solutions.     

Economic ordering decisions with market choice flexibility

Standard approaches to classical inventory control problems treat satisfying a predefined demand level as a constraint. In many practical contexts, however, total demand is comprised of separate demands from different markets or customers. It is not always clear that constraining a producer to satisfy all markets is an optimal approach. Since the inventory‐related cost of an item depends on total demand volume, no clear method exists for determining a market's profitability a priori, based simply on per unit revenue and cost. Moreover, capacity constraints often limit a producer's ability to meet all demands. This paper presents models to address economic ordering decisions when a producer can choose whether to satisfy multiple markets. These models result in a set of nonlinear binary integer programming problems that, in the uncapacitated case, lend themselves to efficient solution due to their special structure. The capacitated versions can be cast as nonlinear knapsack problems, for which we propose a heuristic solution approach that is asymptotically optimal in the number of markets. The models generalize the classical EOQ and EPQ problems and lead to interesting optimization problems with intuitively appealing solution properties and interesting implications for inventory and pricing management. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

面向武器装备体系组合规划的集成决策优化框架

针对当前武器装备体系组合规划存在选择空间规模大、决策目标数量多等问题,提出一种集成决策优化框架,用于组合选择和规划武器装备的发展型号、时间和数量。首先对武器装备体系组合规划问题的NP-Hard和高维多目标性质进行定量化分析和公式化描述;然后采用目标规划方法将该问题构建为双目标优化模型;再基于NSGA-II多目标演化计算方法,开发面向本问题的优化算法,求得该模型的Pareto解集合;最后通过TOPSIS方法,从Pareto解集合中求取符合决策者偏好的满意解。通过某侦察预警监视体系发展规划示例,验证了当给定经验数据和决策者偏好信息后,该框架可获得符合要求的武器装备体系组合规划方案,能够支撑武器装备体系发展论证和规划。     

Inducing coordination in supply chains through linear reward schemes

Decentralized decision‐making in supply chain management is quite common, and often inevitable, due to the magnitude of the chain, its geographical dispersion, and the number of agents that play a role in it. But, decentralized decision‐making is known to result in inefficient Nash equilibrium outcomes, and optimal outcomes that maximize the sum of the utilities of all agents need not be Nash equilibria. In this paper we demonstrate through several examples of supply chain models how linear reward/penalty schemes can be implemented so that a given optimal solution becomes a Nash equilibrium. The examples represent both vertical and horizontal coordination issues. The techniques we employ build on a general framework for the use of linear reward/penalty schemes to induce stability in given optimal solutions and should be useful to other multi‐agent operations management settings. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

基于NSGA-II和多属性决策的防空火力分配

为了解决防空火力分配问题,首先运用NSGA-II算法求出Pareto最优解集,然后运用多属性决策方法对Pareto最优解集中的解进行综合评估,并从中找出一个最优解。用区间数定性描述各属性,建立了防空火力分配的三目标优化模型。描述了NSGA-II算法和多属性决策方法的运算步骤。在仿真算例中,得到了一个最佳防空火力分配方案,说明该方法对于防空火力分配问题有良好的应用价值。     

Supplier‐buyer contracting: Asymmetric cost information and cutoff level policy for buyer participation

We consider the problem of designing a contract to maximize the supplier's profit in a one‐supplier–one‐buyer relationship for a short‐life‐cycle product. Demand for the finished product is stochastic and price‐sensitive, and only its probability distribution is known when the supply contract is written. When the supplier has complete information on the marginal cost of the buyer, we show that several simple contracts can induce the buyer to choose order quantity that attains the single firm profit maximizing solution, resulting in the maximum possible profit for the supplier. When the marginal cost of the buyer is private information, we show that it is no longer possible to achieve the single firm solution. In this case, the optimal order quantity is always smaller while the optimal sale price of the finished product is higher than the single firm solution. The supplier's profit is lowered while that of the buyer is improved. Moreover, a buyer who has a lower marginal cost will extract more profit from the supplier. Under the optimal contract, the supplier employs a cutoff level policy on the buyer's marginal cost to determine whether the buyer should be induced to sign the contract. We characterize the optimal cutoff level and show how it depends on the parameters of the problem. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 41–64, 2001     

Optimality conditions for the bilevel programming problem

The bilevel programming problem (BLPP) is a sequence of two optimization problems where the constraint region of the first is determined implicitly by the solution to the second. In this article it is first shown that the linear BLPP is equivalent to maximizing a linear function over a feasible region comprised of connected faces and edges of the original polyhedral constraint set. The solution is shown to occur at a vertex of that set. Next, under assumptions of differentiability, first-order necessary optimality conditions are developed for the more general BLPP, and a potentially equivalent mathematical program is formulated. Finally, the relationship between the solution to this problem and Pareto optimality is discussed and a number of examples given.     

A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times

We investigate a single‐machine scheduling problem for which both the job processing times and due windows are decision variables to be determined by the decision maker. The job processing times are controllable as a linear or convex function of the amount of a common continuously divisible resource allocated to the jobs, where the resource allocated to the jobs can be used in discrete or continuous quantities. We use the common flow allowances due window assignment method to assign due windows to the jobs. We consider two performance criteria: (i) the total weighted number of early and tardy jobs plus the weighted due window assignment cost, and (ii) the resource consumption cost. For each resource consumption function, the objective is to minimize the first criterion, while keeping the value of the second criterion no greater than a given limit. We analyze the computational complexity, devise pseudo‐polynomial dynamic programming solution algorithms, and provide fully polynomial‐time approximation schemes and an enhanced volume algorithm to find high‐quality solutions quickly for the considered problems. We conduct extensive numerical studies to assess the performance of the algorithms. The computational results show that the proposed algorithms are very efficient in finding optimal or near‐optimal solutions. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 41–63, 2017     

多目标决策的特殊坐标系求解方法

在多目标决策问题中,满意解常常要在非劣解中寻找。一般来讲,对于两个目标(二维)的解的判别并不困难,但遇到多个目标(n维),且有多个可行解时,对非劣解的判别就显得有些繁复了。因此,采用直观容易的特殊坐标系来判别"非劣解",从而给出求解多目标决策问题满意解的方法。     

Bi‐objective missile rescheduling for a naval task group with dynamic disruptions

This paper considers the rescheduling of surface‐to‐air missiles (SAMs) for a naval task group (TG), where a set of SAMs have already been scheduled to intercept a set of anti‐ship missiles (ASMs). In missile defense, the initial engagement schedule is developed according to the initial state of the defensive and attacking units. However, unforeseen events may arise during the engagement, creating a dynamic environment to be handled, and making the initial schedule infeasible or inefficient. In this study, the initial engagement schedule of a TG is assumed to be disrupted by the occurrence of a destroyed ASM, the breakdown of a SAM system, or an incoming new target ASM. To produce an updated schedule, a new biobjective mathematical model is formulated that maximizes the no‐leaker probability value for the TG and minimizes the total deviation from the initial schedule. With the problem shown to be NP‐hard, some special cases are presented that can be solved in polynomial time. We solve small size problems by the augmented ? ‐ constraint method and propose heuristic procedures to generate a set of nondominated solutions for larger problems. The results are presented for different size problems and the total effectiveness of the model is evaluated.     

炮兵指挥决策中优选作战方案的神经网络模型

优选作战方案是炮兵指挥决策的重要内容.如何从炮兵众多的作战方案中确定其价值,并根据作战任务需要选出最佳方案,是炮兵指挥员及其参谋人员的-项重要任务.根据神经网络中联想记忆的-般模型和迭代解法对炮兵作战方案进行分析和排序,并可运用计算机进行处理,为炮兵指挥员的决策行为提供依据.     

Strategic capacity decision‐making in a stochastic manufacturing environment using real‐time approximate dynamic programming

In this study, we illustrate a real‐time approximate dynamic programming (RTADP) method for solving multistage capacity decision problems in a stochastic manufacturing environment, by using an exemplary three‐stage manufacturing system with recycle. The system is a moderate size queuing network, which experiences stochastic variations in demand and product yield. The dynamic capacity decision problem is formulated as a Markov decision process (MDP). The proposed RTADP method starts with a set of heuristics and learns a superior quality solution by interacting with the stochastic system via simulation. The curse‐of‐dimensionality associated with DP methods is alleviated by the adoption of several notions including “evolving set of relevant states,” for which the value function table is built and updated, “adaptive action set” for keeping track of attractive action candidates, and “nonparametric k nearest neighbor averager” for value function approximation. The performance of the learned solution is evaluated against (1) an “ideal” solution derived using a mixed integer programming (MIP) formulation, which assumes full knowledge of future realized values of the stochastic variables (2) a myopic heuristic solution, and (3) a sample path based rolling horizon MIP solution. The policy learned through the RTADP method turned out to be superior to polices of 2 and 3. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

Optimal switchover times between two activities utilizing the same resource

The “gold‐mining” decision problem is concerned with the efficient utilization of a delicate mining equipment working in a number of different mines. Richard Bellman was the first to consider this type of a problem. The solution found by Bellman for the finite‐horizon, continuous‐time version of the problem with two mines is not overly realistic since he assumed that fractional parts of the same mining equipment could be used in different mines and this fraction could change instantaneously. In this paper, we provide some extensions to this model in order to produce more operational and realistic solutions. Our first model is concerned with developing an operational policy where the equipment may be switched from one mine to the other at most once during a finite horizon. In the next extension we incorporate a cost component in the objective function and assume that the horizon length is not fixed but it is the second decision variable. Structural properties of the optimal solutions are obtained using nonlinear programming. Each model and its solution is illustrated with a numerical example. The models developed here may have potential applications in other areas including production of items requiring the same machine or choosing a sequence of activities requiring the same resource. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 186–203, 2002; DOI 10.1002/nav.10008     

A generalization of the weighted set covering problem

We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect b‐matching problem. In general, we may use a polynomial‐time greedy heuristic similar to the one for the classical weighted set covering problem studied by D.S. Johnson [Approximation algorithms for combinatorial problems, J Comput Syst Sci 9 (1974), 256–278], L. Lovasz [On the ratio of optimal integral and fractional covers, Discrete Math 13 (1975), 383–390], and V. Chvatal [A greedy heuristic for the set‐covering problem, Math Oper Res 4(3) (1979), 233–235] to get an approximate solution for the problem. We find a worst‐case bound for the heuristic similar to that for the classical problem. In addition, we introduce a general type of probability distribution for the population of the problem instances and prove that the greedy heuristic is asymptotically optimal for instances drawn from such a distribution. We also conduct computational studies to compare solutions resulting from running the heuristic and from running the commercial integer programming solver CPLEX on problem instances drawn from a more specific type of distribution. The results clearly exemplify benefits of using the greedy heuristic when problem instances are large. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Optimal maintenance policies for serial,multi‐machine systems with non‐instantaneous repairs

We study optimal age‐replacement policies for machines in series with non‐instantaneous repair times by formulating two nonlinear programs: one that minimizes total cost‐rate subject to a steady‐state throughput requirement and another that maximizes steady‐state throughput subject to a cost‐rate budget constraint. Under reasonable assumptions, the single‐machine cost‐optimal and throughput‐optimal solutions are unique and orderable, and the multi‐machine optimal solutions have appealing structure. Furthermore, we establish equivalence between the two formulations and provide an illustrative numerical example. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Heuristics for the multi‐resource generalized assignment problem

The well‐known generalized assignment problem (GAP) involves the identification of a minimum‐cost assignment of tasks to agents when each agent is constrained by a resource in limited supply. The multi‐resource generalized assignment problem (MRGAP) is the generalization of the GAP in which there are a number of different potentially constraining resources associated with each agent. This paper explores heuristic procedures for the MRGAP. We first define a three‐phase heuristic which seeks to construct a feasible solution to MRGAP and then systematically attempts to improve the solution. We then propose a modification of the heuristic for the MRGAP defined previously by Gavish and Pirkul. The third procedure is a hybrid heuristic that combines the first two heuristics, thus capturing their relative strengths. We discuss extensive computational experience with the heuristics. The hybrid procedure is seen to be extremely effective in solving MRGAPs, generating feasible solutions to more than 99% of the test problems and consistently producing near‐optimal solutions. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 468–483, 2001     

An application of yield management for Internet Service Providers

In this paper we study strategies for better utilizing the network capacity of Internet Service Providers (ISPs) when they are faced with stochastic and dynamic arrivals and departures of customers attempting to log‐on or log‐off, respectively. We propose a method in which, depending on the number of modems available, and the arrival and departure rates of different classes of customers, a decision is made whether to accept or reject a log‐on request. The problem is formulated as a continuous time Markov Decision Process for which optimal policies can be readily derived using techniques such as value iteration. This decision maximizes the discounted value to ISPs while improving service levels for higher class customers. The methodology is similar to yield management techniques successfully used in airlines, hotels, etc. However, there are sufficient differences, such as no predefined time horizon or reservations, that make this model interesting to pursue and challenging. This work was completed in collaboration with one of the largest ISPs in Connecticut. The problem is topical, and approaches such as those proposed here are sought by users. © 2001 John Wiley & Sons, Inc., Naval Research Logistics 48:348–362, 2001     

Evasion policies for a vessel being chased by pirate skiffs

Piracy attack is a serious safety problem for maritime transport worldwide. Whilst various strategic actions can be taken, such as rerouting vessels and strengthening navy patrols, this still cannot completely eliminate the possibility of a piracy attack. It is therefore important for a commercial vessel to be equipped with operational solutions in case of piracy attacks. In particular, the choice of a direction for rapidly fleeing is a critical decision for the vessel. In this article, we formulate such a problem as a nonlinear optimal control problem. We consider various policies, such as maintaining a straight direction or making turns, develop algorithms to optimize the policies, and derive conditions under which these policies are effective and safe. Our work can be used as a real‐time decision making tool that enables a vessel master to evaluate different scenarios and quickly make decisions.