A m‐parallel crane scheduling problem with a non‐crossing constraint

In this paper, we study a m‐parallel machine scheduling problem with a non‐crossing constraint motivated by crane scheduling in ports. We decompose the problem to allow time allocations to be determined once crane assignments are known and construct a backtracking search scheme that manipulates domain reduction and pruning strategies. Simple approximation heuristics are developed, one of which guarantees solutions to be at most two times the optimum. For large‐scale problems, a simulated annealing heuristic that uses random neighborhood generation is provided. Computational experiments are conducted to test the algorithms. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

A self‐adapting genetic algorithm for project scheduling under resource constraints

This papers deals with the classical resource‐constrained project scheduling problem (RCPSP). There, the activities of a project have to be scheduled subject to precedence and resource constraints. The objective is to minimize the makespan of the project. We propose a new heuristic called self‐adapting genetic algorithm to solve the RCPSP. The heuristic employs the well‐known activity list representation and considers two different decoding procedures. An additional gene in the representation determines which of the two decoding procedures is actually used to compute a schedule for an individual. This allows the genetic algorithm to adapt itself to the problem instance actually solved. That is, the genetic algorithm learns which of the alternative decoding procedures is the more successful one for this instance. In other words, not only the solution for the problem, but also the algorithm itself is subject to genetic optimization. Computational experiments show that the mechanism of self‐adaptation is capable to exploit the benefits of both decoding procedures. Moreover, the tests show that the proposed heuristic is among the best ones currently available for the RCPSP. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 433–448, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10029     

Asymptotically optimal linear time algorithms for two‐stage and three‐stage flexible flow shops

We consider two‐stage and three‐stage flexible flow shops with parallel machines in each stage and the minimum makespan objective. We develop linear time algorithms for these problems with absolute worst‐case bounds either sharper or no worse than the currently available ones and we accomplish this with lower complexity algorithms. We also demonstrate the asymptotic optimality of a class of algorithms for multistage flexible flow shop problems (which includes the proposed algorithms) under certain probabilistic assumptions on the job processing times. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 259–268, 2000     

A misclassification cost‐minimizing evolutionary–neural classification approach

Machine learning algorithms that incorporate misclassification costs have recently received considerable attention. In this paper, we use the principles of evolution to develop and test an evolutionary/genetic algorithm (GA)‐based neural approach that incorporates asymmetric Type I and Type II error costs. Using simulated, real‐world medical and financial data sets, we compare the results of the proposed approach with other statistical, mathematical, and machine learning approaches, which include statistical linear discriminant analysis, back‐propagation artificial neural network, integrated cost preference‐based linear mathematical programming‐based minimize squared deviations, linear integrated cost preference‐based GA, decision trees (C 5.0, and CART), and inexpensive classification with expensive tests algorithm. Our results indicate that the proposed approach incorporating asymmetric error costs results in equal or lower holdout sample misclassification cost when compared with the other statistical, mathematical, and machine learning misclassification cost‐minimizing approaches. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

Case‐based reasoning and improved adaptive search for project scheduling

Most scheduling problems are notoriously intractable, so the majority of algorithms for them are heuristic in nature. Priority rule‐based methods still constitute the most important class of these heuristics. Of these, in turn, parametrized biased random sampling methods have attracted particular interest, due to the fact that they outperform all other priority rule‐based methods known. Yet, even the “best” such algorithms are unable to relate to the full range of instances of a problem: Usually there will exist instances on which other algorithms do better. We maintain that asking for the one best algorithm for a problem may be asking too much. The recently proposed concept of control schemes, which refers to algorithmic schemes allowing to steer parametrized algorithms, opens up ways to refine existing algorithms in this regard and improve their effectiveness considerably. We extend this approach by integrating heuristics and case‐based reasoning (CBR), an approach that has been successfully used in artificial intelligence applications. Using the resource‐constrained project scheduling problem as a vehicle, we describe how to devise such a CBR system, systematically analyzing the effect of several criteria on algorithmic performance. Extensive computational results validate the efficacy of our approach and reveal a performance similar or close to state‐of‐the‐art heuristics. In addition, the analysis undertaken provides new insight into the behaviour of a wide class of scheduling heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 201–222, 2000     

Cyclic best first search: Using contours to guide branch‐and‐bound algorithms

