A face search heuristic algorithm for optimizing over the efficient set

The problem of optimizing a linear function over the efficient set of a multiple objective linear program is an important but difficult problem in multiple criteria decision making. In this article we present a flexible face search heuristic algorithm for the problem. Preliminary computational experiments indicate that the algorithm gives very good estimates of the global optimum with relatively little computational effort. © 1993 John Wiley & Sons, Inc.     

Composite unimodality

This article defines a class of univariate functions termed composite unimodal, and shows how their minimization admits an effective search procedure, albeit one not as efficient as is Fibonacci search for unimodal functions. An approximate Lagrangian approach to an important real-world logistics problem is seen to yield a surrogate problem whose objective function is composite unimodal. The mathematical form of this objective function is likely to be encountered in solving future real-world problems. © 1993 John Wiley & Sons, Inc.     

Approximating nondominated sets in continuous multiobjective optimization problems

Many important problems in Operations Research and Statistics require the computation of nondominated (or Pareto or efficient) sets. This task may be currently undertaken efficiently for discrete sets of alternatives or for continuous sets under special and fairly tight structural conditions. Under more general continuous settings, parametric characterisations of the nondominated set, for example through convex combinations of the objective functions or ε‐constrained problems, or discretizations‐based approaches, pose several problems. In this paper, the lack of a general approach to approximate the nondominated set in continuous multiobjective problems is addressed. Our simulation‐based procedure only requires to sample from the set of alternatives and check whether an alternative dominates another. Stopping rules, efficient sampling schemes, and procedures to check for dominance are proposed. A continuous approximation to the nondominated set is obtained by fitting a surface through the points of a discrete approximation, using a local (robust) regression method. Other actions like clustering and projecting points onto the frontier are required in nonconvex feasible regions and nonconnected Pareto sets. In a sense, our method may be seen as an evolutionary algorithm with a variable population size. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Production and transport logistics scheduling with two transport mode choices

This paper considers a new class of scheduling problems arising in logistics systems in which two different transportation modes are available at the stage of product delivery. The mode with the shorter transportation time charges a higher cost. Each job ordered by the customer is first processed in the manufacturing facility and then transported to the customer. There is a due date for each job to arrive to the customer. Our approach integrates the machine scheduling problem in the manufacturing stage with the transportation mode selection problem in the delivery stage to achieve the global maximum benefit. In addition to studying the NP‐hard special case in which no tardy job is allowed, we consider in detail the problem when minimizing the sum of the total transportation cost and the total weighted tardiness cost is the objective. We provide a branch and bound algorithm with two different lower bounds. The effectiveness of the two lower bounds is discussed and compared. We also provide a mathematical model that is solvable by CPLEX. Computational results show that our branch and bound algorithm is more efficient than CPLEX. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Minimizing sums and products of linear fractional functions over a polytope

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999     

Batch scheduling with step‐deteriorating processing times to minimize flowtime

Both topics of batch scheduling and of scheduling deteriorating jobs have been very popular among researchers in the last two decades. In this article, we study a model combining these two topics. We consider a classical batch scheduling model with unit‐jobs and batch‐independent setup times, and a model of step‐deterioration of processing times. The objective function is minimum flowtime. The optimal solution of the relaxed version (allowing non‐integer batch sizes) is shown to have a unique structure consisting of two consecutive decreasing arithmetic sequences of batch sizes. We also introduce a simple and efficient rounding procedure that guarantees integer batch sizes. The entire solution procedure requires an effort of O(n) (where nis the number of jobs.) © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

应急物资保障计划辅助决策模型

提出了一个制定应急物资保障计划的流程,构建了制定应急物资保障计划的数学模型,并应用运筹学的方法对其进行了优化.该模型为制定应急物资保障计划提供了有效的途径.     

Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.     

A branch‐and‐bound‐based solution approach for dynamic rerouting of airborne platforms

This article is a sequel to a recent article that appeared in this journal, “An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations” [ 17 ], in which an integer programming formulation to the problem of rescheduling in‐flight assets due to changes in battlespace conditions was presented. The purpose of this article is to present an improved branch‐and‐bound procedure to solve the dynamic resource management problem in a timely fashion, as in‐flight assets must be quickly re‐tasked to respond to the changing environment. To facilitate the rapid generation of attractive updated mission plans, this procedure uses a technique for reducing the solution space, supports branching on multiple decision variables simultaneously, incorporates additional valid cuts to strengthen the minimal network constraints of the original mathematical model, and includes improved objective function bounds. An extensive numerical analysis indicates that the proposed approach significantly outperforms traditional branch‐and‐bound methodologies and is capable of providing improved feasible solutions in a limited time. Although inspired by the dynamic resource management problem in particular, this approach promises to be an effective tool for solving other general types of vehicle routing problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A competitive genetic algorithm for resource-constrained project scheduling

In this paper we consider the resource-constrained project scheduling problem (RCPSP) with makespan minimization as objective. We propose a new genetic algorithm approach to solve this problem. Subsequently, we compare it to two genetic algorithm concepts from the literature. While our approach makes use of a permutation based genetic encoding that contains problem-specific knowledge, the other two procedures employ a priority value based and a priority rule based representation, respectively. Then we present the results of our thorough computational study for which standard sets of project instances have been used. The outcome reveals that our procedure is the most promising genetic algorithm to solve the RCPSP. Finally, we show that our genetic algorithm yields better results than several heuristic procedures presented in the literature. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 733–750, 1998     

Performance and properties of Q‐Statistic monitoring schemes

