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     

Scheduling jobs with piecewise linear decreasing processing times

We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP‐hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP‐hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 531–554, 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.     

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.     

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.     

Compound poisson approximation in systems reliability

The compound Poisson “local” formulation of the Stein-Chen method is applied to problems in reliability theory. Bounds for the accuracy of the approximation of the reliability by an appropriate compound Poisson distribution are derived under fairly general conditions, and are applied to consecutive-2 and connected-s systems, and the 2-dimensional consecutive-k-out-ofn system, together with a pipeline model. The approximations are usually better than the Poisson “local” approach would give. © 1996 John Wiley & Sons, Inc.