| Title, Authors: | Abstract: |
| ORP02-04 A
Note on Distance Matrices Yielding Elementary Landscapes for the TSP J.W. Barnes, Andrew Solomon, Steftcho Dokov, and Raul Acevedo |
Symmetric and antisymmetric distance matrices in the single agent traveling salesman problem (TSP) are not the only distance matrices to generate elementary landscapes for "swap" and "2-opt" neighborhoods. |
| ORP02-03 Weakly
Symmetric Graphs, Elementary Landscapes and the TSP J.W. Barnes, Andrew Solomon, Steftcho Dokov, and Raul Acevedo |
Weakly symmetric graphs are defined and their construction from symmetric graphs is explained. It is shown that the TSP on a weakly symmetric graph joined with each of a number of well known local search neighborhoods yields elementary landscapes (in which local minima are better than the average). In conclusion an O(n2) algorithm for identifying weakly symmetric graphs as described. |
| ORP02-02 Extending
Elementary Landscape Characterizations For Combinatorial Optimization Problems
To Arbitrary Neighborhoods Definitions J.W. Barnes, Andrew Solomon, Steftcho Dokov, and Boryana Dimova |
Certain classes of combinatorial optimization problems (COPs), given appropriate neighborhood definitions, satisfy Grover's difference equation, (Grover 1992). Such COPSs embody an elementary landscape, i.e., a union of a neighborhood, solution space and objective function, that has several favorable properties for heuristic search. Stadler (1996) developed an equivalent characterization of such elementary landscapes using the neighborhood graph Laplacian. In both Grover's and Stadler's work, the neighborhood definitions were restricted to adjacency matrices that were both symmetric and regualr. We use a normalized graph Laplacian to significantly extend the scope of elementary landscapes to arbitrary neighborhood definitions and to introduce a new type of elementary landscape. |
| ORP02-01 Weakly-Antisymmetric
Elementary Landscapes for the Travelling Salesman Problem J.W. Barnes, Raul Acevedo, and Steftcho Dokov |
We characterize the weakly-antisymmetric distance matrices. When used with a variety of common neighborhoods, this class of asymmetric matrices yield elementary landscapes for the travelling salesman problem (TSP). Any weakly-antisymmetric distance matrix may be expressed as the sum of an antisymmetric TSP distance matrix and a constant TSP distance matrix. The weakly-antisymmetric TSP distance matrices are characterized by a set of 3-tuple conditions. |
| ORP01-03 *Stability
and Instability of a Two-Station Queueing Network: The Exponential Case J.W. Barnes, Raul Acevedo, and Steftcho Dokov |
This paper, together with a companion paper [11], proves that the stability region of a 2-station, 5 -class re-entrant queueing network, operating under a non-preemptive static buffer priority service policy, depends on the distributions of the interarrival and service times. In particular, our result shows that conditions on the mean interarrival and service times are not enough to determine the stability of a queueing network. In this paper, we prove that when all distributions are exponential, the network is unstable in the sense that, with probability one, the total number of jobs in the network goes to infinity with time. In the caompanion paper, we show that, among other things, the same network with all interarrival and service times being deterministic is stable. |
| ORP00-05*A Step-by-Step
User's Guide to Implementing the Group Class in Java Victor D. Wiley |
This is a user guide intended to be a step-by-step instruction of how to create a group using the Java based Group class definition as implemented by Victor Wiley. This guide will demonstrate each step of the process using the Symmetric Group on n letters (Sn) as an illustration. The methods defined for Sn during the step-by-step instructions are meant to be the minimal set of necessary methods and are not intended to restrict the user from creating other useful methods. For additional methods that have successfully been applied to Sn, refer to the SymmetricGroup User's manuel. |
| ORP00-04*The SymmetricGroup Class User's Manual for Partitioning and Ordering ProblemsDownload associated Java archiveVictor D. Wiley | The Symmetric Group on n letters structure allows it to easily represent partitioning and ordering problems. This manual is intended to provide details of how the SymmetricGroup class has been derived and how it can be used. |
| ORP00-03*A Simple Relation Between Multiplicative Moves and ConjugationJ. Wesley Barnes, Raul Acevedo | We study the fundamental relation between conjugation and right (left) multiplication of permutations. In the general context of neighborhood search for an incumbent solution, we emphasize the uniqueness of the multiplicative move in cntrast to the non-uniqueness of the conjugative move. A formal closed relationship is given and discussed for the general case on n - cycles. Some examples of low dimensionality are presented for purposes of explanation. |
| ORP00-02*Group Theory and Transition Matrices for Conjugative Move Disciplines in Multiple TSP's with Known Solution StructureJ. Wesley Barnes, Bruce Colletti, and David Neuway | This paper expands and extends the earlier work of Barnes, Colletti, and Neuway (2000). The earlier paper introduced the use of transition matrices to study the one-step conjugative rearrangement neighborhoods of all possible incumbent tours in an n-city, single-agent Traveling Salesperson Problem. Such transition matrices fall into three different types: (1) irreducible matrices of period 2 with two equal-sized closed essential classes. We begin with a complete recounting of this work followed by an extension to multi-agent TSP's using neighborhoods that maintain the cycle structure of the solution space. We conclude by discussing ideas for future investigation. |
| ORP97-08*An Enhanced TSP-Based Heuristic for Makespan Minimization
in a Flow Shop with Setup TimesRoger Z. RÌos-Mercado (roger@hpc.uh.edu),
Jonathan F. Bard |
This paper presents an enhanced heuristic for minimizing the makespan of the flow shop scheduling problem with sequence-dependent setup times. The procedure transforms an instance of the problem into an instance of the traveling salesman problem by introducing a cost function that penalizes for both large setup times and bad fitness of schedule. This hybrid cost function is an improvement over earlier approaches that penalized for setup times only, ignoring the flow shop apsect of the problem. To establish good parameter values, each component of the heuristic was evaluated computationally over a wide range of problems instnaces. In the testing stage, an experimental comparison with a greedy randomized adaptive search procedure revealed the conditions and data attributes where the proposed procedure works best. |
| ORP97-07*Bayesian Maintenance Policies During a Warranty PeriodTa-Mou Chen, Elmira Popova | Most of the brand new items are released on the market with a certain type of warranty. A fixed length warranty period is assumed in this paper. A maintenance policy which consists of minimal repair and preventive maintenance is analyzed for the case of known and unkown failure parameters of the item's lifetime distribution. For the second case, two types of Bayesian policies are considered. An extensive simulatin study comparing the performance of these maintenance policies is performed. |
| ORP97- 06*Characterizing the k-OPT Neighborhood Via Group TheoryBruce W. Colletti, J. W. Barnes, Stefcho Dokov | Group theory can be used to model and synthesize the neighborhood of Traveling Salesman tours reachable through k-OPT exchanges. A primary concept is that a dihedral group action partitions the sets of cut arcs so that k-OPT exchanges of orbital elements are conjugate. Also presented is a method to produce all k-OPT exchanges for a given set of cut arcs. |
| ORP97-05Component Positioning Problem Under Demand and Capacity Uncertainty In Printed Circuit Board AssemblyWei-LiangLin, Valerie Tardif | In this paper, we focus on the problem of selecting position for the components on a PCB assembly line so as to minimize the time taken to satisfy demand for boards during a production period. We assume that the problem is solved once at the baginning of the production period and all different boards are processed without changes in the component positioning. In addition, demand is rarely known at design time. Therefore, we asume that demand is unknown prior to the beginning of the production period but follows a probability distribution captured by different demand scenarios and associated probabilities. This leads us to a stochastic mixed-integer programming formulation. We then propose different methods and heuristics to solve this problem. Even though only small- or moderate-sized problems can be solved to optimality within a timely fashion, we present two heuristic colution methods which are computationally faster andyeild very good solutions. We compare and contrast them within a computational study. |
| ORP97-04Adaptive Single-Stage Pull Control SystemsValerie Tardif, Lars Maaseidvaag | This paper introduces a new adaptive kanban-type pull control mechanism which determines when to release or reorder raw parts based on customer demands and inventory levels. This system differs from the traditional kanban sytem in that the number of kanban cards is allowed to change with respect to the inventory level and number of backorders. However, the number of cards in the system remains limited, thereby restricting the amount of work-in-process in the system. In this paper, we show how to determine the initial number of cards and dynamically readjust this number to match current operating conditions and improve performance. We show that this adaptive system can outperform the traditional kanban pull control mechanism while remaining easy to implenent and understand. We present simulation results and show the benefits of this system under variable demand and lead times. |
| ORP97-03*A Product-Mix Capacity Planning ModelMatthew Stafford (mstafford@tri.sbc.com) | In the semiconductor industry, capacity planning decisions need to take uncertain demand into account. Machines for wafer fabrication plants must be ordered more than a year in advance of their delivery and set-up. It is difficult to accurately forecast the product mix that plants will be required to manufacture this far in advance. This motivates the incorporation of uncertainty into traditional optimization approaches. The product-mix problem fits well into the paradigm of two-stage stochastic optimization models, which were developed for this purpose and have been successfully used in the steel, electric power and finance industries. To illustrate what stochastic optimization techniques have to offer the semiconductor industry, we develop a small model and analyze the results of a sampling-based solution approach of Morton and Woods. |
| ORP97 -02Computational Experience with a Branch-and-Cut Algorithm for Flowhop Scheduling with SetupsRoger Z. RÌos-Mercado (roger@hpc.uh.edu), Jonathan F. Bard | This paper presents a branch-and-cut (B&C) algorithm for the problem of minimizing the makespan associated with scheduling n jobs in an m-machine flowshop with setup times (SDST flowshop). Two different mathematoca; formulations are considered. Model A is based on a traveling salesman problem-like formulation. Model B uses fewer binary variables and constraints, but is less structured than model A. A number of valid inequalities, including facet-inducing inequalities, for these two different formulations are evaluated. It was found that the B&C approach outperforms conventional branch and bound. With respect to coputational effort, model B proved superior. |
| ORP97-01A Branch-and-Bound Algorithm for Flowshop Scheduling with Setup Times.Roger Z. RÌos-Mercado (roger@hpc.uh.edu), Jonathan F. Bard | This paper presents a branch-and-bound enumeration scheme for the makespan minimization of the flowshop scheduling problem with setup times. The algorithm includes the implementation of both lower and upper bounding procedures, a dominance elimination criterion,m and special features such as a partial enumeration strategy. A computational evaluation of the overall scheme demonstrates the effectiveness of each component. Test results are provided for a wide range of problem instances |