An exact solution approach for the time-dependent traveling-salesman problem

We present an algorithm for solving the time-dependent traveling-salesman problem (TDTSP), a generalization of the classical traveling salesman problem in which the cost of travel between two cities depends on the distance between the cities and the position of the transition in the tour. The algorithm is derived by applying Benders decomposition to a mixed-integer linear programming formulation for the problem. We identify trivial TDTSPs for which a standard implementation of the algorithm requires an exponential number of iterations to converge. This motivates the development of an efficient, network-flow-based method for finding Pareto-optimal dual solutions of a highly degenerate subproblem. Preliminary computational experience demonstrates that the use of these Pareto-optimal solutions has a dramatic impact on the performance of the algorithm. © 1996 John Wiley & Sons, Inc.     

On the orbit characteristics of the M/G/ 1 retrial queue

In teletraffic applications of retrial queues only the service zone is observable. Another part of a retrial queue, the orbit, which represents the delay before repeated attempts to get service, cannot be observed. Thus, it is very important to get general results about behavior of the orbit. We investigate two characteristics of the orbit, namely, the orbit busy period and the orbit idle period, which seem to be very useful from this point of view. © 1996 John Wiley & Sons, Inc.     

A robust policy for serial agile production systems

One of the major problems in modeling production systems is how to treat the job arrival process. Restrictive assumptions such as Markovian arrivals do not represent real world systems, especially if the arrival process is generated by job departures from upstream workstations. Under these circumstances, cost‐effective policies that are robust with respect to the nature of the arrival process become of interest. In this paper, we focus on minimizing the expected total holding and setup costs in a two‐stage produce‐to‐order production system operated by a cross‐trained worker. We will show that if setup times are insignificant in comparison with processing times, then near‐optimal policies can be generated with very robust performances with respect to the arrival process. We also present conditions under which these near‐optimal policies can be obtained by using only the arrival and service rates. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Note: A geometrical method of solving certain games

One of the diagrammatic methods for solving two-person 2 × n matrix games can be extended to solve m × n games where each column of the matrix is a concave function of the row number. This gives a simple proof of a theorem of Benjamin and Goldman that such games have solutions involving no more than two consecutive strategies for the row player, and no more than two strategies for the column player. Two extensions are discussed. © 1994 John Wiley & Sons, Inc.     

An analytical evaluation of optimal solution value estimation procedures

The estimation of optimal solution values for large-scale optimization problems is studied. Optimal solution value estimators provide information about the deviation between the optimal solution and the heuristic solution. Some estimation techniques combine heuristic solutions with randomly generated solutions. In particular, we examine a class of jacknife-based estimators which incorporate any heuristic solution value with the two best randomly generated solution values. The primary contribution of this article is that we provide a framework to analytically evaluate a class of optimal solution value estimators. We present closed-form results on the relationship of heuristic performance, sample size, and the estimation errors for the case where the feasible solutions are uniformly distributed. In addition, we show how to compute the estimation errors for distributions other than uniform given a specific sample size. We use a triangular and an exponential distribution as examples of other distributions. A second major contribution of this article is that, to a large extent, our analytical results confirm previous computational results. In particular, the best estimator depends on how good the heuristic is, but seems to be independent of the underlying distribution of solution values. Furthermore, there is essentially an inverse relationship between the heuristic performance and the performance of any estimator. © 1994 John Wiley & Sons, Inc.     

Optimizing the allocation of components to kits in small-lot,multiechelon assembly systems

The kitting problem in multiechelon assembly systems is to allocate on-hand stock and anticipated future deliveries to kits so that cost is minimized. This article structures the kitting problem and describes several preprocessing methods that are effective in refining the formulation. The model is resolved using an optimizing approach based on Lagrangian relaxation, which yields a separable problem that decomposes into a subproblem for each job. The resulting subproblems are resolved using a specialized dynamic programming algorithm, and computational efficiency is enhanced by dominance properties devised for that purpose. The Lagrangian problem is resolved effectively using subgradient optimization and a specialized branching method incorporated in the branch-and-bound procedure. Computational experience demonstrates that the specialized approach outperforms the general-purpose optimizer OSL. The new solution approach facilitates time-managed flow control, prescribing kitting decisions that promote cost-effective performance to schedule. © 1994 John Wiley & Sons. Inc.     

Localization of optimal strategies in certain games

Assume the payoffs of a matrix game are concave in the index of the maximizing player. That player is shown to have an optimal strategy which uses at most two consecutive pure strategies, identifiable through approximate solution of a related continuous game. Generalizations are given, and the results are applied to a motivating hidden-target model due to Shapley. © 1994 John Wiley & Sons, Inc.