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     

Bayesian inference based on partial monitoring of components with applications to preventive system maintenance

Consider a binary, monotone system of n components. The assessment of the parameter vector, θ, of the joint distribution of the lifetimes of the components and hence of the reliability of the system is often difficult due to scarcity of data. It is therefore important to make use of all information in an efficient way. For instance, prior knowledge is often of importance and can indeed conveniently be incorporated by the Bayesian approach. It may also be important to continuously extract information from a system currently in operation. This may be useful both for decisions concerning the system in operation as well as for decisions improving the components or changing the design of similar new systems. As in Meilijson [12], life‐monitoring of some components and conditional life‐monitoring of some others is considered. In addition to data arising from this monitoring scheme, so‐called autopsy data are observed, if not censored. The probabilistic structure underlying this kind of data is described, and basic likelihood formulae are arrived at. A thorough discussion of an important aspect of this probabilistic structure, the inspection strategy, is given. Based on a version of this strategy a procedure for preventive system maintenance is developed and a detailed application to a network system presented. All the way a Bayesian approach to estimation of θ is applied. For the special case where components are conditionally independent given θ with exponentially distributed lifetimes it is shown that the weighted sum of products of generalized gamma distributions, as introduced in Gåsemyr and Natvig [7], is the conjugate prior for θ. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 551–577, 2001.     

A risk function for the stochastic modeling of electric capacity expansion

We present a stochastic optimization model for planning capacity expansion under capacity deterioration and demand uncertainty. The paper focuses on the electric sector, although the methodology can be used in other applications. The goals of the model are deciding which energy types must be installed, and when. Another goal is providing an initial generation plan for short periods of the planning horizon that might be adequately modified in real time assuming penalties in the operation cost. Uncertainty is modeled under the assumption that the demand is a random vector. The cost of the risk associated with decisions that may need some tuning in the future is included in the objective function. The proposed scheme to solve the nonlinear stochastic optimization model is Generalized Benders' decomposition. We also exploit the Benders' subproblem structure to solve it efficiently. Computational results for moderate‐size problems are presented along with comparison to a general‐purpose nonlinear optimization package. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48:662–683, 2001     

充分发展湍流管道内壁边界的红外定量识别

基于导热的管道内壁边界识别已发展成熟,但更贴合实际的湍流管道内壁边界的定量识别尚未见报道。通过关联COMSOL和MATLAB,利用有限元方法和Levenberg-Marquardt算法对二维轴对称充分发展的湍流管道内壁边界形状的稳态识别进行研究。数值实验证明了本方法的有效性。结果表明,在含内壁缺陷的湍流管道中,外壁最大温差和由缺陷引起的绝对温差并不是同步增加的;在进行内壁边界反问题识别时,由于绝对温差中负增长的出现,绝对温差越大,识别结果未必越好;识别精度在不规则内壁终点处略微变差。     

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.     

Optimizing natural gas pipeline transmission with nonuniform elevation: A new initialization approach

In this paper, we develop an iterative piecewise linear approximation approach with a novel initialization method to solve natural gas pipeline transmission problems with the nonuniform network elevation. Previous approaches, such as energy minimization methods, cannot be applied to solve problems with the nonuniform network elevation because they exclude pressure range constraints, and thus provide solutions far from optimum. We propose a new initialization model that considers pressure range constraints and improves the optimality of the solutions and the computational efficiency. Furthermore, we extend the energy minimization methods and provide the necessary conditions under which the extended methods operate in networks with the nonuniform elevation. We test the performances of the methods with previously reported pipeline networks from the literature, with the open data set GasLib, and with our industrial collaborator. The initialization approach is shown to be more efficient than the method with fixed initial breakpoints. The newly proposed initialization approach generates solutions with a higher accuracy than the extended energy minimization methods, especially in large‐size networks. The proposed method has been applied to natural gas transmission planning by the China National Petroleum Corporation and has brought a direct profit increase of 330 million U.S. dollars in 2015‐2017.     

求解不确定型车辆路径问题的弱鲁棒优化方法

为降低鲁棒优化模型最优解的保守性,以最小化违约车辆数和总惩罚成本为目标,建立针对旅行时间不确定的开放式车辆路径问题的弱鲁棒优化模型。对于不确定数据集的每个取值,该模型的最优解可以使其目标函数值始终不超过某数值,进而改善最优解的保守性。为提高启发式算法发现最优解的概率,提出一种自设计遗传算法对模型进行求解,其主要思想是利用粒子群算法搜索出可使遗传算法预期产生最好解的算法要素,并将其进行组合,从而产生新的遗传算法。采用新产生的遗传算法对模型继续求解,输出最好解。计算结果表明:与以往的鲁棒优化方法相比,弱鲁棒优化方法的最优解的保守性显著降低。     

Solving generalized transportation problems via pure transportation problems

This paper investigates certain issues of coefficient sensitivity in generalized network problems when such problems have small gains or losses. In these instances, it might be computationally advantageous to temporarily ignore these gains or losses and solve the resultant “pure” network problem. Subsequently, the optimal solution to the pure problem could be used to derive the optimal solution to the original generalized network problem. In this paper we focus on generalized transportation problems and consider the following question: Given an optimal solution to the pure transportation problem, under what conditions will the optimal solution to the original generalized transportation problem have the same basic variables? We study special cases of the generalized transportation problem in terms of convexity with respect to a basis. For the special case when all gains or losses are identical, we show that convexity holds. We use this result to determine conditions on the magnitude of the gains or losses such that the optimal solutions to both the generalized transportation problem and the associated pure transportation problem have the same basic variables. For more general cases, we establish sufficient conditions for convexity and feasibility. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 666–685, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10034     

对办好高等院校研究生课程进修教育的思考

近年来,高校纷纷举办各种形式多样的在职研究生课程进修班,针对这一新生的、过热的教育形式,本文从其定位和目前存在问题等方面进行系统分析,并提出了进一步办好研究生课程进修班的措施.     

析通信线路消防安全管理方面存在的问题

针对我国通信行业与公安消防部门就通信线路和建构筑物之间安全距离规定不统一 ,分析我国通信线路消防安全管理方面存在的问题 ,并提出改进通信线路消防安全管理的建议