On solving facility layout problems using genetic algorithms

Tam and Chan (1998) present a parallel genetic algorithm approach to solve the facility layout problem. They adopt a slicing tree representation of a floor layout. The coding scheme represents a layout as a string with three parts. This paper demonstrates the difficulties in applying classical crossover and mutation operators for solving facility layout problems. The paper modifies the representation of Tam and Chan and introduces a new preserving operation, referred to as transplanting , that manages to produce feasible offspring. It also studies the applicability of other genetic operations such as diagonal crossover and cloning in generating feasible offspring. The paper is written in a note format and the reader may refer to Tam and Chan for more details.     

FLEXPERT: facility layout expert system using fuzzy linguistic relationship codes

Linguistic variables, fuzzy statements and fuzzy algorithms, from the theory of fuzzy sets, provide suitable tools to solve ill-defined problems. Unlike conventional techniques that deal only with discrete conditions, like 'on' and 'off', and precise numerical values, fuzzy logic offers an alternate technique that deals with non-discrete conditions, such as 'absolutely important', 'quite important' and 'less important'. This paper presents a new approach, based on the theory of fuzzy logic, to solve the facility layout problem. The proposed approach considers the multicriteria nature of the layout problem and the fuzziness of the input data through the integration of an expert system and a fuzzy algorithm with a facility layout program. The system generates the best layout that satisfies die qualitative as well as the quantitative constraints on the layout problem. This facilitates the incorporation of the knowledge of facility layout experts. A knowledge-based system, named FLEXPERT, has been developed to implement the new approach.     

Heuristic approach for solving the multi-objective facility layout problem

A new heuristic approach for the generation of preferred objective weights to solve the multi-objective facility layout problem is presented. By applying a multi-pass halving and doubling procedure, a paired comparison method based on the strength of preference among objectives given by the decision-maker is developed. Furthermore, a ‘prior test’ is proposed to examine the consistency of the paired comparison matrix. An efficient method to transform the inconsistent matrix into a consistent one so the result can closely approximate the decision-maker's original assessments is also offered. The geometric mean method is then employed to obtain the objective weights and the final solution. There are five phases in the proposed heuristic approach. The first generates a basic solution; the second involves constructing a paired comparison matrix by using the multi-pass halving and doubling procedure; the third identifies the consistency of the paired comparison matrix; the fourth transforms the inconsistent matrix into a consistent one; and the fifth generates the preferred weights and obtains the facility layout solution. An illustrative example is given to demonstrate an application of the proposed approach for solving the multi-objective facility layout problem.     

Development of a knowledge-based expert system for solving metal cutting problems

In metal cutting, the problems need to be well analyzed in order to take precautions before any unexpected results are encountered. This process plays a significant role in achieving consistent quality and in controlling the overall cost of manufacturing. However, it is a difficult task that needs an expert who has a great deal of information and experience in metal cutting. In the present paper, a knowledge-based expert system (COROSolve) that investigates problems that are encountered in three main metal cutting areas: turning, milling and drilling is developed. A great deal of metal cutting operations such as external/internal turning with negative/positive inserts, aluminum turning, parting bars/tubes, grooving, profiling, recessing and threading operations in turning; face milling, square shoulder milling, end milling, multi-purpose milling and side and face milling operations in milling; and drilling operations that use solid drills or drills with indexable inserts in drilling are taken into consideration. COROSolve gives recommendations for the cutting data (i.e., cutting speed, depth of cut, and feed) and updates the problem, cause and remedy database, thus the number of problems that the system can handle is increased.     

Preprocessing for static and dynamic facility layout problems

Most facility layout problems have departments with unequal areas and have significant rearrangement costs. This paper describes a model and improved algorithm which simultaneously handles these parameters. An existing algorithm solves the dynamic facilities layout problem while permitting the departments to have unequal areas. One part of the algorithm solves a mixed integer programming problem to find the desired block diagram layout. This large, complex problem could only be solved optimally for small problems. Therefore a preprocessing method was developed to prespecify certain obvious department pair orientations, which had previously required binary variables. The method uses estimated location, department sizes, and flow costs to determine the probable variable values. Then, a revised branch and bound strategy solves for the less obvious department pair orientations. Test results show a significant cost reduction on a variety of previously published problems, and feasible solutions to previously unsolved problems. The algorithm found a layout solution to the standard . CRAFT problem which has 10 5% lower costs than the previously best published layout.     

Visual facility layout design system

This paper presents an integrated visual facility layout design system to solve layout problems with geometric constraints on a continual planar site. The system employs a tabu search algorithm as the search engine with heuristic neighbourhood control and a manual interference mechanism to obtain good solutions. The Windows®-based system provides layout designers with a friendly environment that can automatically search a good solution aided by the visual inspection function. The visual inspection function is a mechanism embedded in the search process that dynamically displays the improvement status and allows manual adjustment of facility location during the search. The system also serves as a powerful tool for performing 'what if' analyses for layout designers.     

