Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.09.005 Byline: K. Spiliopoulos, S. Sofianopoulou Keywords: Computing science; Data cleansing; Shortest path problem; String matching; Levenshtein distance Abstract: Fast detection of string differences is a prerequisite for string clustering problems. An example of such a problem is the identification of duplicate information in the data cleansing stage of the data mining process. The relevant algorithms allow the application of large-scale clustering techniques in order to create clusters of similar strings. The vast majority of comparisons, in such cases, is between very dissimilar strings, therefore methods that perform better at detecting large differences are preferable. This paper presents approaches which comply with this requirement, based on reformulation of the underlying shortest path problem. It is believed that such methods can lead to a family of new algorithms. An upper bound algorithm is presented, as an example, which produces promising results. Author Affiliation: Department of Industrial Management and Technology, University of Piraeus, 80 Karaoli and Dimitriou Street, 185 34 Piraeus, Greece Article History: Received 11 August 2004; Accepted 2 September 2005

A new method for formulating efficient solutions to Cell Formation Problems in Group Technology was presented as an improvement over existing methods based on clustering theory which are constrained by their weakness in formulating exact solutions. The new approach utilizes both the Gilmore-Lawler bound for the Quadratic Assignment Problem and the Rendl-Wolkowicz bound for the Quadratic Transportation Problem. Results show the new method to be an efficient procedure in formulating optimal solutions at low computational cost.

In the presence of alternative routings, the manufacturing cell design involves the solution of a large number of (simple) cell-formation problems. We present a bounding scheme which examines all combinations of alternative routings and solves only a few cell-formation problems, thereby limiting the solution space which is searched heuristically. This leads to increased reliability for the solutions obtained. The resulting algorithm is shown to be applicable for problems arising in practice frequently, when the initial design includes relatively few exceptional elements, and machine duplication and/or genuine multiple process plans are used correctively, to eliminate the remaining intercellular traffic. [ABSTRACT FROM AUTHOR]

This paper proposes a three-stage approach for the manufacturing cells design problem and a tabu search scheme for its solution. The proposed approach is based on the observation that almost all computationally complex aspects can be incorporated in a middle stage optimization model. A preliminary parts grouping stage precedes and a stage eliminating remaining intercellular traffic follows. The tabu search scheme that solves the middle stage problem integrates proper short- and long-term memory structures and an overall search strategy for their use. At the code-development phase, special care has been taken to enhance the explorative capability of the algorithm by correlating search statistics with the values of the search parameters. The resulting algorithm is robust and produces more than promising results with negligible computational effort. In the absence of known optimal solutions for larger dimensions (more than 30 machines), datasets from mathematically similar areas were used. Tests with problems of size up to 50 also give encouraging results. [ABSTRACT FROM AUTHOR]

Determining safety margins for a structure or a component against excessive inelastic deformations is an important issue for engineering design. Direct methods and particularly shakedown analysis constitute a convenient tool towards this direction. Most of the developed approaches in shakedown analysis are based on optimization algorithms. In this paper, a procedure for the shakedown analysis of structures under thermo-mechanical loads is presented. The approach makes use of the recently published Residual Stress Decomposition Method (RSDM) which assumes the decomposition of the residual stress field into Fourier series with respect to time. Starting from a high loading factor, the shakedown limit is estimated through an iterative procedure that updates the Fourier coefficients, reducing at the same time this loading factor until the only remaining term of the Fourier series is the constant term. The method is formulated within the finite element method and is applied to two-dimensional structures under thermal and mechanical cyclic loading. [ABSTRACT FROM AUTHOR]