We consider production line design where the information available for equipment under consideration is unreliable, incomplete, or erroneous. We develop an analytic procedure for information gathering, which reduces uncertainty by systematically improving the information critical for overall design performance. We report test results using real design cases from General Motors.

The performance of heuristic algorithms for combinatorial optimization is often sensitive to problem instances. In extreme cases, a specialized heuristic algorithm may perform exceptionally well on a particular set of instances while fail to produce acceptable solutions on others. Such a problem-sensitive nature is most evident in algorithms for combinatorial optimization problems such as job shop scheduling, vehicle routing, and cluster analysis. The paper proposes a formal method for comparing and selecting heuristic algorithms (or equivalently, different settings of a same algorithm) given a desired confidence level and a particular set of problem instances. We formulate this algorithm comparison problem as a stochastic optimization problem. Two approaches for stochastic optimization, ordinal optimization and optimal computing budget allocation are applied to solve this algorithm selection problem. Computational testing on a set of statistical clustering algorithms in the IMSL library is conducted. The results demonstrate that our method can determine the relative performance of heuristic algorithms with high confidence probability while using a small fraction of computer times that conventional methods require.

We propose an adaptable routing scheme for telecommunication networks based on the notion of virtual clustering. Virtual clustering logically reconfigures the network topology in a periodic basis according to the traffic requirements in the network. This temporary topology configuration imposes restrictions on the potential paths between certain groups of source—destination node pairs, thus regulating and balancing the global network traffic while maintaining sufficient local flexibility for real-time routing. The proposed routing scheme can be implemented in an established telecommunication environment where the actual routing of network traffic is conducted by an existing dynamic routing algorithm, while the routing tables are preprocessed by the current virtual clustering configuration. We develop a virtual clustering algorithm using problem space search proposed by Storer, Wu and Vaccari (1992. New Search Spaces for Sequencing Problems with Applications to Job Shop Schedule, Management Science 38, 1495–1509; 1996. Local Search in Problem and Heuristic Space for Job Shop Scheduling, ORSA Journal on Computing 7, 453–465). The algorithm iteratively evaluates clustering solutions and its potential impact to routing performance by perturbation of the traffic requirement matrix. The proposed routing scheme is tested through intensive computational experiments on randomly generated geometric networks, and on PREPNET, a real-world subnetwork on the Internet. Using Monte Carlo simulation, we compare the proposed routing scheme to centralized routing and decentralized asynchronous routing. Computational results show that the proposed approach significantly outperforms these traditional schemes under dynamic traffic fluctuation.

In this paper, we present an approach to weighted tardiness job-shop scheduling problems (JSP) using a graph decomposition technique. Our method decomposes a JSP into a series of sub-problems by solving a variant of the generalized assignment problem which we term "VAP". Given a specified assignment cost, VAP assigns operations to mutually exclusive and exhaustive subsets, identifying a partially specified schedule, Compared to a conventional, completely specified schedule, this partial schedule is more robust to shop disturbances, and therefore more useful for planning and control. We have developed assignment heuristics which iteratively update the problem parameters using lower and upper bounds computed from the corresponding schedule. The heuristics are tested on standard test problems. We show that the proposed approach provides a means for extending traditional scheduling capabilities to a much wider spectrum of shop conditions and production scenarios.

In a recent paper we discussed “problem” and “heuristic” spaces which serve as a basis for local search in job shop scheduling problems. By encoding schedules as heuristic, problem pairs (H,P) search spaces can be defined by perturbing problem data and/or heuristic parameters. In this paper we attempt to determined, through computational testing, how these spaces can be successfully searched. Well known local search strategies are applied in problem and heuristic space and compared to Shifting Bottleneck heuristics, and to probabilistic dispatching methods. An interesting result is the good performance of genetic algorithms in problem space. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.