The cyclic best‐first search (CBFS) strategy is a recent search strategy that has been successfully applied to branch‐and‐bound algorithms in a number of different settings. CBFS is a modification of best‐first search (BFS) that places search tree subproblems into contours which are collections of subproblems grouped in some way, and repeatedly cycles through all non‐empty contours, selecting one subproblem to explore from each. In this article, the theoretical properties of CBFS are analyzed for the first time. CBFS is proved to be a generalization of all other search strategies by using a contour definition that explores the same sequence of subproblems as any other search strategy. Further, a bound is proved between the number of subproblems explored by BFS and the number of children generated by CBFS, given a fixed branching strategy and set of pruning rules. Finally, a discussion of heuristic contour‐labeling functions is provided, and proof‐of‐concept computational results for mixed‐integer programming problems from the MIPLIB 2010 database are shown. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 64–82, 2017     

Multi‐period maintenance scheduling of tree networks with minimum flow disruption

We introduce a multi‐period tree network maintenance scheduling model and investigate the effect of maintenance capacity restrictions on traffic/information flow interruptions. Network maintenance refers to activities that are performed to keep a network operational. For linear networks with uniform flow between every pair of nodes, we devise a polynomial‐time combinatorial algorithm that minimizes flow disruption. The spiral structure of the optimal maintenance schedule sheds insights into general network maintenance scheduling. The maintenance problem on linear networks with a general flow structure is strongly NP‐hard. We formulate this problem as a linear integer program, derive strong valid inequalities, and conduct a polyhedral study of the formulation. Polyhedral analysis shows that the relaxation of our linear network formulation is tight when capacities and flows are uniform. The linear network formulation is then extended to an integer program for solving the tree network maintenance scheduling problem. Preliminary computations indicate that the strengthened formulations can solve reasonably sized problems on tree networks and that the intuitions gained from the uniform flow case continue to hold in general settings. Finally, we extend the approach to directed networks and to maintenance of network nodes. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Proactive release procedures for just‐in‐time job shop environments,subject to machine failures

In this paper, we consider just‐in‐time job shop environments (job shop problems with an objective of minimizing the sum of tardiness and inventory costs), subject to uncertainty due to machine failures. We present techniques for proactive uncertainty management that exploit prior knowledge of uncertainty to build competitive release dates, whose execution improves performance. These techniques determine the release dates of different jobs based on measures of shop load, statistical data of machine failures, and repairs with a tradeoff between inventory and tardiness costs. Empirical results show that our methodology is very promising in comparison with simulated annealing and the best of 39 combinations of dispatch rules & release policies, under different frequencies of breakdowns. We observe that the performance of the proactive technique compared to the other two approaches improves in schedule quality (maximizing delivery performance while minimizing costs) with increase in frequency of breakdowns. The proactive technique presented here is also computationally less expensive than the other two approaches. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Path optimization for the resource‐constrained searcher

We formulate and solve a discrete‐time path‐optimization problem where a single searcher, operating in a discretized three‐dimensional airspace, looks for a moving target in a finite set of cells. The searcher is constrained by maximum limits on the consumption of one or more resources such as time, fuel, and risk along any path. We develop a specialized branch‐and‐bound algorithm for this problem that uses several network reduction procedures as well as a new bounding technique based on Lagrangian relaxation and network expansion. The resulting algorithm outperforms a state‐of‐the‐art algorithm for solving time‐constrained problems and also is the first algorithm to solve multi‐constrained problems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Subspace dynamic‐simplex linear interpolation search for mixed‐integer black‐box optimization problems

Design and management of complex systems with both integer and continuous decision variables can be guided using mixed‐integer optimization models and analysis. We propose a new mixed‐integer black‐box optimization (MIBO) method, subspace dynamic‐simplex linear interpolation search (SD‐SLIS), for decision making problems in which system performance can only be evaluated with a computer black‐box model. Through a sequence of gradient‐type local searches in subspaces of solution space, SD‐SLIS is particularly efficient for such MIBO problems with scaling issues. We discuss the convergence conditions and properties of SD‐SLIS algorithms for a class of MIBO problems. Under mild conditions, SD‐SLIS is proved to converge to a stationary solution asymptotically. We apply SD‐SLIS to six example problems including two MIBO problems associated with petroleum field development projects. The algorithm performance of SD‐SLIS is compared with that of a state‐of‐the‐art direct‐search method, NOMAD, and that of a full space simplex interpolation search, Full‐SLIS. The numerical results suggest that SD‐SLIS solves the example problems efficiently and outperforms the compared methods for most of the example cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 305–322, 2017     

