The Impact of Emerging Technologies on Computer Science and Operations Research

The emergence of high-performance computers and sophisticated software tech­ nology has led to significant advances in the development and application of operations research. In turn, the growing complexity of operations research models has posed an increasing challenge to computational methodology and computer technology. This volume focuses on recent advances in the fields of Computer Science and Operations Research, on the impact of technologi­ cal innovation on these disciplines, and on the close interaction between them. The papers cover many relevant topics: computational probability; design and analysis of algorithms; graphics; heuristic search and learning; knowledge-based systems; large-scale optimization; logic modeling and computation; modeling languages; parallel computation; simulation; and telecommunications. 1 This volume developed out of a conference held in Williamsburg, Virginia, January 5-7, 1994. It was sponsored by the Computer Science Technical Section of the Operations Research Society of America. The conference was attended by over 120 people from across the United States, and from many other countries. We would like to take this opportunity to thank the participants of the con­ ference, the authors, the anonymous referees, and the publisher for helping produce this volume. We express our special thanks to Bill Stewart and Ed Wasil for serving as Area Editors.

Table of Contents:
1 An Upper Bound Suitable for Parallel Vector Processing for the Objective Function in a Class of Stochastic Optimization Problems.- 1 Introduction.- 2 Design of the Upper Bound.- 3 Concluding Remarks.- References.- 2 On Embedded Languages, Meta-Level Reasoning, and Computer-Aided Modeling.- 1 Introduction.- 2 Meta-Level Reasoning.- 3 Reasoning: Inference and Decoding.- 4 Embedded Languages.- 5 Computer-Aided Modeling.- 6 Discussion and Examples.- References.- 3 Mapping Tasks to Processors to Minimize Communication Time in a Multiprocessor System.- 1 Introduction.- 2 Tabu Search for the Mapping Problem.- 3 Robust Parallel Tabu Search Algorithm.- 4 Computational Results.- 5 Conclusions.- References.- 4 Refinements to the So-Called Simple Approximations for the Bulk-Arrival Queues: MX/G/1.- 1 Introduction.- 2 The Model.- 3 Queueing-Time Distributions.- 4 The Tails of the Queueing-Time Distributions.- 5 Special Cases.- 6 Numerical Results.- 7 Conclusions.- Appendix A.- Appendix B.- References.- 5 A Nearly Asynchronous Parallel Lp-Based Algorithm for the Convex Hull Problem in Multidimensional Space.- 1 Introduction.- 2 Previous LP-based Approaches.- 3 Theoretical Aspects of LP-based Approaches.- 4 A General Approach.- 5 The New LP-based Approach.- 6 Parallel Formulation.- 7 Test Problem Generation.- 8 Computational Results.- 9 Concluding Remarks.- References.- 6 A Dynamically Generated Rapid Response Capacity Planning Model for Semiconductor Fabrication Facilities.- 1 Introduction.- 2 A Brief Review Of Producing Micro-Electronic Chips.- 3 The Required Fact Bases.- 4 Steady State Capacity Analysis Model.- 5 Summary.- Appendix A Decision Tiers.- Appendix B Overview of ROSE.- Appendix C First Small Model.- Appendix D Code To Calculate Reachability Matrix.- Appendix E HandlingVariations Between Tools.- Appendix F Transient Solver.- References.- 7 Queueing Analysis in TK Solver (QTK).- 1 Introduction.- 2 TK and QTK.- 3 Selecting and Working with a QTK Model.- 4 Modifying Existing Models.- References.- 8 On-Line Algorithms for a Single Machine Scheduling Problem.- 1 Introduction.- 2 A single machine scheduling problem.- 3 Analysis of FCFS and SAJF.- 4 A general lower bound.- 5 Computational results.- 6 Conclusions.- References.- 9 Modeling Experience Using Multivariate Statistics.- 1 Introduction.- 2 Expectations.- 3 Constructing Expectations.- 4 An Example.- 5 Conclusions.- References.- 10 Optimal Spare Parts Allocation and Industrial Applications.- 1 Introduction.- 2 Model.- 3 SPARE—an implementation.- 4 Industrial Applications.- References.- 11 A C++ Class Library for Mathematical Programming.- 1 Introduction.- 2 A Small Example Model.- 3 Structure and Use of the Class Library.- 4 Algebraic Notation and Sparse Arrays.- 5 Variable Aliasing.- 6 Extensions.- 7 Conclusion.- References.- 12 Integrating Operations Research and Neural Networks for Vehicle Routing.- 1 Introduction.- 2 A parallel insertion heuristic.- 3 The Initialization Phase.- 4 Computational Results.- 5 Concluding Remarks.- References.- 13 Using Artificial Intelligence to Enhance Model Analysis.- 1 Introduction.- 2 Current Analysis Tools.- 3 Insight System Description.- 4 INSIGHT—A Sample Session.- 5 A Sample Problem.- 6 Results.- 7 Research Directions.- References.- 14 Solving Quadratic Assignment Problems Using the Reverse Elimination Method.- 1 Introduction.- 2 Reverse Elimination Method.- 3 Intensification and Diversification—A Clustering Approach.- 4 Computational Results.- 5 Conclusions.- Appendix A Best Found Solutions.- References.- 15 Neural Networks forHeuristic Selection: An Application in Resource-Constrained Project Scheduling.- 1 Introduction.- 2 Description of Problem and Data.- 3 Data Preprocessing and Representation.- 4 Experimental Design and Results.- 5 Conclusion.- References.