A forward network simplex algorithm for solving multiperiod network flow problems

An optimization model which is frequently used to assist decision makers in the areas of resource scheduling, planning, and distribution is the minimum cost multiperiod network flow problem. This model describes network structure decision-making problems over time. Such problems arise in the areas of production/distribution systems, economic planning, communication systems, material handling systems, traffic systems, railway systems, building evacuation systems, energy systems, as well as in many others. Although existing network solution techniques are efficient, there are still limitations to the size of problems that can be solved. To date, only a few researchers have taken the multiperiod structure into consideration in devising efficient solution methods. Standard network codes are usually used because of their availability and perceived efficiency. In this paper we discuss the development, implementation, and computational testing of a new technique, the forward network simplex method, for solving linear, minimum cost, multiperiod network flow problems. The forward network simplex method is a forward algorithm which exploits the natural decomposition of multiperiod network problems by limiting its pivoting activity. A forward algorithm is an approach to solving dynamic problems by solving successively longer finite subproblems, terminating when a stopping rule can be invoked or a decision horizon found. Such procedures are available for a large number of special structure models. Here we describe the specialization of the forward simplex method of Aronson, Morton, and Thompson to solving multiperiod network network flow problems. Computational results indicate that both the solution time and pivot count are linear in the number of periods. For standard network optimization codes, which do not exploit the multiperiod structure, the pivot count is linear in the number of periods; however, the solution time is quadratic.     

Network design for time‐constrained delivery

To meet customer demand, delivery companies are offering an increasing number of time‐definite services. In this article, we examine the strategic design of delivery networks which can efficiently provide these services. Because of the high cost of direct connections, we focus on tree‐structured networks. As it may not be possible to identify a tree‐structured network that satisfies all of the delivery guarantees, we allow these guarantees to be violated but seek to minimize the sum of the violations. We establish the complexity of the problem and exploit an empirically identified solution structure to create new neighborhoods which improve solution values over more general neighborhood structures. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

An (s,q) inventory model with stochastic and interrelated lead times

In this article we introduce a lead time mechanism that allows simultaneous order arrivals. This mechanism ensures that orders never cross each other. For the continuous review (s, q) inventory system with constant demand, we show that the allowance of batch arrivals gives rise to a discontinuous cost function. By exploiting the special structure of this cost function, a search algorithm is derived that yields the optimal order strategy in a reasonable amount of time. The search is restricted to integer order strategies only. We also consider an approximate method of solution that is based on a related model with a continuous cost function. The results obtained by this approximation are, in general, very satisfactory. © 1995 John Wiley & Sons, Inc.     

A concave‐cost production planning problem with remanufacturing options

We focus on the concave‐cost version of a production planning problem where a manufacturer can meet demand by either producing new items or by remanufacturing used items. Unprocessed used items are disposed. We show the NP‐hardness of the problem even when all the costs are stationary. Utilizing the special structure of the extreme‐point optimal solutions for the minimum concave‐cost problem with a network flow type feasible region, we develop a polynomial‐time heuristic for the problem. Our computational study indicates that the heuristic is a very efficient way to solve the problem as far as solution speed and quality are concerned. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

The (s,Q) inventory model with Erlang lead time and deterministic demand

We develop a simple, approximately optimal solution to a model with Erlang lead time and deterministic demand. The method is robust to misspecification of the lead time and has good accuracy. We compare our approximate solution to the optimal for the case where we have prior information on the lead‐time distribution, and another where we have no information, except for computer‐generated sample data. It turns out that our solution is as easy as the EOQ's, with an accuracy rate of 99.41% when prior information on the lead‐time distribution is available and 97.54–99.09% when only computer‐generated sample information is available. Apart from supplying the inventory practitioner with an easy heuristic, we gain insights into the efficacy of stochastic lead time models and how these could be used to find the cost and a near‐optimal policy for the general model, where both demand rate and lead time are stochastic. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

An efficient metaheuristic for integrated scheduling and staffing IT projects based on a generalized minimum cost flow network