An iterative facility layout algorithm

In this paper we present a facility layout algorithm that iterates between a genetic algorithm with a slicing tree representation and a mixed-integer program with a subset of the binary variables set via the genetic algorithm. The genetic algorithm is very good at finding low-cost solutions while maintaining shape constraints on the departments. The slicing tree representation and the mixed-integer program are compatible in terms of layout representation, with the mixed-integer program representation more general. The mixed-integer program allows us to relax the last remaining constraints of the slicing tree representation of the genetic algorithm. We present our genetic algorithm and the iterative algorithm, while illustrating their performance on test problems from the literature. In 10 of the 12 problems, new lower best-cost solutions are found.     

An improved facility layout construction method

This study presents a new distance-based facility layout construction technique. Given a two-dimensional (i.e. single-floor) facility layout construction problem in which the order of placement of individual departments is known (a challenging problem in itself), the technique presented herein proposes the use of sub-departments and expected distance functions instead of centroid-to-centroid distances for the placement of departments. In this paper an expected distance function is defined as the probabilistic expectation of the particular distance metric of interest (rectilinear, Euclidean, etc.) in which the parameters involved are defined by random vectors in 2-dimensional Euclidean space. This study presents an enhanced facility layout construction technique that incorporates several enhancements over the well-known systematic layout procedure (SLP). The goal herein is to minimise the error induced by the use of the centroid-to-centroid distances between the departments inherent to the SLP.     

An extended distance-based facility layout problem

The distance-based facility layout problem with unequal-area departments has been studied by many researchers for over 30 years. Still, current approaches require certain assumptions that limit the type of solutions obtained. In this paper, we consider manufacturing systems in which replicates of the same machine type may exist in the facility, and propose an extended distance-based facility layout problem that concurrently determines the number and shape of the departments, the assignment of machines to departments, and the allocation of part flow volume to individual machines. A non-linear mixed-integer program that accurately captures the extended facility layout and part flow allocation problem, a decomposition approach that exploits the structure of the formulation using a heuristic solution procedure, as well as computational results that evaluate the proposed approach, are presented.     

Solution of facility layout problems with pickup/drop-off locations using random search techniques

Due to non-polynomial hardness, the facility layout problem (FLP) becomes more critical when pickup/drop-off (P/D) locations are considered in the design of an open field layout under a manufacturing environment. This paper proposes an indigenous model of the facility layout problem based on random search techniques and its solution methodology using a genetic algorithm (GA), simulated annealing (SA) and a hybrid algorithm (HA). The paper illustrates the performance of different random search operating parameters in solving the facility layout problem considering P/D locations along the periphery of rectangular machine blocks. The preliminary experiments were carried out on three facility layout test problems having six, eight and ten machines in order to fix the different operating parameters such as crossover operator, crossover rate, initial temperature, temperature reduction factor, number of generations, population size, etc. The results of extensive preliminary experimentation were utilized to solve facility layout problems having 12 and 18 machines and, finally, were compared with the existing procedures in the literature. The experimental tables and related analysis performed via the solution methods by applying GA, SA and HA revealed that random-search-based modeling of FLP considering P/D and its solution as suggested in this paper is worth pursuing.     

An application of an expert system in layout compaction of VLSI design

Abstract

Recent research in knowledge‐based expert systems of VLSI design tools has concentrated on placement, routing, and cell generation. This paper presents an alternative application for artificial intelligence (AI) techniques on compaction design for a VLSI mask layout‐expert compactor. In order to overcome the shortcomings of iterative search through a large problem space within a working memory, and therefore, to speed‐up the runtime of compaction, a set of rule‐based region query operations and knowledge‐based techniques for the plane sweep method are proposed in this system. Experimental results have explored the possibility of using expert system technology (EST) to automate the compaction process by “reasoning” out the layout design and applying sophisticated expert rules to its knowledge base.     

An interactive approach to computer aided facility layout

In all manufacturing and service industries the layout of facilities is an important determinant of operating efficiency and costs. Whenever the flow of materials or people is complex, computerized procedures offer the only feasible means of developing and evaluating alternative arrangements.

This paper describes an interactive approach to construction and improvement procedures which utilizes a refresh graphics terminal (IMLAC)linked to a PRIME 400 computer. Input includes projected materials flow, estimates of material handling costs, 2-D templates of machines, etc., and an initial layout which can be either existing, proposed, or constructed using the procedure INLAYT. A heuristic procedure, S-ZAKY, utilizes multi-pairwise facility exchange to develop improved layouts based upon an analysis of materials flow. The improved layout is displayed in detail alongside the initial layout at the graphics terminal together with relevant material handling costs. The user may then accept, reject or modify the improved layout using the light-pen attached to the terminal before proceeding to successive iterations until satisfied. An economic evaluation of the projected savings in material handling costs against costs of relayout may be displayed at each iteration. On completion, a fully documented record including drawings may be obtained for every stage in the. procedure.     