In this article, we study the Shewhart chart of Q statistics proposed for the detection of process mean shifts in start‐up processes and short runs. Exact expressions for the run‐length distribution of this chart are derived and evaluated using an efficient computational procedure. The procedure can be considerably faster than using direct simulation. We extend our work to analyze the practice of requiring multiple signals from the chart before responding, a practice sometimes followed with Shewhart charts. The results show that waiting to receive multiple signals severely reduces the probability of quickly detecting shifts in certain cases, and therefore may be considered a risky practice. Operational guidelines for practitioners implementing the chart are discussed. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Lot sizing when yields increase during the production run

We investigate the problem of determining lot sizes for multiple items when the expected percentage of acceptable output increases with the duration of the production run, usually due to adjustments made during the early part of the production run. Such problems arise in metal stamping, textile finishing processes, and a variety of other industries. The goal is to minimize the total cost of production, inventory holding costs, and setup costs (where applicable). We develop a heuristic procedure based on a Lagrangian relaxation that differs from relaxations used in earlier studies. We use various properties of the objective function to guide the adjustment of the initial solution from the relaxation toward feasibility. Computational results indicate that, on the average, the heuristic produces solutions within 4.9% of the lower bound obtained from the Lagrangian relaxation. © 1996 John Wiley & Sons, Inc.     

Optimal clustering: A model and method

Classifying items into distinct groupings is fundamental in scientific inquiry. The objective of cluster analysis is to assign n objects to up to K mutually exclusive groups while minimizing some measure of dissimilarity among the items. Few mathematical programming approaches have been applied to these problems. Most clustering methods to date only consider lowering the amount of interaction between each observation and the group mean or median. Clustering used in information systems development to determine groupings of modules requires a model that will account for the total group interaction. We formulate a mixed-integer programming model for optimal clustering based upon scaled distance measures to account for this total group interaction. We discuss an efficient, implicit enumeration algorithm along with some implementation issues, a method for computing tight bounds for each node in the solution tree, and a small example. A computational example problem, taken from the computer-assisted process organization (CAPO) literature, is presented. Detailed computational results indicate that the method is effective for solving this type of cluster analysis problem.     

Lagrangian relaxation approach to the targeting problem

In this paper, we consider a new weapon–target allocation problem with the objective of minimizing the overall firing cost. The problem is formulated as a nonlinear integer programming model. We applied Lagrangian relaxation and a branch‐and‐bound method to the problem after transforming the nonlinear constraints into linear ones. An efficient primal heuristic is developed to find a feasible solution to the problem to facilitate the procedure. In the branch‐and‐bound method, three different branching rules are considered and the performances are evaluated. Computational results using randomly generated data are presented. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 640–653, 1999     

基于多目标模糊决策模型的联合作战方案优选

为选择作战方案中的最优方案,对所有的方案进行了排序,依据定性准则和定量的数学模型,利用多目标模糊决策分析方法,对联合作战方案的相关因素进行了分析,综合评价出各方案的优劣程度,最后得到了较为合理的作战方案先后顺序.     

A heuristic approach to bicriteria scheduling

We consider the problem of sequencing jobs on a single machine while minimizing a nondecreasing function of two criteria. We develop a heuristic procedure that quickly finds a good solution for bicriteria scheduling. The procedure is based on using several arcs in the criterion space that are representative of the possible locations of nondominated solutions. By sampling a small number of points on these arcs, a promising point is identified in the criterion space for each arc. An efficient sequence in the neighborhood of each of the promising points is found and the best of these efficient sequences is selected as the heuristic solution. We implement the procedure for two different bicriteria scheduling problems: (i) minimizing total flowtime and maximum tardiness and (ii) minimizing total flowtime and maximum earliness. The computational experience on a wide variety of problem instances show that the heuristic approach is very robust and yields good solutions. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 777–789, 1999     

Multiple subset sum with inclusive assignment set restrictions

In a traditional multiple subset sum problem (MSSP), there is a given set of items and a given set of bins (or knapsacks) with identical capacities. The objective is to select a subset of the items and pack them into the bins such that the total weight of the selected items is maximized. However, in many applications of the MSSP, the bins have assignment restrictions. In this article, we study the subset sum problem with inclusive assignment set restrictions, in which the assignment set of one item (i.e., the set of bins that the item may be assigned to) must be either a subset or a superset of the assignment set of another item. We develop an efficient 0.6492‐approximation algorithm and test its effectiveness via computational experiments. We also develop a polynomial time approximation scheme for this problem. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph—a directed series‐parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series‐parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574–592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031     

A quadratic assignment problem without column constraints

We convert a quadratic assignment problem [1] with a nonconvex objective function into an integer linear program. We then solve the equivalent integer program by a simple enumeration that produces global minima.     

Minimax resource allocation problems with ordering constraints

Resource allocation problems consider the allocation of limited resources among numerous competing activities. We address an allocation problem with multiple knapsack resource constraints. The activities are grouped into disjoint sets. Ordering constraints are imposed on the activities within each set, so that the level of one activity cannot exceed the level of another activity in the same set. The objective function is of the minimax type and each performance function is a nonlinear, strictly decreasing and continuous function of a single variable. Applications for such resource allocation problems are found, for example, in high-tech industries confronted with large-scale and complex production planning problems. We present two algorithms to solve the allocation problem with ordering constraints. The first one uses characterization of the optimal decision variables to apply a search method. The second algorithm solves a sequence of problems, each in the format of the original problem without ordering constraints. Whereas the computational effort of the first algorithm depends on the desired degree of accuracy even for linear performance functions, the effort of the latter algorithm is polynomial for certain classes of performance functions. © 1994 John Wiley & Sons, Inc.