Scheduling IT projects and assigning the project work to human resources are an important and common tasks in almost any IT service company. It is particularly complex because human resources usually have multiple skills. Up to now only little work has considered IT‐specific properties of the project structure and human resources. In this article, we present an optimization model that simultaneously schedules the activities of multiple IT projects with serial network structures and assigns the project work to multiskilled internal and external human resources with different efficiencies. The goal is to minimize costs. We introduce a metaheuristic that decomposes the problem into a binary scheduling problem and a continuous staffing problem where the latter is solved efficiently by exploiting its underlying network structure. For comparison, we solve the mixed–binary linear program with a state–of–the–art commercial solver. The impacts of problem parameters on computation time and solution gaps between the metaheuristic and the solver are assessed in an experimental study. Our results show that the metaheuristic provides very favorable results in considerable less time than the solver for midsize problems. For larger problems, it shows a similar performance while the solver fails to return feasible solutions. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 111–127, 2012     

Algorithms for the multi‐item multi‐vehicles dynamic lot sizing problem

We consider a two‐stage supply chain, in which multi‐items are shipped from a manufacturing facility or a central warehouse to a downstream retailer that faces deterministic external demand for each of the items over a finite planning horizon. The items are shipped through identical capacitated vehicles, each incurring a fixed cost per trip. In addition, there exist item‐dependent variable shipping costs and inventory holding costs at the retailer for items stored at the end of the period; these costs are constant over time. The sum of all costs must be minimized while satisfying the external demand without backlogging. In this paper we develop a search algorithm to solve the problem optimally. Our search algorithm, although exponential in the worst case, is very efficient empirically due to new properties of the optimal solution that we found, which allow us to restrict the number of solutions examined. Second, we perform a computational study that compares the empirical running time of our search methods to other available exact solution methods to the problem. Finally, we characterize the conditions under which each of the solution methods is likely to be faster than the others and suggest efficient heuristic solutions that we recommend using when the problem is large in all dimensions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

Nonpreemptive scheduling of independent tasks with prespecified processor allocations

In this article we study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of prespecified processors, with the objective of minimizing the maximum completion time. We propose a graph-theoretical approach and identify a class of polynomial instances, corresponding to comparability graphs. We show that the scheduling problem is polynomially equivalent to the problem of extending a graph to a comparability graph whose maximum weighted clique has minimum weight. Using this formulation we show that in some cases it is possible to decompose the problem according to the canonical decomposition of the graph. Finally, a general solution procedure is given that includes a branch-and-bound algorithm for the solution of subproblems which can be neither decomposed nor solved in polynomial time. Some examples and computational results are presented. © 1994 John Wiley & Sons, Inc.     

Benders decomposition with alternative multiple cuts for a multi‐product closed‐loop supply chain network design model

In this article, we consider a multi‐product closed‐loop supply chain network design problem where we locate collection centers and remanufacturing facilities while coordinating the forward and reverse flows in the network so as to minimize the processing, transportation, and fixed location costs. The problem of interest is motivated by the practice of an original equipment manufacturer in the automotive industry that provides service parts for vehicle maintenance and repair. We provide an effective problem formulation that is amenable to efficient Benders reformulation and an exact solution approach. More specifically, we develop an efficient dual solution approach to generate strong Benders cuts, and, in addition to the classical single Benders cut approach, we propose three different approaches for adding multiple Benders cuts. These cuts are obtained via dual problem disaggregation based either on the forward and reverse flows, or the products, or both. We present computational results which illustrate the superior performance of the proposed solution methodology with multiple Benders cuts in comparison to the branch‐and‐cut approach as well as the traditional Benders decomposition approach with a single cut. In particular, we observe that the use of multiple Benders cuts generates stronger lower bounds and promotes faster convergence to optimality. We also observe that if the model parameters are such that the different costs are not balanced, but, rather, are biased towards one of the major cost categories (processing, transportation or fixed location costs), the time required to obtain the optimal solution decreases considerably when using the proposed solution methodology as well as the branch‐and‐cut approach. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

条（环）状干摩擦阻尼器的微滑移数值模型

