The parallel replacement problem with demand and capital budgeting constraints

A generalized parallel replacement problem is considered with both fixed and variable replacement costs, capital budgeting, and demand constraints. The demand constraints specify that a number of assets, which may vary over time, are required each period over a finite horizon. A deterministic, integer programming formulation is presented as replacement decisions must be integer. However, the linear programming relaxation is shown to have integer extreme points if the economies of scale binary variables are fixed. This allows for the efficient computation of large parallel replacement problems as only a limited number of 0–1 variables are required. Examples are presented to provide insight into replacement rules, such as the “no‐splitting‐rule” from previous research, under various demand scenarios. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 40–56, 2000     

Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures

In this paper, we study the problem of scheduling quay cranes (QCs) at container terminals where incoming vessels have different ready times. The objective is to minimize the maximum relative tardiness of vessel departures. The problem can be formulated as a mixed integer linear programming (MILP) model of large size that is difficult to solve directly. We propose a heuristic decomposition approach to breakdown the problem into two smaller, linked models, the vessel‐level and the berth‐level models. With the same berth‐level model, two heuristic methods are developed using different vessel‐level models. Computational experiments show that the proposed approach is effective and efficient. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

An efficient heuristic procedure for the uncapacitated warehouse location problem

This paper introduces an efficient heuristic procedure for a special class of mixed integer programming problems called the uncapacitated warehouse (plant) location problem. This procedure is derived from the branching decision rules proposed for the branch and bound algorithm by the author in an earlier paper. It can be viewed as tracing a single path of the branch and bound tree (from the initial node to the terminal node), the path being determined by the particular branching decision rule used. Unlike branch and bound the computational efficiency of this procedure is substantially less than linearly related to the number of potential warehouse locations (integer variables) in the problem. Its computational efficiency is tested on problems found in the literature.     

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     

On the first come–first served rule in multi‐echelon inventory control

A two‐echelon distribution inventory system with a central warehouse and a number of retailers is considered. The retailers face stochastic demand and replenish from the warehouse, which, in turn, replenishes from an outside supplier. The system is reviewed continuously and demands that cannot be met directly are backordered. Standard holding and backorder costs are considered. In the literature on multi‐echelon inventory control it is standard to assume that backorders at the warehouse are served according to a first come–first served policy (FCFS). This allocation rule simplifies the analysis but is normally not optimal. It is shown that the FCFS rule can, in the worst case, lead to an asymptotically unbounded relative cost increase as the number of retailers approaches infinity. We also provide a new heuristic that will always give a reduction of the expected costs. A numerical study indicates that the average cost reduction when using the heuristic is about two percent. The suggested heuristic is also compared with two existing heuristics. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

航天测控调度问题的拉格朗日启发式算法

通过分析航天测控调度问题的测控需求,建立了航天测控调度0-1整数规划模型,运用拉格朗日松弛方法对模型中的任务约束和设备约束进行了松弛,运用次梯度优化算法求得了航天测控调度问题上界,同时得到了决策变量对应的拉格朗日权重,可以作为决策变量在最优解中是否被调度的启发式信息,对拉格朗日权重进行分析,提出了求解问题可行解的拉格朗日启发式算法。最后,通过对两个场景的试验分析验证了拉格朗日启发式算法所求可行解的优越性。     

A linear programming solution to the generalized rectangular distance weber problem

The Weber Problem generalized to the location of several new points with respect to existing points is formulated as a linear programming problem under the assumption that distances are rectangular. The dual problem is then formulated and subsequently reduced to a problem with substantially fewer variables and constraints than required by an existent alternative linear programming formulation. Flows may exist between new as well as between new and existing points. Linear constraints can be imposed to restrict the location of new points. Pairwise constraints limiting distances between new points and between new and existing points can also be accommodated.     

Mathematical formulation and heuristic algorithm for the block relocation and loading problem

This study considers the block relocation and loading problem in container terminals. The optimal loading sequence and relocation location are simultaneously decided on the basis of the desired ship‐bay and initial yard space configuration. An integer linear programming model is developed to minimize the number of relocations in the yard space on the basis of no shifts in the ship bay. The accuracy of the model is tested on small‐scale scenarios by using CPLEX. Considering the problem size in the real world, we present a rule‐based heuristic method that is combined with a mathematical model for the removal, loading, and relocation operations. The influence of rules on algorithm performance is also analyzed, and the heuristic algorithm is compared with different types of algorithms in the literature. The extensive numerical experiments show the efficiency of the proposed heuristic algorithm.     

多传感器任务分派的快速启发式规划新算法