The stochastic U‐line balancing problem

A U‐line arranges tasks around a U‐shaped production line and organizes them into stations that can cross from one side of the line to the other. In addition to improving visibility and communication between operators on the line, which facilitates problem‐solving and quality improvement, U‐lines can reduce the total number of operators required on the line and make rebalancing the line easier compared to the traditional, straight production line. This paper studies the (type 1) U‐line balancing problem when task completion times are stochastic. Stochastic completion times occur when differences between operators cause completion times to vary somewhat and when machine processing times vary. A recursive algorithm is presented for finding the optimal solution when completion times have any distribution function. An equivalent shortest path network is also presented. An improvement for the special case of normally distributed task completion times is given. A computational study to determine the characteristics of instances that can be solved by the algorithms shows that they are able to solve instances of practical size (like the 114 Japanese and U.S. U‐lines studied in a literature review paper). © 2002 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

On the uncapacitated K‐commodity network design problem with zero flow‐costs

Extending Sastry's result on the uncapacitated two‐commodity network design problem, we completely characterize the optimal solution of the uncapacitated K‐commodity network design problem with zero flow costs for the case when K = 3. By solving a set of shortest‐path problems on related graphs, we show that the optimal solutions can be found in O(n³) time when K = 3, where n is the number of nodes in the network. The algorithm depends on identifying a list of “basic patterns”; the number of basic patterns grows exponentially with K. We also show that the uncapacitated K‐commodity network design problem can be solved in O(n³) time for general K if K is fixed; otherwise, the time for solving the problem is exponential. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

一种模拟退火伪并行遗传算法

借鉴模拟退火算法的局部搜索能力,结合并行计算的思想设计了一种采用模拟退火机制的实数编码自适应交叉、全概率变异伪并行遗传算法,最后用这种方法对典型的多峰值函数求极值,并和基本遗传算法进行比较,结果表明:该算法具有较强的全局搜索能力和局部搜索能力,能够更有效地克服早熟收敛问题。     

A branch and bound algorithm for computing optimal replacement policies in consecutive k‐out‐of‐n‐systems

This paper presents a branch and bound algorithm for computing optimal replacement policies in a discrete‐time, infinite‐horizon, dynamic programming model of a binary coherent system with n statistically independent components, and then specializes the algorithm to consecutive k‐out‐of‐n systems. The objective is to minimize the long‐run expected average undiscounted cost per period. (Costs arise when the system fails and when failed components are replaced.) An earlier paper established the optimality of following a critical component policy (CCP), i.e., a policy specified by a critical component set and the rule: Replace a component if and only if it is failed and in the critical component set. Computing an optimal CCP is a optimization problem with n binary variables and a nonlinear objective function. Our branch and bound algorithm for solving this problem has memory storage requirement O(n) for consecutive k‐out‐of‐n systems. Extensive computational experiments on such systems involving over 350,000 test problems with n ranging from 10 to 150 find this algorithm to be effective when n ≤ 40 or k is near n. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 288–302, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10017     

Worst‐case performance of approximation algorithms for tool management problems

Since the introduction of flexible manufacturing systems, researchers have investigated various planning and scheduling problems faced by the users of such systems. Several of these problems are not encountered in more classical production settings, and so‐called tool management problems appear to be among the more fundamental ones of these problems. Most tool management problems are hard to solve, so that numerous approximate solution techniques have been proposed to tackle them. In this paper, we investigate the quality of such algorithms by means of worst‐case analysis. We consider several polynomial‐time approximation algorithms described in the literature, and we show that all these algorithms exhibit rather poor worst‐case behavior. We also study the complexity of solving tool management problems approximately. In this respect, we investigate the interrelationships among tool management problems, as well as their relationships with other well‐known combinatorial problems such as the maximum clique problem or the set covering problem, and we prove several negative results on the approximability of various tool management problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 445–462, 1999     

Client‐contractor bargaining on net present value in project scheduling with limited resources