A genetic algorithm for facility layout

Facility layout is an important aspect of designing any manufacturing setup. However, the problem of finding optimal layouts is hard and deterministic techniques are not computationally feasible. In this work a genetic algorithm is presented for obtaining efficient layouts. The different aspects involved in the design of efficient genetic algorithms are discussed in detail. It is shown that the population maintained by the genetic algorithm for facility layout should consist of feasible solutions only. A new efficient crossover operator is developed. Experimental results obtained with the proposed algorithm on test problems taken from the literature are promising.     

An experimental comparison of systematic placement procedures for facility layout design

A comparison of alternative procedures for automatic placement of facilities in a layout is presented. Various placement procedures are reviewed, incorporated in an existing ‘construction’ type heuristic and evaluated in terms of placement computation time, satisfaction of goals expressed using linguistic patterns, fulfilment of desired adjacency of facilities and regularity of shapes of facilities in resulting layouts. An experiment illustrates the application of various placement procedures fora set of randomly generated and known layout problems to compare the performance of alternative placement procedures.     

An improved algorithm for solving a multi-period facility location problem

This note develops a pruning rule for a previously published multi-period facility location algorithm. This rule can be used to reduce the number of candidate single period location configurations to be examined. An important feature of the proposed rule is that very little additional computation is required in order to apply it. The rule is illustrated using one of the examples in the previously published paper. Finally an experiment is also conducted to examine the effectiveness of the proposed rule under different conditions.     

An improved algorithm for solving a multi-period facility location problem

An exact algorithm for the multi-period facility location problem is proposed that efficiently integrates mixed-integer and dynamic programming methods. Two simplification procedures are introduced to reduce the size of the general multi-period facility location problem substantially. Because the proposed algorithm utilizes dynamic programming to obtain the optimal sequence over the entire planning horizon, many near-optimal solutions also become available that are extremely useful for postoptimality analysis. The solution method is tested and compared with a well-known procedure on several problems with varying conditions. The comparisons appear very promising, and the required CPU times by the proposed method are substantially reduced.     

An improved procedure for solving transient heat conduction problems using the boundary element method

In employing the boundary element method to solve transient heat conduction problems, domain integrals need to be calculated. These integrals can be calculated either by directly discretizing the domain, or indirectly by utilizing a time-marching scheme which requires the time integrations to be evaluated from the initial time. Although the second approach overcomes the need for domain discretization, it has the disadvantage of requiring large storage and CPU time for increasing number of time steps. This paper is concerned with a procedure which approximates the domain integrals without the need for domain discretization. The time-marching scheme is employed so that the domain integrals can be calculated at a particular time with a known weighting and temperature distribution. These integrals can then be utilized to approximate similar domain integrals with a different weighting. It is shown that the method proposed dramatically reduces the storage requirements and CPU time, even for a small number of time divisions.     

An expert system for network management control

Abstract

Due to the varying time and the complexity of the commercial telecommunication network configuration, routing of the communication traffic becomes very important for telecommunication systems. No one can keep in mind all the complex routing plans used in networks, so it is hard to quickly take proper actions while the switching node is being blocked.

In this paper, we propose an expert system which can collect traffic data, monitor network status, reason and take appropriate actions for extreme traffic congestion on a network just as a network management expert can do. It would certainly streamline the whole network control procedure, and. provide dynamic routing functions based on the original static routing method adopted in Taiwan. It does improve both network efficiency and network reliability.     

Data input model for virtual reality-aided facility layout

An approach to automatically extract three dimensional (3D) models (that is, geometries and topologies) of physical objects in a facility is described. The rationale for this work is its repeated use in efficiently developing databases of 3D objects for applying virtual reality (VR) tools in detailed layout decision support. Obtaining 3D object models can be a challenging task. Sometimes they are available, for example, in a Computer-Aided Design (CAD) database and these can be readily imported into a VR database. But on many occasions one is not so fortunate and these object models have to be created in correlation to an existing or proposed facility, which can be an extremely tedious and time consuming task. A time efficient and economical alternative is to use video camera images, but quickly and accurately capturing the depth information from 2D camera images has so far remained elusive because the existing methodologies are too general purpose and operate at a lower level of abstraction, namely digitized images. We have developed a method for directly inputting 3D objects into VR-aided facility layout models, by integrating the strengths of previously tried and tested technological components: (i) camera calibration; (ii) image processing; (iii) stereo vision; and (iv) Delaunay triangulation. The techniques described here are embedded in a prototype architecture and toolkit called MIRRORS (Methodology for Inputting Raw Recordings into 3D Object Renderings for Stereo). The primary contribution of this paper is that it has been able to design an integrated system to build 3D object models from 2D images. The MIRRORS system has been primarily designed for objects without free-form surfaces and whose shape can be recovered from a relatively nondense set of points.