Dominant graphs for rectilinear network design with barriers

Given a set of points on a Cartesian plane and the coordinate axes, the rectilinear network design problem is to find a network, with arcs parallel to either one of the axes, that minimizes the fixed and the variable costs of interactions between a specified set of pairs of points. We show that, even in the presence of arbitrary barriers, an optimal solution to the problem (when feasible) is contained in a grid graph defined by the set of given points and the barriers. This converts the spatial problem to a combinatorial problem. Finally we show connections between the rectilinear network design problem and a number of well-known problems. Thus this paper unifies the known dominating set results for these problems and extends the results to the case with barriers.     

Heuristics for the plate-cutting traveling salesman problem

In this paper we present a new problem that arises when parts are cut from large plates of metal or glass. We call this problem the plate-cutting traveling salesman problem (P-TSP) because it requires the determination of a minimum-length tour such that exactly one point must be visited on each of a number of given polygons. We present a mathematical formulation of the problem and show that the problem is a variation of the well-known traveling salesman problem. We examine the problem when the order in which parts are to be cut is known. For this problem we present a Lagrangean decomposition of the problem and develop lower bounds and heuristics based on this decomposition. Computational testing on problems with 5-40 polygons reveals that the heuristics give fairly good solutions. When the order in which polygons are to be cut is known, the heuristic solutions are within 3-4% of the optimal. The decomposition-based heuristics are embedded in a variable r-opt heuristic for the overall problem.     

Lot sizing problems with strong set-up interactions

We address the problem of coordinated replenishment of products when the products can be produced only in fixed proportion to each other. Such problems commonly arise in the manufacture of sheet/plate metal parts or die-cast parts. The problem is a variant of the well-known Joint Replenishment Problem. We call this problem the Strong Interaction Problem (SIP). After giving a mathematical formulation of the problem, we show that the general problem is NP-hard. An important variant of the problem, in which products are unique to a family, is shown to be polynomially solvable. We present several lower bounds, an exact algorithm and a heuristic for the problem. Computational testing on randomly generated problems suggests that our exact algorithm performs very well when compared with a commercially available integer programming solver. The heuristic method also gives good solutions.     

Design of loading policies for a high-performance computer system

We use a systematic simulation study of computer-system loading policies to design a loading policy for a high-performance system. Our results illustrate the performance advantages of 'round-robin' disciplines, the interference caused by finite memory, and how this interference can be mitigated by using carefully selected loading policies that exploit information about job resource requirements. Our choice of performance measures allows us to assess response-time predictability and fairness as well as overall efficiency. Using the insights obtained from our study, we introduce a new type of policy, the NEST policy, which is structured to employ the principles of good scheduling, while avoiding shortcomings of commonly used approaches.