提出一种求解弹性条(环)状阻尼器微滑移接触运动的数值方法。将阻尼器和外部激励历程在空间和时间上离散,将相同数量的干摩擦触点布置于离散阻尼器上;把接触运动判据应用到各离散接触点,确定其运动状态并修正刚度矩阵,求解整个阻尼器的平衡方程。该方法避免了有限元软件求解含摩擦接触问题的迭代过程,从而保证了求解的可执行性。同时,克服了微滑移模型理论解法对法向载荷分布规律及载荷时变性的限制,为求解具有局部性以及时变性的法向载荷的结构动态响应提供了更为精确的边界条件,从而可提高结构频响分析的准确性。应用多谐波平衡法分别计算宏滑移和微滑移阻尼器约束下的结构动态响应,发现在结构减振中,微滑移模型能够适应更宽范围的法向力。     

Distribution network design: Selection and sizing of congested connections

This paper focuses on certain types of distribution networks in which commodity flows must go through connections that are subject to congestion. Connections serve as transshipment and/or switching points and are modeled as M/G/1 queues. The goal is to select connections, assign flows to the connections, and size their capacities, simultaneously. The capacities are controlled by both the mean and the variability of service time at each connection. We formulate this problem as a mixed integer nonlinear optimization problem for both the fixed and variable service rate cases. For the fixed service rate case, we prove that the objective function is convex and then develop an outer approximation algorithm. For the variable service rate case, both mean and second moment of service time are decision variables. We establish that the utilization rates at the homogeneous connections are identical for an optimal solution. Based on this key finding, we develop a Lagrangian relaxation algorithm. Numerical experiments are conducted to verify the quality of the solution techniques proposed. The essential contribution of this work is the explicit modeling of connection capacity (through the mean and the variability of service time) using a queueing framework. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

A recursive branch and bound algorithm for the multidimensional knapsack problem

This paper presents an efficient branch and bound algorithm for the solution of certain multiconstrained knapsack problems. The key to this algorithm is a rigidly defined tree structure in which branching and bounding may be performed through recursive relationships. The algorithm is particularly useful when only limited amounts of core storage are available as only the current and one previous solution is saved at any one time. Execution speeds compare favorably with other algorithms. A numerical example and computational experience is given.     

Formulations for dynamic lot sizing with service levels