在多目标多传感器管理中经常采用的线性规划算法中,随着传感器个数和目标个数的增加,计算量会爆炸式增长,使得跟踪系统不能实时计算,为此,根据传感器管理中线性规划的特点,提出了一种快速启发式算法,考虑组合中的传感器个数将组合的分配效用转化为权重,递推分配权重最大的组合,逐步减小组合和目标的个数.证明了权重最大的组合分派能实现组合中的传感器的最大效用.仿真结果表明该算法在与采用线性规划方法的跟踪精度相当的情况下,能有效地减小计算量.     

Generation and storage dispatch in electricity networks with generator disruptions

We present methods for optimizing generation and storage decisions in an electricity network with multiple unreliable generators, each colocated with one energy storage unit (e.g., battery), and multiple loads under power flow constraints. Our model chooses the amount of energy produced by each generator and the amount of energy stored in each battery in every time period in order to minimize power generation and storage costs when each generator faces stochastic Markovian supply disruptions. This problem cannot be optimized easily using stochastic programming and/or dynamic programming approaches. Therefore, in this study, we present several heuristic methods to find an approximate optimal solution for this system. Each heuristic involves decomposing the network into several single‐generator, single‐battery, multiload systems and solving them optimally using dynamic programming, then obtaining a solution for the original problem by recombining. We discuss the computational performance of the proposed heuristics as well as insights gained from the models. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 493–511, 2015     

Production lot sizing under setup and worker learning

Previous lot-sizing models incorporating learning effects focus exclusively on worker learning. We extend these models to include the presence of setup learning, which occurs when setup costs exhibit a learning curve effect as a function of the number of lots produced. The joint worker/setup learning problem can be solved to optimality by dynamic programming. Computational experience indicates, however, that solution times are sensitive to certain problem parameters, such as the planning horizon and/or the presence of a lower bound on worker learning. We define a two-phase EOQ-based heuristic for the problem when total transmission of worker learning occurs. Numerical results show that the heuristic consistently generates solutions well within 1% of optimality.     

Interdiction models for delaying adversarial attacks against critical information technology infrastructure

Information technology (IT) infrastructure relies on a globalized supply chain that is vulnerable to numerous risks from adversarial attacks. It is important to protect IT infrastructure from these dynamic, persistent risks by delaying adversarial exploits. In this paper, we propose max‐min interdiction models for critical infrastructure protection that prioritizes cost‐effective security mitigations to maximally delay adversarial attacks. We consider attacks originating from multiple adversaries, each of which aims to find a “critical path” through the attack surface to complete the corresponding attack as soon as possible. Decision‐makers can deploy mitigations to delay attack exploits, however, mitigation effectiveness is sometimes uncertain. We propose a stochastic model variant to address this uncertainty by incorporating random delay times. The proposed models can be reformulated as a nested max‐max problem using dualization. We propose a Lagrangian heuristic approach that decomposes the max‐max problem into a number of smaller subproblems, and updates upper and lower bounds to the original problem via subgradient optimization. We evaluate the perfect information solution value as an alternative method for updating the upper bound. Computational results demonstrate that the Lagrangian heuristic identifies near‐optimal solutions efficiently, which outperforms a general purpose mixed‐integer programming solver on medium and large instances.     

舰船成本预测系统中的自变量约简方法

针对舰船成本预测系统中自变量众多且相互关系错综复杂的特点,提出了用模糊粗糙集方法对舰船成本预测系统中的自变量进行约简。在模糊粗糙集方法的框架下,给出了模糊不可分辨关系和相对约简的定义,构建了基于模糊粗糙集的舰船成本预测系统自变量约简模型,并且针对实际的舰船成本预测系统一般是混合数据系统的问题,对广义差别矩阵的定义进行了改进,设计了相应的启发式约简算法。实例分析结果表明:文中所提的方法不仅能使约简的自变量大为减少,而且约简的效果较传统方法更好,且计算过程也更简单。     

Neighborhood search heuristics for selecting hierarchically well‐formulated subsets in polynomial regression

The importance of subset selection in multiple regression has been recognized for more than 40 years and, not surprisingly, a variety of exact and heuristic procedures have been proposed for choosing subsets of variables. In the case of polynomial regression, the subset selection problem is complicated by two issues: (1) the substantial growth in the number of candidate predictors, and (2) the desire to obtain hierarchically well‐formulated subsets that facilitate proper interpretation of the regression parameter estimates. The first of these issues creates the need for heuristic methods that can provide solutions in reasonable computation time; whereas the second requires innovative neighborhood search approaches that accommodate the hierarchical constraints. We developed tabu search and variable neighborhood search heuristics for subset selection in polynomial regression. These heuristics are applied to a classic data set from the literature and, subsequently, evaluated in a simulation study using synthetic data sets. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

