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.     

The long term effects of an aging fleet on operational availability and cost: evidence from the U.S. coast guard

This paper empirically examines whether the aging of a fleet affects operational availability and operating cost using a unique data-set on the 117 47-foot Motor Lifeboats (MLBs) of the United States Coast Guard (USCG). Procured from 1997 to 2003, the 47-foot MLB is the standard lifeboat of the USCG and all 117 MLBs remain in service. The aging of the MLB fleet has resulted in higher annual operating costs and lower operational availability, although the nature of this relationship remains unclear. Our estimation strategy utilizes an error components estimator to examine these issues. We employ three variants of the dependent variables (i.e. the standard logarithmic transformation as is most commonly seen in the literature, inverse hyperbolic sine [IHS], and level outcomes). The point estimates from the standard logarithmic model finds operational availability for the MLBs decreases at a rate between 0.83 and 1.8% per year and cost increases at a rate between 0.33 and 7.81% per year. Similar effects are shown with the IHS and level outcome specifications. In terms of nonlinearity effects, we find the most pronounced changes in operational availability and cost occur for MLBs aged 15 years or more (in comparison to younger MLBs).     

Minimization of expected variance of completion times on single machine for stochastic jobs

This article deals with the problem of scheduling jobs with random processing times on single machine in order to minimize the expected variance of job completion times. Sufficient conditions for the existence of V-shaped optimal sequences are derived separately for general and ordered job processing times. It is shown that when coefficient of variation of random processing times are bounded by a certain value, an optimal sequence is V-shaped. © 1997 John Wiley & Sons, Inc.     

Multiple-facility loading under capacity-based economies of scope

Multiple-facility loading (MFL) involves the allocation of products among a set of finite-capacity facilities. Applications of MFL arise naturally in a variety of production scheduling environments. MFL models typically assume that capacity is consumed as a linear function of products assigned to a facility. Product similarities and differences, however, result in capacity-based economies or diseconomies of scope, and thus the effective capacity of the facility is often a (nonlinear) function of the set of tasks assigned to the facility. This article addresses the multiple-facility loading problem under capacity-based economies (and diseconomies) of scope (MFLS). We formulate MFLS as a nonlinear 0–1 mixed-integer programming problem, and we discuss some useful properties. MFLS generalizes many well-known combinatorial optimization problems, such as the capacitated facility location problem and the generalized assignment problem. We also define a tabu-search heuristic and a branch-and-bound algorithm for MFLS. The tabu-search heuristic alternates between two search phases, a regional search and a diversification search, and offers a novel approach to solution diversification. We also report computational experience with the procedures. In addition to demonstrating MFLS problem tractability, the computational results indicate that the heuristic is an effective tool for obtaining high-quality solutions to MFLS. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 229–256, 1997     

A squared-euclidean distance location-allocation problem

This article is concerned with the analysis of a squared-Euclidean distance location-allocation problem with balanced transportation constraints, where the costs are directly proportional to distances and the amount shipped. The problem is shown to be equivalent to maximizing a convex quadratic function subject to transportation constraints. A branch-and-bound algorithm is developed that utilizes a specialized, tight, linear programming representation to compute strong upper bounds via a Lagrangian relaxation scheme. These bounds are shown to substantially dominate several other upper bounds that are derived using standard techniques as problem size increases. The special structure of the transportation constraints is used to derive a partitioning scheme, and this structure is further exploited to devise suitable logical tests that tighten the bounds implied by the branching restrictions on the transportation flows. The transportation structure is also used to generate additional cut-set inequalities based on a cycle prevention method which preserves a forest graph for any partial solution. Results of the computational experiments, and a discussion on possible extensions, are also presented.     

Setting military reenlistment bonuses

The United States military frequently has difficulty retaining enlisted personnel beyond their initial enlistment. A bonus program within each service, called a Selective Reenlistment Bonus (SRB) program, seeks to enhance reenlistments and thus reduce personnel shortages in critical military occupational specialties (MOSs). The amount of bonus is set by assigning “SRB multipliers” to each MOS. We develop a nonlinear integer program to select multipliers which minimize a function of deviations from desired reenlistment targets. A Lagrangian relaxation of a linearized version of the integer program is used to obtain lower bounds and feasible solutions. The best feasible solution, discovered in a coordinate search of the Lagrangian function, is heuristically improved by apportioning unexpended funds. For large problems a heuristic variable reduction is employed to speed model solution. U.S. Army data and requirements for FY87 yield a 0-1 integer program with 12,992 binary variables and 273 constraints, which is solved within 0.00002% of optimality on an IBM 3033AP in less than 1.7 seconds. More general models with up to 463,000 binary variables are solved, on average, to within 0.009% of optimality in less than 1.8 minutes. The U.S. Marine Corps has used a simpler version of this model since 1986. © 1993 John Wiley & Sons, Inc.     

A parametric-based heuristic program for the quadratic assignment problem

In this article we study the quadratic assignment problem by embedding the actual data in a data space which satisfies an extension of the metric triangle property. This leads to simpler computations for the determination of heuristic solutions. Bounds are given for the loss of optimality which such heuristic solutions would involve in any specific instance. © 1993 John Wiley & Sons, Inc.