In this article, we study deterministic dynamic lot‐sizing problems with a service‐level constraint on the total number of periods in which backlogs can occur over a finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS‐SL‐I) and study the structure of its solution. We show that an optimal solution to this problem can be found in \begin{align*}\mathcal O(n^2\kappa)\end{align*} time, where n is the planning horizon and \begin{align*}\kappa=\mathcal O(n)\end{align*} is the maximum number of periods in which demand can be backlogged. Using the proposed shortest path algorithms, we develop alternative tight extended formulations for LS‐SL‐I and one of its relaxations, which we refer to as uncapacitated lot sizing with setups for stocks and backlogs. {We show that this relaxation also appears as a substructure in a lot‐sizing problem which limits the total amount of a period's demand met from a later period, across all periods.} We report computational results that compare the natural and extended formulations on multi‐item service‐level constrained instances. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Optimal service and arrival rates in Jackson queueing networks

In this paper we present an algorithm for solving a class of queueing network design problems. Specifically, we focus on determining both service and arrival rates in an open Jackson network of queueing stations. This class of problems has been widely studied and used in a variety of applications, but not well solved due to the difficulty of the resulting optimization problems. As an example, consider the classic application in computer network design which involves determining the minimum cost line capacities and flow assignments while satisfying a queueing performance measure such as an upper limit on transmission delay. Other application areas requiring the selection of both service and arrival rates in a network of queues include the design of communication, manufacturing, and health care systems. These applications yield optimization problems that are difficult to solve because typically they are nonconvex, which means they may have many locally optimal solutions that are not necessarily globally optimal. Therefore, to obtain a globally optimal solution, we develop an efficient branch and bound algorithm that takes advantage of the problem structure. Computational testing on randomly generated problems and actual problems from a health care organization indicate that the algorithm is able to solve realistic sized problems in reasonable computing time on a laptop computer. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 1–17, 2000     

Coordinated overhaul scheduling of production units

This article presents a new approach to solve the problem of coordinating the overhaul scheduling of several nonidentical production units. For each production unit, we assume that the operating cost is an n-order polynomial function of the time elapsed since its previous overhaul. We develop an efficient iterative algorithm that generates a near-optimal cyclic overhaul schedule. We also construct a simple algorithm for the case where the overhaul interval for each production unit and the cycle time are restricted to be power-of-two multiples of some base planning period. Finally, we provide a worst-case performance bound for the solution to the problem under the power-of-two restriction. © 1994 John Wiley & Sons, Inc.     

Stochastic call center staffing with uncertain arrival,service and abandonment rates: A Bayesian perspective

In this article, we introduce staffing strategies for the Erlang‐A queuing system in call center operations with uncertain arrival, service, and abandonment rates. In doing so, we model the system rates using gamma distributions that create randomness in operating characteristics used in the optimization formulation. We divide the day into discrete time intervals where a simulation based stochastic programming method is used to determine staffing levels. More specifically, we develop a model to select the optimal number of agents required for a given time interval by minimizing an expected cost function, which consists of agent and abandonment (opportunity) costs, while considering the service quality requirements such as the delay probability. The objective function as well as the constraints in our formulation are random variables. The novelty of our approach is to introduce a solution method for the staffing of an operation where all three system rates (arrival, service, and abandonment) are random variables. We illustrate the use of the proposed model using both real and simulated call center data. In addition, we provide solution comparisons across different formulations, consider a dynamic extension, and discuss sensitivity implications of changing constraint upper bounds as well as prior hyper‐parameters. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 460–478, 2016     

Route optimization for multiple searchers

We consider a discrete time‐and‐space route‐optimization problem across a finite time horizon in which multiple searchers seek to detect one or more probabilistically moving targets. This article formulates a novel convex mixed‐integer nonlinear program for this problem that generalizes earlier models to situations with multiple targets, searcher deconfliction, and target‐ and location‐dependent search effectiveness. We present two solution approaches, one based on the cutting‐plane method and the other on linearization. These approaches result in the first practical exact algorithms for solving this important problem, which arises broadly in military, rescue, law enforcement, and border patrol operations. The cutting‐plane approach solves many realistically sized problem instances in a few minutes, while existing branch‐and‐bound algorithms fail. A specialized cut improves solution time by 50[percnt] in difficult problem instances. The approach based on linearization, which is applicable in important special cases, may further reduce solution time with one or two orders of magnitude. The solution time for the cutting‐plane approach tends to remain constant as the number of searchers grows. In part, then, we overcome the difficulty that earlier solution methods have with many searchers. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

一种无线传感器网络中的Sybil攻击检测方案

Sybil攻击破坏无线传感器网络中的数据融合、公平资源分配等机制，因此对Sybil攻击的防范与检测具有很重要的意义。将一种基于到达时间差（TDOA）的三维定位引入到Sybil攻击的检测中，算法可以检测存在的Sybil攻击并对Sybil节点进行定位。通过性能分析证明该算法具有开销小、有效性高的特点。     

An optimum group maintenance policy

In this article we present an optimum maintenance policy for a group of machines subject to stochastic failures where the repair cost and production loss due to the breakdown of machines are minimized. A nomograph was developed for machines with exponential failure time distributions. The optimal schedule time for repair as well as the total repair cost per cycle can be obtained easily from the nomograph. Conditions for the existence of a unique solution for the optimum schedule and the bounds for the schedule are discussed.     

一类不匹配不确定非线性系统鲁棒变结构控制

针对一类具有不匹配非参数化不确定性的非线性系统 ,设计出一种鲁棒变结构控制器。该控制器能够保证当时间 t趋于无穷时 ,闭环控制系统的输出跟踪误差趋于零。仿真实例说明了该控制器具有满意的控制效果