The frequency assignment problem: A solution via nonlinear programming

This paper gives a mathematical programming model for the problem of assigning frequencies to nodes in a communications network. The objective is to select a frequency assignment which minimizes both cochannel and adjacent-channel interference. In addition, a design engineer has the option to designate key links in which the avoidance of jamming due to self interference is given a higher priority. The model has a nonconvex quadratic objective function, generalized upper-bounding constraints, and binary decision variables. We developed a special heuristic algorithm and software for this model and tested it on five test problems which were modifications of a real-world problem. Even though most of the test problems had over 600 binary variables, we were able to obtain a near optimum in less than 12 seconds of CPU time on a CDC Cyber-875.     

A simulated annealing approach to the cyclic staff-scheduling problem

This article presents the application of a simulated annealing heuristic to an NP-complete cyclic staff-scheduling problem. The new heuristic is compared to branch-and-bound integer programming algorithms, as well as construction and linear programming-based heuristics. It is designed for use in a continuously operating scheduling environment with the objective of minimizing the number of employees necessary to satisfy forecast demand. The results indicate that the simulated annealing-based method tends to dominate the branch-and-bound algorithms and the other heuristics in terms of solution quality. Moreover, the annealing algorithm exhibited rapid convergence to a low-cost solution. The simulated annealing heuristic is executed in a single program and does not require mathematical programming software. © 1993 John Wiley & Sons, Inc.     

An approximative algorithm for the fixed charge problem

This paper describes an approximate solution method for solving the fixed charge problem. This heuristic approach is applied to a set of test problems to explore the margin of error. The results indicate that the proposed fixed charge simplex algorithm is capable of finding optimal or near optimal solutions to moderate sized fixed charge problems. In the absence of an exact method, this heuristic should prove useful in solving this fundamental nonlinear programming problem.     

Heuristics for minimizing mean tardiness for m parallel machines

The concept of parallel operations has been widely used in manufacturing and data processing. However, not many efficient methods have been proposed to reduce job tardiness. This article proposes an efficient heuristic to minimize the mean tardiness of a set of tasks with known processing times and due dates for single and m parallel machines. For the single-machine case, the proposed heuristic is compared with the well-known Wilkerson and Irwin algorithm; for the m parallel machine case, it is compared with an extension of the Wilkerson-Irwin algorithm. We also introduce a simple dispatching rule, and it is compared with some existing dispatching rules. The comprehensive simulation results show that the proposed heuristic performs better than the Wilkerson-Irwin algorithm at a significantly reduced computational time.     

Dichotomous categorical variable formation in mathematical programming discriminant analysis models

Classification models, whether generated by statistical techniques or mathematical programming (MP) discriminant analysis methods, are often simplified by ad hoc formation of dichotomous categorical variables from the original variables with, for example, a dichotomous variable taking value 1 if the original variable is above a threshold level and 0 otherwise. In this paper an MP discriminant analysis method is developed for forming dichotomous categorical variables in problems with discriminant functions that are monotone in the original variables. For each of the original variables from which dichotomous variables may be formed, a set of possible threshold levels for dichotomous variable formation is defined. An MP model is then used to determine both the threshold level for forming each dichotomous variable and the associated discriminant function coefficient. The proposed MP approach is applied to a published problem and a number of simulated problem sets. It is shown that the discriminant functions in dichotomous categorical variables generated by this new MP approach can in some cases outperform the functions generated by standard MP discriminant analysis models using the original variables. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

A novel modeling approach for express package carrier planning

Express package carrier networks have large numbers of heavily‐interconnected and tightly‐constrained resources, making the planning process difficult. A decision made in one area of the network can impact virtually any other area as well. Mathematical programming therefore seems like a logical approach to solving such problems, taking into account all of these interactions. The tight time windows and nonlinear cost functions of these systems, however, often make traditional approaches such as multicommodity flow formulations intractable. This is due to both the large number of constraints and the weakness of the linear programming (LP) relaxations arising in these formulations. To overcome these obstacles, we propose a model in which variables represent combinations of loads and their corresponding routings, rather than assigning individual loads to individual arcs in the network. In doing so, we incorporate much of the problem complexity implicitly within the variable definition, rather than explicitly within the constraints. This approach enables us to linearize the cost structure, strengthen the LP relaxation of the formulation, and drastically reduce the number of constraints. In addition, it greatly facilitates the inclusion of other stages of the (typically decomposed) planning process. We show how the use of templates, in place of traditional delayed column generation, allows us to identify promising candidate variables, ensuring high‐quality solutions in reasonable run times while also enabling the inclusion of additional operational considerations that would be difficult if not impossible to capture in a traditional approach. Computational results are presented using data from a major international package carrier. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008