The client‐contractor bargaining problem addressed here is in the context of a multi‐mode resource constrained project scheduling problem with discounted cash flows, which is formulated as a progress payments model. In this model, the contractor receives payments from the client at predetermined regular time intervals. The last payment is paid at the first predetermined payment point right after project completion. The second payment model considered in this paper is the one with payments at activity completions. The project is represented on an Activity‐on‐Node (AON) project network. Activity durations are assumed to be deterministic. The project duration is bounded from above by a deadline imposed by the client, which constitutes a hard constraint. The bargaining objective is to maximize the bargaining objective function comprised of the objectives of both the client and the contractor. The bargaining objective function is expected to reflect the two‐party nature of the problem environment and seeks a compromise between the client and the contractor. The bargaining power concept is introduced into the problem by the bargaining power weights used in the bargaining objective function. Simulated annealing algorithm and genetic algorithm approaches are proposed as solution procedures. The proposed solution methods are tested with respect to solution quality and solution times. Sensitivity analyses are conducted among different parameters used in the model, namely the profit margin, the discount rate, and the bargaining power weights. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

基于遗传模拟退火算法的空袭兵力分配及优化

对遗传模拟退火算法中的交叉、变异操作进行了改进,并实施了最优保留策略,形成了改进遗传模拟退火算法.以突击效果最大化和兵力损失最小化为目标函数,以空袭兵力总量的限制、空袭兵器挂载类型的限制等为约束条件,建立了空袭兵力分配及优化模型.在考虑兵力分配模型特点的基础上,利用改进遗传模拟退火算法求解.通过与多目标数学规划和标准遗传算法优化进行的比较表明,该方法能够有效地解决带约束的多目标优化问题.     

Incorporation dynamic aspects and uncertainty in 1‐median location problems

In this paper we present several 1‐median formulations on a tree network which incorporate dynamic evolution and/or uncertainty of node demands and transportation costs over a planning horizon. Dynamic evolution is modeled using linear demand functions for the nodes and linear length functions for the edges. Uncertainty is modeled with the use of multiple scenarios, where a scenario is a complete specification of the uncertain node demands and/or edge lengths. We formulate our objective using minimax regret like criteria. We use two different criteria, namely, robust deviation and relative robustness. We discuss what motivated the introduction of these objectives, as well as their relation to existing literature and decision making practices. For all of the models presented, we provide low‐order polynomial time algorithms. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 147–168, 1999     

Two‐stage component test plans for testing the reliability of a series system

A system reliability is often evaluated by individual tests of components that constitute the system. These component test plans have advantages over complete system based tests in terms of time and cost. In this paper, we consider the series system with n components, where the lifetime of the i‐th component follows exponential distribution with parameter λ_i. Assuming test costs for the components are different, we develop an efficient algorithm to design a two‐stage component test plan that satisfies the usual probability requirements on the system reliability and in addition minimizes the maximum expected cost. For the case of prior information in the form of upper bounds on λ_i's, we use the genetic algorithm to solve the associated optimization problems which are otherwise difficult to solve using mathematical programming techniques. The two‐stage component test plans are cost effective compared to single‐stage plans developed by Rajgopal and Mazumdar. We demonstrate through several numerical examples that our approach has the potential to reduce the overall testing costs significantly. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 95–116, 2002; DOI 10.1002/nav.1051     

The network redesign problem for access telecommunications networks

The network redesign problem attempts to design an optimal network that serves both existing and new demands. In addition to using spare capacity on existing network facilities and deploying new facilities, the model allows for rearrangement of existing demand units. As rearrangements mean reassigning existing demand units, at a cost, to different facilities, they may lead to disconnecting of uneconomical existing facilities, resulting in significant savings. The model is applied to an access network, where the demands from many sources need to be routed to a single destination, using either low‐capacity or high‐capacity facilities. Demand from any location can be routed to the destination either directly or through one other demand location. Low‐capacity facilities can be used between any pair of locations, whereas high‐capacity facilities are used only between demand locations and the destination. We present a new modeling approach to such problems. The model is described as a network flow problem, where each demand location is represented by multiple nodes associated with demands, low‐capacity and high‐capacity facilities, and rearrangements. Each link has a capacity and a cost per unit flow parameters. Some of the links also have a fixed‐charge cost. The resulting network flow model is formulated as a mixed integer program, and solved by a heuristic and a commercially available software. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 487–506, 1999