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     

Scheduling with tool changes to minimize total completion time: A study of heuristics and their performance

The machine scheduling literature does not consider the issue of tool change. The parallel literature on tool management addresses this issue but assumes that the change is due only to part mix. In practice, however, a tool change is caused most frequently by tool wear. That is why we consider here the problem of scheduling a set of jobs on a single CNC machine where the cutting tool is subject to wear; our objective is to minimize the total completion time. We first describe the problem and discuss its peculiarities. After briefly reviewing available theoretical results, we then go on to provide a mixed 0–1 linear programming model for the exact solution of the problem; this is useful in solving problem instances with up to 20 jobs and has been used in our computational study. As our main contribution, we next propose a number of heuristic algorithms based on simple dispatch rules and generic search. We then discuss the results of a computational study where the performance of the various heuristics is tested; we note that the well‐known SPT rule remains good when the tool change time is small but deteriorates as this time increases and further that the proposed algorithms promise significant improvement over the SPT rule. © 2002 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Algorithmic insights and a convergence analysis for a Karmarkar-type of algorithm for linear programming problems

This paper is concerned with a modification of a recently proposed variant of Karmarkar's algorithm for solving linear programming problems. In analyzing this variant, we exhibit interesting and useful relationships of these types of algorithms with barrier function methods, and subgradient optimization procedures involving space dilation techniques, which subsume the well-known ellipsoidal type of algorithms. Convergence of this variant is established under certain regularity conditions. We also provide remarks on how to obtain dual variables or Lagrange multipliers at optimality.     

Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems

Clustering problems are often difficult to solve due to nonlinear cost functions and complicating constraints. Set partitioning formulations can help overcome these challenges, but at the cost of a very large number of variables. Therefore, techniques such as delayed column generation must be used to solve these large integer programs. The underlying pricing problem can suffer from the same challenges (non‐linear cost, complicating constraints) as the original problem, however, making a mathematical programming approach intractable. Motivated by a real‐world problem in printed circuit board (PCB) manufacturing, we develop a search‐based algorithm (Rank‐Cluster‐and‐Prune) as an alternative, present computational results for the PCB problem to demonstrate the tractability of our approach, and identify a broader class of clustering problems for which this approach can be used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Analysis and optimal design of discrete order picking technologies along a line

Order picking accounts for most of the operating expense of a typical distribution center, and thus is often considered the most critical function of a supply chain. In discrete order picking a single worker walks to pick all the items necessary to fulfill a single customer order. Discrete order picking is common not only because of its simplicity and reliability, but also because of its ability to pick orders quickly upon receipt, and thus is commonly used by e‐commerce operations. There are two primary ways to reduce the cost (walking distance required) of the order picking system. First is through the use of technology—conveyor systems and/or the ability to transmit order information to pickers via mobile units. Second is through the design—where best to locate depots (where workers receive pick lists and deposit completed orders) and how best to lay out the product. We build a stochastic model to compare three configurations of different technology requirements: single‐depot, dual‐depot, and no‐depot. For each configuration we explore the optimal design. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Replacing nonidentical vital components to extend system life

We consider a system that depends on a single vital component. If this component fails, the system life will terminate. If the component is replaced before its failure then the system life may be extended; however, there are only a finite number of spare components. In addition, the lifetimes of these spare components are not necessarily identically distributed. We propose a model for scheduling component replacements so as to maximize the expected system survival. We find the counterintuitive result that when comparing components' general lifetime distributions based on stochastic orderings, not even the strongest ordering provides an a priori guarantee of the optimal sequencing of components. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

What you should know about simulation and derivatives

Derivatives (or gradients) are important for both sensitivity analysis and optimization, and in simulation models, these can often be estimated efficiently using various methods other than brute‐force finite differences. This article briefly summarizes the main approaches and discusses areas in which the approaches can most fruitfully be applied: queueing, inventory, and finance. In finance, the focus is on derivatives of another sort. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008