Tesis sobre el tema "Facility Layout Problem( FLP)"

In today’s dynamic environment, where product demands are highly volatile and unstable, the ability to design and operate manufacturing facilities that are robust with respect to uncertainty and variability is becoming increasingly important to the success of any manufacturing firm in order to operate effectively in such an environment. Hence manufacturing facilities must be able to exhibit high levels of robustness and stability in order to deal with changing market demands. In general, Facility Layout Problem (FLP) is concerned with the allocation of the departments or machines in a facility with an objective to minimize the total material handling cost (MHC) of moving the required materials between pairs of departments. Most FLP approaches assume the flow between departments is deterministic, certain and constant over the entire time planning horizon. Changes in product demand and product mix in a dynamic environment invalidate these assumptions. Therefore there is a need for stochastic FLP approaches that aim to assess the impact of uncertainty and accommodate any possible changes in future product demands.This research focuses on stochastic FLP with an objective to present a methodology in the form of a framework that allows the layout designer to incorporate uncertainty in product demands into the design of a facility. In order to accomplish this objective, a measure of impact of this uncertainty is required. Two solution methods for single and multi period stochastic FLPs are presented to quantify the impact of product demand uncertainty to facility layout designs in terms of robustness (MHC) and variability (standard deviation). In the first method, a hybrid (simulation) approach which considers the development of a simulation model and integration of this model with the VIPPLANOPT 2006 algorithm is presented. In the second method, mathematical formulations of analytic robust and stable indices are developed along with the use of VIPPLANOPT for solution procedure. Several case studies are developed along with numerical examples and case studies from the literature are used to demonstrate the proposed methodology and the application of the two methods to address different aspects of stochastic FLP both analytically and via the simulation method. Through experimentation, the proposed framework with solution approaches has proven to be effective in evaluating the robustness and stability of facility layout designs with practical assumptions such as deletion and expansion of departments in a stochastic environment and in applying the analysis results of the analytic and simulation indices to reduce the impact of errors and make better decisions

This dissertation develops efficient solution techniques for general and problem-specific applications within nonconvex optimization, exploiting the constructs of the Reformulation-Linearization Technique (RLT). We begin by developing a technique to enhance general problems in nonconvex optimization through the use of a new class of RLT cuts, called semidefinite cuts. While these cuts are valid for any general problem for which RLT is applicable, we demonstrate their effectiveness in optimizing a nonconvex quadratic objective function over a simplex. Computational results indicate that on average, the semidefinite cuts have reduced the number of nodes in the branch-and-bound tree by a factor of 37.6, while decreasing solution time by a factor of 3.4. The semidefinite cuts have also led to a significant reduction in the optimality gap at termination, in some cases producing optimal solutions for problems that could not be solved using RLT alone. We then narrow our focus to the class of mixed-integer programming (MIP) problems, and develop a modification of Bendersâ decomposition method using concepts from RLT and lift-and-project cuts. This method is particularly motivated by the class of two-stage stochastic programs with integer recourse. The key idea is to design an RLT or lift-and-project cutting plane scheme for solving the subproblems where the cuts generated have right-hand sides that are functions of the first-stage variables. An illustrative example is provided to elucidate the proposed approach. The focus is on developing a first comprehensive finitely convergent extension of Bendersâ methodology for problems having 0-1 mixed-integer subproblems. We next address a specific challenging MIP application known as the facility layout problem, and we significantly improve its formulation through outer-linearization techniques and concepts from disjunctive programming. The enhancements produce a substantial increase in the accuracy of the layout produced, while at the same time, providing a dramatic reduction in computational effort. Overall, the maximum error in department size was reduced from about 6% to nearly zero, while solution time decreased by a factor of 110. Previously unsolved test problems from the literature that had defied even approximate solution methods have been solved to exact optimality using our proposed approach.
Ph. D.

The facilities layout problem, which is an integral part of facilities design, aims to spatially locate the production units within a facility subject to some design criteria and area limitations, with one or multiple objectives. In this study, the layout problem is reviewed in detail, with an emphasis on the dynamic environment it operates in. Despite the fact that layouts within the context of changing manufacturing requirements represent the problem better, the single period block layout problem is observed to have remained worth analyzing. In this thesis, a hybrid model that combines the strong aspects of the available models in the literature is constructed for the single period block layout problem. The LP relaxation of this model and the effect of adding valid inequalities to the model are studied. A rounding heuristic based on the LP relaxation of the problem is proposed and computational experimentation is made. Also, an evolutionary algorithm scheme that uses the sequence pair representation is proposed. Three mutation operators are developed to be used in this scheme. Preliminary test are made for implementations of these operators and results are given.

Thesis (M.S.)--West Virginia University, 2001.
Title from document title page. Document formatted into pages; contains x, 133 p. : ill. Includes abstract. Includes bibliographical references (p. 88-94).

Thesis (M.S.)--West Virginia University, 2002.
Title from document title page. Document formatted into pages; contains vii, 76 p. : ill. Includes abstract. Includes bibliographical references (p. 72-76).

Thesis (M.S.)--West Virginia University, 2005.
Title from document title page. Document formatted into pages; contains vii, 88 p. : ill. Includes abstract. Includes bibliographical references (p. 83-88).

The facility layout design problem is concerned with determining the arrangement and configuration of facilities, which optimizes a prescribed objective such as profit, cost, or distance, and which satisfies various prescribed constraints pertaining to available resources. In industry, facility layout design problems arise in manufacturing, in warehousing, and in various assignment type situations. The solution of these problems impacts on the viability of the industry. For example, material-handling costs which can comprise between 30 and 75% of the total manufacturing costs, can be reduced by using the optimization methods associated with the facility layout design. In the service industries, facility layout design problems arise in the location of emergency facilities (such as ambulance, fire stations) and in the allocation of space. The solution of these location problems impacts on the well being of the community. Mathematically, the facility layout problem has been modelled as: a quadratic assignment problem, a quadratic set covering problem, a linear integer programming problem, a mixed integer programming problem, and a graph theoretic problem. The problem has been shown to be NP-complete. This computational difficulty has led researchers to consider suboptimal solutions generated by heuristic approaches. There are a number of heuristic procedures that have been proposed for solving the facility layout design problem, including Simulated Annealing, Tabu Search, Expert Systems, and Graph Theoretic Algorithms. The most successful heuristic approaches are based on graph theoretic concepts. In this thesis we focus our study on constructive graph theoretic based heuristics for determining an optimal arrangement and configuration of facilities with the objective of maximizing the total benefit.
We are particularly interested in constructive heuristics, which can produce a maximum-weighted planar graph as a final solution. Our contribution is the development, implementation, and testing of three new algorithms. Computational results, based on 4200 randomly (uniform and normal distribution) generated problems, demonstrate the value of our methods. We also present the performance of each algorithm when various initial solutions are applied. Chapter 1 provides the background of the facility layout design, including the notation, terminology and general concepts as well as a summary of the thesis. Chapter 2 provides a comprehensive survey of the facility layout design problem. This includes models and methods of solution based on exact algorithms (including the branch and bound method and the cutting plane method), as well as heuristic algorithms. We detail the main constructive graph theoretic based heuristics in the literature: the Deltahedron Method, the Green-Al Hakim Algorithm, the Leung’s Constructive Heuristic, the Kim-Kim Algorithm, the Wheel Expansion Method, TESSA and the String Processing Algorithm. We also briefly discuss the non-graph theoretic heuristics including simulated annealing, tabu search, and expert systems. In Chapter 3 we present three new graph theoretic based heuristics. These heuristics are constructive and the solution is built up, starting with an initial layout of four facilities, by an insertion process. Our algorithms have two important features. Firstly, they allow for previously chosen edges to be removed at each insertion step. Secondly, they do not restrict the type of maximal planar graph produced. Computational results and a comparative analysis of the main graph theoretic based heuristics are provided. The analysis is based on 4200 randomly generated test problems (from uniform and normal distribution).
The test problems consist of 30 data sets with the number of facilities ranging from 5 to 100 in increments of 5. Chapter 4 is devoted to the performance of graph theoretic based heuristics when different types of initial solutions are applied. Examples show that the final solution is sensitive to the initial solution. Computational results indicate that for most algorithms, the best type of initial solution is the selection of four facilities which yield the best objective function value contribution. However, this does not always coincide with that proposed in the original description of the algorithms. We conclude this thesis by discussing some future research that can be carried out on the facility layout design problem, particularly in graph theoretic based heuristics.

In this thesis, we study both dynamic and distributed facility layout problems, where the demand for product mix changes over time. We propose a new simulated annealing algorithm, SALAB, for the dynamic facility layout problem. Four variants of SALAB find the best known solution for 20 of the 48 benchmark problems from the literature, improving upon the best known solutions of 18 problems. We modify SALAB to obtain DSALAB, solving the dynamic distributed facility layout problem with the objective of minimizing relocation cost and total (full and empty) travel cost of the material handling system. We simulate DSALAB solutions of randomly generated problems to study the tradeoff between total cost and congestion in the system. Our experimental results indicate that distributing the department duplicates throughout the facility reduces the total cost with diminishing returns and causes increasing congestion. Therefore, distribution beyond a certain level is not justified.

Thesis (Ph. D.)--West Virginia University, 2008.
Title from document title page. Document formatted into pages; contains xiii, 109 p. : ill. (some col.). Includes abstract. Includes bibliographical references (p. 97-103).

L'agencement d'espace est un problème courant dans la plupart des secteurs industriels. Ce problème est de nature continue et discret et il est considéré comme un problème NP-difficile. Les méthodes d'optimisation traditionnelles, plus appropriées pour une recherche locale sont difficilement utilisables aux problèmes d'agencement. Afin de contourner ces limitations inhérentes aux méthodes classiques, nous proposons deux algorithmes adaptés aux problèmes d'agencement statique de composants de différentes tailles. Pour les problèmes d'agencement considérés, les fonctions objectives à minimiser sont non linéaires et représentent les coûts associés aux sommes pondérées des distances entre les composants. La première approche que nous considérons est une méthode hybride en deux étapes. La première étape consiste à construire un agencement en se basant sur la méthode dite "bas-gauche" comme une solution locale. Ensuite, la solution obtenue est améliorée en appliquant un algorithme génétique modifié. Les opérateurs de croisement et de mutation sont alors adaptés pour prendre en compte les spécificités du problème d'agencement. La deuxième approche est une combinaison entre une recherche locale et globale. Dans ce cas, l'algorithme génétique est également modifié par l'introduction d'un opérateur spécialisé pour le traitement des rotations des composants. Il permet notamment d'éviter le couplage entre les variables réelles et entières et permet également de réduire considérablement le nombre de variables du problème d'optimisation. Les performances des deux approches sont testées et comparées avec les exemples de référence extraits des publications traitant du problème d'optimisation d'agencement. Nous démontrons que les deux approches que nous proposons obtiennent de meilleures performances que les approches existantes
A facility layout design is one of the most commonly faced problems in the manufacturing sectors. The problem is mixed-integer in nature and usually an NP-hard problem, which makes it difficult to solve using classical optimization techniques, which are better for local search. To overcome these limitations, two algorithms have been proposed for solving static facility layout problems with the unequal size compartments. The objective function of the problems considered is nonlinear in which the sum of the material handling cost has been minimized. In the first approach, a hybrid constructive and improvement model has been proposed where an advanced bottom-left fill technique was used as constructive approach. The constructive model proposed also acts as a local search method based on greedy algorithm. For improvement approach a hybrid genetic algorithm has been proposed, where the crossover and mutation operator are specially designed to handle the solution representation which itself is used as constructive model. In the second approach, a combined local and global search model was proposed where a rotation operator was used to avoid mixed-integer formulation of the problem. Use of rotation operator has also reduced the number of variables significantly. Apart from the conventional evolutionary operators this model has also used exchange and rotation operators. The performances of both model are tested over a previously solved problem selected from the literature. The evaluation of the results shows that the performances of the proposed models are better than many existing algorithms and has the potential for field applications

Dans les dernières décennies, l'augmentation de la consommation des services de soins et la croissance de la population ont fait de l'élimination du gaspillage et l'amélioration continue de la productivité de plus en plus cruciale pour les hôpitaux. La productivité et l'efficacité d'un hôpital dépendent des conditions de travail des soignants qui sont influencés fortement par l'organisation des lieux de travail et des installations [Dares (2013)]. L’agencement des installations consiste à "déterminer l'organisation physique d'un système de production et de trouver l’arrangement le plus efficace de ‘n’ installations dans ‘n’ positions" [Singh et Sharma (2006)]. L’agencement des installations a un grand impact sur la productivité et l'efficacité du fonctionnement d'un hôpital. Etant conscient de ce besoin, le travail que nous présentons vise à trouver une solution à l’agencement des salles du Bloc Opératoire "le coeur de l'hôpital", ainsi que les salles annexes en proposant un outil intelligent que nous mettons à la disposition des maitres d’ouvrages pour optimiser leur conception du bloc opératoire. Les méthodes que nous avons explorées pour la réalisation de ce travail sont les méthodes exactes, les heuristiques, les métaheuristiques et les méthodes intelligentes, ce qui nous a permis de comparer les différentes approches afin de fournir la meilleure solution pour différents scénarios de problèmes. Nous présentons les contributions majeures de notre travail, à commencer par l'application de la programmation mathématique en nombres entiers mixtes (Mixed Integer Programming (MIP)) pour résoudre le problème d’agencement du bloc opératoire (Operating Theater Layout Problem (OTLP)) comme la première contribution scientifique. Ce travail considère trois structures différentes (multi-section, multi-étage et multi-rangé) dans deux types d'environnement différents, tout en optimisant deux fonctions objectifs différents. La combinaison de ces différentes composantes donne lieu à neuf modèles MIP pour résoudre l’OTLP pour lesquels une solution optimale a été atteinte pour des problèmes avec jusqu'à quarante salles. L'utilisation de Systèmes Multi-Agents (MAS) pour résoudre le problème d’agencement des installations est la deuxième contribution scientifique que nous présentons dans le cinquième chapitre. Dans la littérature, on retrouve un seul travail [Tarkesh et al., (2009)] ayant appliqué le MAS pour résoudre des problèmes de petites tailles, ce qui rend notre travail, le premier adoptant MAS pour répondre à la fois le FLP sous environnement statique et dynamique pour des problèmes de grande taille en utilisant un algorithme en trois étapes pour résoudre OTLP. La plate-forme multi-agents développée exploite les trois différents protocoles de communication d’agents, à savoir la coordination, la coopération et la négociation pour concevoir différentes architectures d’agents afin de faire face à l’OTLP statique et dynamique. La dernière contribution consistant en l'utilisation de l’optimisation par essaim de particules (Particle Swarm Optimization (PSO)) sous une représentation continue de l’espace de recherche pour résoudre le problème d’agencement multi-rangée est présentée dans le sixième chapitre. Puisque la PSO est généralement utilisé pour résoudre les problèmes d’affectation ou les FLP avec une représentation discrète, la formulation actuelle est parmi les rares travaux traitant la représentation continue du FLP. Nous avons conçu une nouvelle technique de codage des particules et des heuristiques appropriées pour générer des solutions initiales et pour effectuer la procédure de recherche locale. Une autre nouveauté est liée à l'application de la PSO à un problème de structure multi-rangé, qui n'a pas été abordé auparavant car à notre connaissance, les travaux avec la PSO ont formulé le FLP comme une structure d’une seule rangée ou dans le meilleur des scénarios, comme une structure à deux rangées
In the last decades, the important increasing consumption of health care and the growing of population make elimination of waste and continuous productivity improvement more and more critical for hospitals to provide their care services effectively and efficiently. The productivity and efficiency of a hospital depends on the caregivers working conditions, which are impacted greatly by the work place and the facilities organization [Dares (2013)]. Facilities planning “determines the physical organization of a production system and finding the most efficient arrangement of ‘n’ indivisible facilities in ‘n’ locations” [Singh & Sharma (2006)]. Thus, facilities planning has a great impact on the productivity and efficiency of running a hospital. Being aware of this need, the work we present aims to find a solution to facilities planning for the Operating Theater “the heart of hospital” by proposing an intelligent tool we make available to decision makers for optimizing their operating theater design. Our research work focuses on the use of operational research methods in order to find a solution for this optimization problem. Methods we explored for the realization of this work were variant, namely exact algorithm, heuristics, metaheuristics and intelligent methods, which allow us to compare different issues in order to provide the best solution to different scenarios of problems. Thus, in this dissertation we present the major contribution of our work, starting with the application of Mixed Integer Programming (MIP) to solve Operating Theater Layout Problem (OTLP) as the first scientific contribution. This work considers three different formulations (i.e. the multi-sections, the multi-floors and the multi-rows) in two different environment types (i.e. static and dynamic) while optimizing two different objective functions (i.e. to minimize the total traveling cost and to maximize the total adjacency rate). The combination of these different components gives rise to nine MIP models to solve the OTLP for which optimal solution was provided to problems with until forty facilities. These contributions are presented in the third and fourth chapters. The use of Multi-Agent System (MAS) to solve Facility Layout Problem (FLP) is the second scientific contribution we present in chapter five. In literature, only one work [Tarkesh et al., (2009)] applied the MAS to solve small sized problems, which makes our work the first one adopting MAS to address both the static and dynamic FLP for large sized problems using a novel algorithm running in three steps to solve OTLP. The developed multi-agent platform exploit the three different agents’ protocols of communication, namely coordination, cooperation and negotiation to conceive different agents’ architectures to deal with the static and dynamic OTLP. The last contribution consisting on the use of Particle Swarm Optimization (PSO) under continuous layout representation to solve multi-rows FLP is presented in chapter six. Since the PSO is generally used to solve assignment problems or discrete FLP, the actual formulation is among the few works dealing with the continuous one. This leads us to conceive a novel encoding technique and the appropriate heuristics to generate initial solutions and to perform the local search procedure. Another novelty is related to the application of PSO to a multi-rows layout problem, which was not addressed before. To the best of our knowledge, PSO works usually formulate the FLP as a single row or in the best of scenarios, as a double-rows problem

The facility layout problem (FLP) is one of the most important and challenging problems in both the operations research and industrial engineering research domains. In FLP research, the continuous-representation-based FLP can consider all possible all-rectangular department solutions. Given this flexibility, this representation has become the representation of-choice in FLP research. Much of this research is based on a methodology of mixed integer programming (MIP) models. However, these MIP-FLP models can only solve problems with a limited number of departments to optimality due to a large number of binary variables used in the models to prevent departments from overlapping. Our research centers around the sequence-pair representation, a concept that originated in the Very Large Scale Integration (VLSI) design literature. We show that an exhaustive search of the sequence-pair solution space will result in finding the optimal layout of the MIP-FLP and that every sequence-pair solution is binary-feasible in the MIP-FLP. Based on this fact, we propose a methodology that combines the sequence-pair and MIP-FLP model to efficiently solve large continuous-representation-based FLPs. Our heuristic approach searches the sequence-pair solution space and then use the sequence-pair representation to simplify and solve the MIPFLP model. Based on this methodology, we systematically study the different aspects of the FLP throughout this dissertation. As the first contribution of this dissertation, we present a genetic algorithm based heuristic, SEQUENCE, that combines the sequence-pair representation and the most recent MIPFLP model to solve the all-rectangular-department continuous-representation-based FLP. Numerical experiments based on different sized test problems from both the literature and industrial applications are provided and the solutions are compared with both the optimal solutions and the solutions from other heuristics to show the effectiveness and efficiency of our heuristic. For eleven data sets from the literature, we provide solutions better than those previously found. For the FLP with fixed departments, many sequence-pairs become infeasible with respect to the fixed department location and dimension restrictions. As our second contribution, to address this difficulty, we present a repair operator to filter the infeasible sequence-pairs with respect to the fixed departments. This repair operator is integrated into SEQUENCE to solve the FLP with fixed departments more efficiently. The effectiveness of combining SEQUENCE and the repair operator for solving the FLP with fixed departments is illustrated through a series of numerical experiments where the SEQUENCE solutions are compared with other heuristics' solutions. The third contribution of this dissertation is to formulate and solve the FLP with an existing aisle structure (FLPAL). In many industrial layout designs, the existing aisle structure must be taken into account. However, there is very little research that has been conducted in this area. We extend our research to further address the FLPAL. We first present an MIP model for the FLPAL (MIP-FLPAL) and run numerical experiments to test the performance of the MIP-FLPAL. These experiments illustrate that the MIP-FLPAL can only solve very limited sized FLPAL problems. Therefore, we present a genetic algorithm based heuristic, SEQUENCE-AL, to combine the sequence-pair representation and MIP-FLPAL to solve larger-sized FLPAL problems. Different sized data sets are solved by SEQUENCE-AL and the solutions are compared with both the optimal solutions and other heuristics' solutions to show the effectiveness of SEQUENCE-AL. The fourth contribution of this dissertation is to formulate and solve the FLP with non-rectangular-shaped departments. Most FLP research focuses on layout design with all rectangular-shaped departments, while in industry there are many FLP applications with non-rectangular-shaped departments. We extend our research to solve the FLP with nonrectangular-shaped departments. We first formulate the FLP with non-rectangular-shaped departments (FLPNR) to a MIP model (MIP-FLPNR), where each non-rectangular department is partitioned into rectangular-shaped sub-departments and the sub-departments from the same department are connected according to the department's orientation. The effect of different factors on the performance of the MIP-FLPNR is explored through a series of numerical tests, which also shows that MIP-FLPNR can only solve limited-sized FLPNR problems. To solve larger-sized FLPNR problems, we present a genetic algorithm based heuristic, SEQUENCE-NR, along with two repair operators based on the mathematical properties of the MIP-FLPNR to solve the larger-sized FLPNR. A series of numerical tests are conducted on SEQUENCE-NR to compare the SEQUENCE-NR solutions with both the optimal solutions and another heuristic's solutions to illustrate the effectiveness of SEQUENCE-NR. As the first systematic research study on a methodology that combines the sequence-pair representation and the MIP-based FLP, this dissertation addresses different types of continuous-representation based facility layout design problems: from block layout design with and without fixed departments to re-layout design with an existing aisle structure, and from layout design with all-rectangular-shaped departments to layout design with arbitrary non-rectangular-shaped departments. For each type of layout design problem, numerical experiments are conducted to illustrate the effectiveness of our specifically designed family of sequence-pair and MIP-based heuristics. As a result, better solutions than those previously found are provided for some widely used data sets from the literature and some new datasets based on both the literature and industrial applications are proposed for the first time. Furthermore, future research that continues to combine the sequence-pair representation and the MIP-FLP model to solve the FLP is also discussed, indicating the richness of this research domain.
Ph. D.

[EN] The Facilities Layout Problem in a industrial plant (FLP) pursues the good ordenation of the integrating elements (that in this work they will call themselves facilities, understan-ding those elements of the production system that they require space) of a production system and it contemplates, among other, geometric and economic aspects. The eco-nomic aspect has to do with the installation of the plant and with its operation while the geometric one is related with the architecture of the system. Under consideration of these aspects they are derived different formulations of the problem according to the geometric model adopted for represent the solution and according to the function to optimize that can include quantitative terms as installation costs and operation cost (manu-tención) and qualitative terms derived of the chart establishing relationship of activities from the met-hodology SLP. Certain tradition exists in the Educational Unit of Buildings and Architectu-re Industrial (at the moment U.D of Industrial Buldings), on the resolution of this FLP from diverse focuses, what there is origin that already from the years 90, myself, author of this thesis, as well as other partners, let us have implemented some computer applications of several types for the resolution of the same, based, by way of example, in genetic algo-rithms or in fuzzy logic. The last one goal was this one implemented with ACO ("Ant Co-lony Optimization") that this work shows. Anyway, this applications, often used in other works or even with educational ends, they have provided satisfactory results so much in the investigating scheduling as in the academic. At the beginning of the 2000, when the normative of Industrial Buldings Fire Proofing appears, when being starting from then of a preceptive normative in the greater part of industries of new installation, and the position that was continued in the real works was: in a first phase the elaboration of the layout, while in a second phase the application of the preceptive normative of fire proofing was demanded against fires to the layout obtained previously, with obligatory character so much in the industrial field, like in the subsidiary uses that aren't industrials, different from the main one. Any layout that it doesn't complete the fire proofing normative approaches in all the areas, be these industrial or not, it lacks legal validity and therefore it's not viable. In a third phase it is endowed of the thermal appropriate atmosphere, higroscopic, acous-tic and lighting to the obtained solution. In front of this reality, more and more commenda-ble starting from the appearance of the Technical Code of Buildings, that impels the per-formance designing and not in prescriptions, of the non convenience of unlying the design phases, we have started including the approach of the compartmentalization in the design like another objective in the quality of the final adopted solution, and therefore optimizable like any another. Hence in this work we have been carried out a proposal of compart-mentalization algorithm that works starting from the information and approaches that the normative of fires use, and we have also defined a proposal of objective function, as well as a series of parameters that allows to consider like it influences this compartmentaliza-tion in the flow of materials through the different facilities.
[ES] El problema de la distribución en planta de procesos industriales (FLP) persigue la ordenación óptima de los elementos (que en este trabajo se llamarán actividades, conceptuándose como aquellos elementos del sistema de producción que requieren espacio) de un sistema de producción y contempla, entre otros, aspectos geométricos y económicos. El aspecto económico tiene que ver con la instalación de la planta y con su operación mientras que el geométrico se relaciona con la arquitectura del sistema. De la consideración de estos aspectos se derivan diferentes formulaciones del problema según el modelo geométrico adoptado para representar la solución y según la función a optimizar, que puede incluir términos cuantitativos como costes de instalación y de operación (manutención) y términos cualitativos derivados de la tabla relacional de actividades establecida desde la metodología SLP. Existe cierta tradición en la Unidad Docente de Construcción y Arquitectura Industrial (actualmente U.D de Construcciones Industriales), sobre la resolución de este problema de distribución en planta desde diversos enfoques, lo que ha originado que ya desde los años 90, yo mismo, autor de esta Tesis Doctoral, así como otros compañeros, hayamos implementado algunas aplicaciones informáticas de varios tipos para la resolución del mismo, basadas, a modo de ejemplo, en algoritmos genéticos o en lógica borrosa. El último caso el de la aplicación informática que utiliza ACO ("Ant Colony Optimization") que se presenta en este trabajo. En cualquier caso, dichas aplicaciones, a menudo utilizadas en otras investigaciones o incluso con fines docentes, han proporcionado resultados satisfactorios tanto en el plano investigador como en el académico. A principios de los 2000, cuando aparece la normativa de Protección Contra Incendios en Establecimientos Industriales, al tratarse a partir de entonces de una normativa de obligado cumplimiento en la gran mayoría de actividades de nueva planta, y el planteamiento que se siguió al realizar los trabajos y proyectos sobre casos reales fue en una primera fase la elaboración de la distribución en planta, mientras que en una segunda fase se exigía la aplicación de la normativa de protección contra incendios a la distribución en planta obtenida con anterioridad, con carácter obligatorio tanto en el ámbito industrial, como en los usos subsidiaros no industriales diferentes del principal. Cualquier distribución en planta que no cumpla los criterios normativos en todas las zonas, sean éstas industriales o no, carece de validez legal y por tanto no es viable. En una tercera fase se dota del adecuado ambiente térmico, higroscópico, acústico y lumínico a la solución obtenida. Frente a esta realidad, cada vez más plausible a partir de la entrada en vigor del Código Técnico de la edificación, que impulsa el diseño basado en prestaciones y no en prescripciones, de la no conveniencia de desligar las fases de diseño, se ha comenzado por incluir el criterio de la sectorización en el diseño como un objetivo más mesurable en la calidad de la solución final adoptada, y por lo tanto optimizable como cualquier otro. Por ello en este trabajo se ha realizado una propuesta de algoritmo de sectorización, que funciona a partir de la información y criterios que las normativas de incendios utilizan, y se ha definido también una propuesta de función objetivo, así como una serie de parámetros que permiten considerar cómo influye esta sectorización en el trasiego de materiales (fundamentalmente flujos) a través de las distintas actividades.
[CAT] El problema de la distribució en planta de processos industrials (FLP) perseguix l'ordena-ció òptima dels elements (que en este treball es cridaran activitats, conceptuant-se com aquells elements del sistema de producció que requerixen espai) d'un sistema de pro-ducció i contempla, entre altres, aspectes geomètrics i econòmics. L'aspecte econòmic té a veure amb la instal·lació de la planta i amb la seua operació mentres que el geo-mètric es relaciona amb l'arquitectura del sistema. De la consideració d'estos aspectes es deriven diferents formulacions del problema segons el model geomètric adoptat per a representar la solució i segons la funció a optimitzar, que pot incloure termes quantitatius com a costos d'instal·lació i d'operació (manutenció) i termes qualitatius derivats de la taula relacional d'activitats establida des de la metodologia SLP. Hi ha una certa tradició en la Unitat Docent de Construcció i Arquitectura Industrial (actualment U.D de Cons-truccions Industrials) , sobre la resolució d'este problema de distribució en planta des de diversos enfocaments, la qual cosa ha originat que ja des dels anys 90, jo mateix, autor d'esta tesi, així com altres companys, hàgem implementat algunes aplicacions informàti-ques de diversos tipus per a la resolució del mateix, basades, a manera d'exemple, en algoritmes genètics o en lògica borrosa. L'últim cas el de l'aplicació informàtica que uti-litza ACO ("Ant Colony Optimization") que es presenta en este treball. En tot cas, les dites aplicacions, sovint utilitzades en altres investigacions o inclús amb fins docents, han pro-porcionat resultats satisfactoris tant en el pla investigador com en l'acadèmic. A principis dels 2000, quan apareix la normativa de Protecció Contra Incendis en Establiments In-dustrials, al tractar-se a partir de llavors d'una normativa de compliment obligatori en la gran majoria d'activitats de nova planta, i el plantejament que es va seguir en els treballs i projectes reials va ser en una primera fase l'elaboració de la distribució en planta, men-tres que en una segona fase s'exigia l'aplicació de la normativa de protecció contra in-cendis a la distribució en planta obtinguda amb anterioritat, amb caràcter obligatori tant en l'àmbit industrial, com en els usos subsidiar-vos no industrials diferents del principal. Qualsevol distribució en planta que no complisca els criteris normatius en totes les zones, siguen ést. En una tercera fase es dota de l'adequat ambient tèrmic, higroscòpic, acústic i lumínic a la solució obtinguda. Enfront d'esta realitat, cada vegada més plausible a partir de l'entrada en vigor del Codi Tècnic de l'Edificació, que impulsa el disseny basat en prestacions i no en prescripcions, de la no conveniència de deslligar les fases de disseny, s'ha començat per incloure el criteri de la sectorització en el disseny com un objectiu més mesurable en la qualitat de la solució final adoptada, i per tant optimizable com qualsevol altre. Per això en este treball s'ha realitzat una proposta d'algoritme de sectorització, que funciona a partir de la informació i criteris que les normatives d'incendis utilitzen, i s'ha definit també una proposta de funció objectiu, així com una sèrie de paràmetres que permeten considerar com influïx esta sectorització en el trasbals de materials (fonamen-talment fluxos) a través de les distintes activitats.
Jaén Gómez, PI. (2015). Algoritmos híbridos para la resolución del F.L.P. (Facility Layout Problem) basados en colonias de hormigas [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/59447
TESIS

In this dissertation, we address three different combinatorial optimization problems (COPs), each of which has specific real-life applications. Owning to their specific nature, these problems are different from those discussed in the literature. For each of these problems, we present a mathematical programming formulation, analyze the problem to determine its useful, inherent structural properties, and develop an efficient methodology for its solution by exploiting these properties. The first problem that we address is the course timetabling problem encountered at Virginia Tech. The course timetabling problem for a university is a difficult problem and has been studied by many researchers over the years. As a result, a plethora of models and approaches have been reported in the literature. However, most of these studies have focused on applications pertaining to course scheduling for a single or at most few departments of a university. The sheer size of the university-wide timetabling problem that we address, involving thousands of courses to be scheduled in hundreds of classrooms in each semester, makes it a challenging problem. We employ an appropriate decomposition technique that relies on some inherent structural properties of the problem both during the modeling and algorithmic development phases. We show the superiority of the schedules generated by our methodology over those that are currently being used. Also, our methodology requires only a reasonable amount of computational time in solving this large-size problem. A facility layout problem involving arbitrary-shaped departments is the second problem that we investigate in this dissertation. We designate this problem as the arbitrary-shaped facility layout problem (ASFLP). The ASFLP deals with arranging a given set of departments (facilities, workstations, machines) within the confines of a given floor space, in order to optimize a desired metric, which invariably relates to the material handling cost. The topic of facility planning has been addressed rather extensively in the literature. However, a major limitation of most of the work reported in the literature is that they assume the shape of a department to be a rectangle (or even a square). The approach that relies on approximating an arbitrary-shaped department by a rectangle might result in an unattractive solution. The key research questions for the ASFLP are: (1) how to accurately model the arbitrary-shaped departments, and (2) how to effectively and efficiently determine the desired layout. We present a mixed-integer programming model that maintains the arbitrary shapes of the departments. We use a meta-heuristic to solve the large-size instances of the ASFLP in a reasonable amount of time. The third problem that we investigate is a supply chain scheduling problem. This problem involves two stages of a supply chain, specifically, a manufacturer and one or more customers. The key issue is to achieve an appropriate coordination between the production and distribution functions of the manufacturer so as to minimize the sum of the shipping and job tardiness costs. We, first, address a single customer problem, and then, extend our analysis to the case of multiple customers. For the single-customer problem, we present a polynomial-time algorithm to solve it to optimality. For the multiple-customer problem, we prove that this problem is NP-hard and solve it by appropriately decomposing it into subproblems, one of which is solvable in polynomial time. We propose a branch-and-bound-based methodology for this problem that exploits its structural properties. Results of an extensive computational experimentation are presented that show the following: (1) our algorithms are efficient to use and effective to implement; and (2) significant benefits accrue as a result of integrating the production and distribution functions.
Ph. D.

En el proceso de diseño e las construcciones industriales, es de vital importancia conocer cual es la ubicación óptima de las diferentes áras de trabajo que conforman un proceso de fabricación, así como de las instalaciones y servicios auxiliares. El problema de distribución en planta (Facilities Layout Problem, FLP) integra a todas las actividades industriales y se ha convertido desde los años 60 en uno de los problemas clásicos de optimización combinatoria, en el que trabajan multiutd de investigadores a nivel internacional. Hasta los años 90, el enfoque que se realizaba del problema era básicamente un enfoque monobjetivo, en el que se primaba fundamentalmente la minimización del coste de transporte de material o personas entre las diferentes áreas productivas o de servicios. Para ello se han venido empleando diferentes técnicas de optimización heurística, que persiguen minimizar el tiempo de cálculo y facilitar la búsqueda de mínimos, aunque sean locales, pues el espacio de soluciones es tan grande, que es difícil garantizar la existencia de un mínimo global del problema. No obstante, el criterio de coste no es el único que se debe considerar en este tipo de planteamientos, pues existen otra serie de indicadores que son de vital importancia, para garantizar que la solución propuesta tiene un nivel de desarrollo tecnológico con la aparición de equipos y programas informáticos más desarrollados, han prosperado las aproximaciones multiobjetivos al problema de distribución en planta. Entre los objetivos principales del presente trabajo se encuentran; la realización de un estado del arte de los indicadores que se han empleado en la bibliografía para la resolución en planta, obteniendo un conjunto de indicadores independientes y suficientes que puedan ser empleados en la obtención de distribuciones en planta óptimas. Se investigará si es necesario definir algún nuevo indicador que cubra los objetivos fundamentales de la distribución en planta establecidos por distintos autores. Una vez seleccionados los indicadores se propone una técnica de optimización multiobjetivo basada en un algoritmo de recocido simulado (Simulated Annealing). Finalmente se presentan los resultados de los experimentos realizados, empleando la técnica de optimización multiobjetivo propuesta, sobre un problema ampliamente utilizado en la bibliografía, el propuesto por Armour y Buffa de 20 actividades. Se obtienen las fronteras de Pareto para diferentes bicriterios, introduciendo puntos que completan las existentes hasta la actualidad, estudiando la posibilidad de extender la optimización a 3 indicadores.
Montalva Subirats, JM. (2011). Optimización multiobjetivo de la distribución en planta de procesos industriales. Estudio de objetivos [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/11147
Palancia

Pour faire face à la concurrence, les entreprises cherchent à améliorer leurs performances industrielles. L’une des solutions à ce défi réside dans la détermination de la meilleure configuration des ateliers de production. Ce type de problème est connu en anglais par Facility Layout Problem « FLP». Dans ce contexte, notre travail propose une méthodologie pour la définition de la configuration d’atelier à travers une approche réaliste. Plus précisément, notre objectif est de prendre en compte les distances réelles parcourues par les pièces dans l’atelier et des contraintes liées au système qui n’ont pas encore été intégrées aux modèles proposés dans la littérature. Pour ce faire, notre première contribution scientifique consiste à développer une nouvelle méthodologie qui utilise l’algorithme A* pour identifier les distances les plus courtes entre les postes de travail de manière réaliste. La méthodologie proposée combine l’Algorithme Génétique (AG) et l’algorithme A* afin d’explorer des espaces de solutions. Pour se rapprocher de plus en plus des cas réels, notre deuxième contribution consiste à présenter une nouvelle formulation généralisée du FLP initialement étudié, en tenant compte de différentes formes et de dimensions des équipements ainsi que de l’atelier. Les résultats obtenus prouvent l’applicabilité et la faisabilité de cette approche dans diverses situations. Une étude comparative de l’approche proposée avec les essaims particulaires intégrés avec A* a prouvé la qualité de la première approche en terme de coût de transport. Finalement, notre troisième contribution consiste à traiter le FLP dans un espace 3D où des contraintes spatiales sont intégrées dans la phase de modélisation. La résolution est une extension de la méthodologie proposée pour le problème 2D, qui intègre donc l'algorithme A* et l’AG afin de générer diverses configurations dans l’espace 3D. Pour chacune de ces contributions, une analyse de sensibilité des différents paramètres d’AG utilisés a été faite à l’aide de simulations de Monte Carlo
To face the competition, companies seek to improve their industrial performance. One of the solutions to this challenge lies in determining the best configuration of the production workshops. This type of problem is known in English by Facility Layout Problem "FLP". In this context, our work proposes a methodology for the definition of the workshop configuration through a realistic approach. More precisely, our goal is to take into account the actual distances traveled by the parts in the workshop and system-related constraints that have not yet been incorporated into the models proposed in the literature. To do this, our first scientific contribution is to develop a new methodology that uses the A* algorithm to identify the shortest distances between workstations in a realistic way. The proposed methodology combines the Genetic Algorithm (GA) and the algorithm A* to explore solution spaces. To get closer to real cases, our second contribution is to present a new generalized formulation of FLP initially studied, taking into account different shapes and dimensions of the equipment and the workshop. The results obtained prove the applicability and the feasibility of this approach in various situations. A comparative study of the proposed approach with particle swarms integrated with A * proved the quality of the first approach in terms of transport cost. Finally, our third contribution is to treat the FLP in a 3D space where spatial constraints are integrated into the modeling phase. The resolution is an extension of the proposed methodology for the 2D problem, which therefore integrates the A * algorithm and the AG to generate various configurations in the 3D space. For each of these contributions, a sensitivity analysis of the different AG parameters used was made using Monte Carlo simulations

碩士
元智大學
工業工程與管理學系
90
Abstract The facility layout problem is to optimize the relative location of the departments with the minimum cost of either material handling or interactive cost. The effective layout of the facilities is one of the keys to the success of the production system for the poor layout and design will cost more and deteriorate the operational efficiency. Past researches were mostly focused on the quantitative measures (e.g., material handling cost), while few were concerned about the qualitative measures (e.g., adjacent closeness). This purpose of this research was to study the facility layout problem based on the adjacency closeness measure. For the qualitative factor, this study focuses on the department closeness measure and utilize the space-filling curve to generate the layout. The proposed approach can help the designer with another choice other than the traditional cost based measures. The results show that this proposed model can obtain better solution in both Total Closeness Rating (TCR) and Weighted Closeness Rating (WCR) than the traditional approaches.

碩士
國立交通大學
工業工程研究所
83
The result of facility layout will influence the performance of production system and is the key factor of deciding production cost. This paper presents a multi-objective facility layout model for combining quantitative factor (material handling cost) and qualitative factor (closeness rating). In this model, closeness rating is weighted by a cost parameter in order to reduce the influence of difference between two objective functions, and let the quality of individual objective be close each other. During the programming procedure, consider changes in production level, this is "flexibility" of facility layout. In this paper, we use lost cost to measure the flexibility of a layout. The lower the lost cost is, the more flexible the layout is. Finally, this paper presents a two-phase algorithm to solve the flexible facility layout problem. In phase one, CRAFT is ployed to obtained the suboptimal layout for each period. Using these suboptimal layouts, the lost cost of each period can be caculated. In phase two, the most flexible layout during planning horizon can obtained by using simulated annealing algorithm.

The continuous facility layout problem consists of arranging a set of facilities so that no pair overlaps and the total sum of the pairwise connection costs (proportional to the center-to-center rectilinear distance) is minimized. This thesis presents a completely mixed integer semidefinite programming (MISDP) model for the continuous facility layout problem. To begin we describe the problem in detail; discuss the conditions required for a feasible layout; and define quaternary variables. These variables are the basis of the MISDP model. We prove that the model is an exact formulation and a distinction is made between the constraints that semidefinite programming (SDP) optimization software can solve and those that must be relaxed. The latter are called exactness constraints and three possible exactness constraints are shown to be equivalent. The main contribution of this thesis is the theoretical development of a MISDP model that is based on quaternary, as oppose to binary, variables; nevertheless preliminary computational results will be presented for problems with 5 to 20 facilities. The optimal solution is found for problems with 5 and 6 facilities, confirming the validity of the model; and the potential of the model is revealed as a new upper bound is found for an 11-facility problem.

碩士
朝陽大學
營建工程系碩士班
88
Construction site engineers have to face problems of allocating facilities to proper locations, which could maximize the productivity of construction sites. This kind of problems has not been easy to solve because the potential solution space usually is large. Genetic algorithms (GAs) are searching mechanisms based on nature selection, survival of the fittest, and theories of genes. GAs have proved to be efficient for solving large-scale optimization problems. A new genetic algorithm to improve efficiency in generating solutions for facility layout problems is developed in this research. The results show that the new algorithm can find the optimal solution efficiently. In addition, a user-friendly program based on the MicrosoftÒ Excel and VBA is developed, which make the results more applicable to facility layout problems.

碩士
中原大學
工業工程研究所
102
Abstract Traditional facility layout problem assumes that all of the parameter are known. However in the real world, parameter such as demand of the product would always keep changing; this in result, will affect the production demand. Stochastic facility layout problem have the advantage, such that it can adapt over time subjected to the fluctuations in demand and in results would affect the production demand as well. To create more similar environment to real world scenario, the proposed study would use the stochastic facility layout problem to minimize material handling costs and wastes. Since, facility layout problem is NP-Hard problem we would use meta-heuristic to solve and find the best possible solution. The more recently meta-heuristic, Bat Algorithm (Yang, 2010) is proven to be faster and more efficient on solving benchmark functions (De Jong's, Schwefel's, etc) compared to the previous meta-heuristics. However, no research has been done on implementing bat algorithm to the facility layout problem. the proposed study, proposes a new method on implementing bat algorithm to solve facility layout problem dealing with uncertainty. As a benchmark, Simulated Annealing (SA) algorithm is used as a comparison with the new proposed meta-heuristic. The findings show that Bat Algorithm is proven to be faster and more efficient compare to the SA algorithm. Keyword: Stochastic facility layout problem, Uncertainty, Risk, Bat Algorithm, Simulated Annealing Algorithm

碩士
南台科技大學
工業管理研究所
97
Facility layout, the appropriateness of the decision of the entire production system of cost and efficiency, because a good layout mode will help to improve the efficiency of production systems and process on the manufacture, opposite poor layout mode will greatly reduce the efficiency of production. In the traditional solving facility layout mode, most are select one model to solve of qualitative or quantitative model. as a result of people who use quantitative model believe that the relationship between adjacent facilities, it is difficult to quantify the reasonable. So it is not considered in a model. But this kind of planning, often resulting facilities adjacent but that should not adjacent. That will make the manufacturing process in the troubled and reduce production efficiency. In the qualitative model also assumes that all factors of the facility layout is used to represent closeness rating. To make the planning are subjective. Therefore the study will thank about qualitative approach and quantitative approach on the same time. To become a multiple objective optimization question. There are many algorithms that solve a multiple objective optimization question have been published. Genetic Algorithm operations process is Parallel Search and many chromosomes are worked equal to a group of temporary solutions at the same time in search. That can make solving more stable quality, and in solving the optimization problem, there is no limit too much of mathematics. All discrete, continuous and mixed of space that limitations and its objectives is linear or nonlinear operations can be solved. So this study will use the genetic algorithm to solve the facility layout problems, and considering two different attributes of the target and solving the final pareto optimal set. Using genetic algorithm of the special characteristic, save a lot of time, in order to make pursuant to decision by leaders and picked out a more appropriate solution for the final implementation to solve the multi-objective optimization problem of facility layout.

The facility layout problem is modelled as a cycle decomposition process in which the maximum-weight clique and travelling salesman problems are utilized to extract cycles from the graph adjacency matrix. The space between cycles is triangulated so the graph is maximally planar. The adjacency graph is then systematically developed into a block plan layout. With use of the maximum-weight clique algorithm, the procedure addresses layout problems that are not 100% dense. Many examples are utilized to demonstrate the flexibility of the algorithm and the resulting adjacency graph and block plan layout drawings. The Steiner Circulation Network solution derived from an adjacency graph solution and its dual graph, provides a minimum cost system of hallways and connecting links for the material handling system. Using the flows between activities and departments in a layout problem, the circulation network provides the necessary link between the steps of finding the adjacency graph solution and finding useful block plan layout. A case study demonstrates how the solution for the layout and its material handling system can be integrated. Computational results up to size n = 100 are presented along with a comparative study with a competitive algorithm.

博士
元智大學
工業工程與管理學系
91
A Study of Facility Layout Problem by Genetic Algorithm Student : Ming-Jaan Wang Advisor : Dr. Michael H. Hu Institute of Industrial Engineering and Management Yuan-Ze University ABSTRACT Minimal material handling cost (MHC) achievement is one of the critical objectives in facilities layout problems for layout designers. However, solving the larger departments of facilities layout problem accompanying with the optimal MHC is time-consuming or even infeasible. Therefore, many heuristic algorithms such as simulated annealing (SA), tabu search (TA), and genetic algorithm (GA) were developed to find out near-optimal solutions for MHC. This study used genetic algorithm and a rule-based expert system to implement and create space filling curve (SFC), for achieving the optimal solution of the discrete facility layout problem. Concerning the equal area department problems, the objective function is mainly according to the measurement of material flow factor cost (MFFC). However, the objective function for unequal area department problem in this study is a multiple criteria, involving MFFC, shape ratio factor (SRF), and area utilization factor (AUF) to reach minimal total layout cost (TLC). Then, a method of modified the irregular-shape departments to regular-shape ones and eliminate the redundant areas based on the principle of 100% area utilization is proposed. The experimental results show that the proposed approach is much more feasible for dealing with the facilities layout problems and better than existed results. Keyword: Genetic Algorithm, Space Filling Curve, Material Flow Factor Cost, Shape Ratio Factor, Area Utilization Factor, Total Layout Cost

碩士
立德管理學院
應用資訊研究所
95
The facility layout problem is a part of the application in the artificial intelligence. It is belong to the combinatorial optimization and quadratic assignment problem. For many artificial intelligence tools, the tabu search algorithm is widely applied to a lot of combinatorial optimization problems. In this research, an improved tabu search algorithm is developed to solve a NP-complete problem in the facility layout problem. The approach on the two facilities layout problems is examined. The first one is a construction site layout problem, and the second one is a hospital facility layout problem. In order to get better layout result, this research has tried the different setting in this algorithm by altering the values of parameters. This research can provide a good algorithm to solve the quadratic assignment problem in facility layout arrangement.

碩士
義守大學
工業工程與管理學系碩士班
95
In a classical static facility layout problem (SFLP), the facility is divided into a group of divisions, each called a department, a set of candidate locations are preserved for locating these departments, and the quantity of material flows between each pair of departments, the distance of each pair of candidate locations, and the cost per unit of flow per unit distance are calculated in which the material flows between pairs of departments or relative material flows are assumed to be constant over time. The dynamic facility layout problem (DFLP) extends the SFLP by designing the facility layouts based on multiple period planning horizons that assumes the material flows between pairs of departments might be changed over time periods in order to take today’s highly changeable manufacturing environment into account. The trade-offs between costs of excess material handling if a layout is not rearranged when required and costs of such rearrangements make the DFLP much more difficult than the SFLP. There are N! possible solutions in the SFLP and (N!)T possible solutions for the DFLP instance with N departments and T periods. For their high combinatorial complexities, we need to apply the modern heuristic solution methods to solve those DFLP problems with reasonable large departments. In this thesis, we develop a new heuristic method based on the basic idea of the genetic algorithm for solving the dynamic facility layout problem (DFLP), and test numerically the new method with test problems taken from literature. The new heuristic method produces 11 new best solutions of 48 problems in the literature. The new heuristic produces solutions with average deviation of 1.29% and -0.34% for the shorter and longer period smaller size test problems respectively while comparing with the best solution in the literature, -5.76% and -7.01% for the medium size test problems, and -10.47% and -9.04% for the larger size test problem.

碩士
國立清華大學
工業工程與工程管理學系所
105
Single Row Facility Layout Problem (SRFLP) is a permutation problem which has been widely studied in the academic field in order to improve the efficiency on production site. The main purpose of SRFLP is to find an optimal permutation of a number of rectangular facilities with given material flows between each facility, in order to obtain the minimum total cost by arranging them along a straight line. Since SRFLP has already been proven to be a NP-Complete problem, it is irrational to expect to obtain the global optimal solution by exhaustive methods, therefore the recent researches of SRFLP have therefore been adopted to heuristic algorithms in order to obtain an optimal or a near optimal solution within acceptable CPU time. In this paper, we use a novel, efficient heuristic algorithm called Simplified Swarm Optimization algorithm (SSO), with an effective local search mechanism, and other optimizational techniques to find the near-optimal solution for SRFLP within acceptable time. With a comparison to the computational results of two benchmark problem sets from the previous studies, it is shown that our proposed method has better efficiency in solving SRFLP, without sacrifice the effectiveness of the algorithm. Key

碩士
中原大學
土木工程研究所
99
In this study, a new flexible bay structure representation and a particle swarm optimization containing multiple swarms (PSOMS) and are proposed to solve the unequal-area facility layout problem. An efficient method of coding the relevant features of a layout as a particle memory is an important requirement for applying PSO to the facility layout problem. A mixture coding which combines integer coding with real coding is proposed in this study. The symbols for the code of sequence lists of departments are integers between 1 and N, which represent departments. The same way is used to represent the number of bays. The symbols for the code of the bay width are real numbers between 0.0 and the area width. Several international benchmark problems are used to test the algorithm efficiency of PSOMS. The results are compared with the previously best known solutions. PSOMS can obtain the same or better solutions to some benchmark problems. These results show the potential for solving complex facility layout problems.

碩士
中原大學
工業與系統工程研究所
99
With today’s booming economy, in order to keep with product demand, manufacturing factory must find a way to raise productivity and reduce cost to obtain maximum profits. Thus, the purpose of the study is to improve facility layout. In order to reflect the reality situation, this study combines multi-objective and dynamic facility layout, considing the both material flow cost and closeness ranking between departments. Therefore, Multi-objective dynamic facility layout problem is developed. Multi-objective dynamic facility layout problem is a NP-Hard problem, which and resembles the quadratic assignment problem. It uses “Heuristic” to solve NP-Hard problem to save production time and cost. Therefore, this study uses hybrid ant colony system with Pareto optimal front. The Pareto optimal front is combined with Ant Colony Optimization to form Pareto optimal Multi-objective Dynamic Layout (ACO-PMDL) to solve the Multi-objective Dynamic Facility Layout problem. In this study, we use ACO-PMDL method to solve for dynamic facility layout problem, multi-objective facility layout problem and Multi-objective dynamic facility layout problem, based on datasets from literatures to test ACO-PMDL solution quality. The results show ACO-PMDL has better solutions for dynamic facility layout problem and multi-objective facility layout problem. For multi-objective dynamic facility layout problem, the ACO-PMDL solution effectively places one department next to another in terms of importance departments. In terms of total material flow cost, the results from ACO-PMDL are much better than reference solution. From the results, ACO-PMDL of this study is proven to find the best department assignment of Multi-objective dynamic facility layout problem.

碩士
國立臺灣科技大學
工業管理系
100
The layout positioning problem of facilities on a straight line is known as Single Row Facility Layout Problem (SRFLP). The objective of SRFLP, categorized as NP-Complete problem, is to arrange the layout so that the sum of distances between all facilities’ pairs can be minimized. Estimation Distribution Algorithm (EDA) improves the solution quality efficiently in first few runs, but the diversity lost grows rapidly as more iterations are run. To maintain the diversity, hybridization with meta-heuristic algorithms is needed. This research proposes Artificial Particle Swarm Optimization (APSO), an algorithm which consists of hybridization of EDA, Particle Swarm Optimization (PSO), and Tabu Search (TS). Other hybridization algorithms are also built as comparers. They are extended Artificial Chromosomes Genetic Algorithm (eACGA), Estimation Distribution Algorithm Particle Swarm Optimization (EDAPSO), and Estimation Distribution Algorithm Tabu Search (EDAtabu). APSO’s performance is tested in 15 benchmark problems of SRFLP and it successfully achieves optimum solution. Moreover, the mean error rates of APSO always get the lowest value compared to other algorithms. SRFLP can be enhanced by considering more constraints and become enhanced SRFLP. Computational results show that APSO also can solve enhanced SRFLP effectively. Therefore, we can conclude that APSO is a promising meta-heuristic algorithm which could be used to overcome the basic and enhanced SRFLP.

碩士
中原大學
土木工程研究所
99
The Facility Layout Problem (FLP) is a typical combinational optimization problem. In this research, a slicing tree and self-adaptive harmony search (SGHS) based heuristic is proposed for solving unequal-area block layout problem. The major difference between SGHS and harmony search (HS) is the harmony memory consideration rate and pitch adjustment rate of SGHS are dynamically adapted by the learning mechanisms. Furthermore, the newly developed pitch adjustment is composed of two schemes, intra-subtrees and inner-subtrees. To evaluate the effectiveness of this approach, a series of computational experiments are performed and testing results are compared to those found in the literature. Datasets of well known problems, O7, O8, O9, and Ba12 are used for demonstration. Additionally, a large problem instance comprised of 62 facilities has been solved in reasonable time.

碩士
國立臺北科技大學
工業工程與管理系碩士班
100
Facilities layout is a professional technique to assign departments to the appropriate location, and to reach the minimal handling cost and land cost for a system. In addition, an appropriate layout could improve the productivity, increase the production efficiency and cost down the operation expenses of a system. Many papers are published about continuous layout problem (CLP), CLP is to place the departments anywhere within a plant site without overlapping each others. CLP is base on two dimensions framework problem, however, to find the optimal layout cost of larger departments is too complexity and time-consuming. Boundary search heuristic (BSH) is a dimension schema for solving CLP, BSH could reduce the computing time and dealing with much more feasible for facilities layout problem. In order to eliminate redundant area and evaluate the layout cost of CLP, a factor of area utilization is considered in objective function of this research. Through BSH to define the correlation between the departments, and then generate the characteristics of layout design to encode. By Genetic Algorithms to achieve the improvement of BSH.

碩士
中原大學
工業與系統工程研究所
103
In the twenty-first century, sustainable development has become a topic can’t be ignored. The earth’s effect of global warming due to greenhouse gases(GHG) continue to increase caused seriously increasing. Many studies have shown that it’s caused by the manufacturing industry and supply chain. How to reduce the damage made by enterprise to the Earth has become a problem decision-makers need to face now. This study apply reducing carbon emissions generated by the supply chain as one objective, and in order to measure the carbon footprint of sustainable management of enterprise. To create more similar environment to real world scenario, this study apply dynamic facility layout as research methodology. At the same time, consider material handling cost between departments and closeness rating of neighboring departments. This study can be defined as a multiple objective optimization problem. Because of this dynamic facility layout problem with three objectives and three periods and lots of data, this problem is a NP-Hard problem, so this study choose Meta-heuristic to solve it. Multi-objective Bat algorithm and Multi-objective Simulated Annealing algorithm are used in this problem. After running the two algorithm, Pareto optimal solution is used to compare the solution which with three objectives can’t be compared with each other. Finally, this study also compare the solving efficiency and the solution diversity of the two algorithm. The results show that the diversity of two algorithm are almost the same, but for the solving efficiency, Multi-objective Bat algorithm has an edge over Multi-objective Simulated Annealing algorithm.

碩士
國立中央大學
工業管理研究所
98
Recently, competitions among companies have been increased by advanced technology. Therefore, the facility layout of corporation will play an important role in the future and it will have influence on operational efficiency. In the past, traditional facilities planning always focused on the single-period. Because it did not consider the long-term layout planning for the future, it should pay extra cost and time when it need to re-layout. Basically, manufacturing organizations often adjust and vary layout periodically for the business strategy. For example, expanding, shrinking and moving the departments. Dynamic strategy is adjusting design of moving materials, varying space of departments via planning periods, to design and arrange the most efficient facility layout. But it will produce some relocation costs since change the layout from certain period to the next. However, we proposed a heuristic algorithm to minimize both material handling costs and relocation costs. Assuming all the departments are rectangular in shape, varying departments in area, given facility in area and planning period. We operate graph-pair to control the location of departments in layout. Solving the dynamic facility layout by a mixed-integer programming and dynamic heuristic algorithm.

碩士
國立中央大學
工業管理研究所
95
In recent years, semiconductor manufacturing (SM) companies enthusiastically establish 300-mm fabs. However, establishing a new SM facility needs at least multi-billion US dollars. With the limited area in Taiwan, large footprints not only pose constraints for the facility designer but present challenge in the design of automatic material handling system (AMHS). SM is a highly sophiscated operation with various processes to be performed, and SM factories typically have reentrant flow to introduce the incresed number of process steps. In response to such challenge, it has become necessary to eliminate the manual handling of the wafers. As a result, facility layout design and AMHS are two major aspects to achieve a sucessful 300-mm fab. The purpose of the optimazation of material transport is to reduce cycle time, work in process (WIP), delivery time, and increase yield. Therefore, the approach attepmpted to incorporate facility layout and AMHS simulataneously has become a critical factor on factory operation. This paper focuses on using the integrated fab layout to achieve a short transportation distance of interbay by employing heuristic algorithm and mathematical programming model. In addition, this paper proposes this two-stage procedure can obtain a good quality solution. Based on this analysis, effective facility layout is shown to reduce tansportation distance of wafer lots, and increase equipment utility. This pape will mainly aimed double-loop configuration(which is blend spine-configuration with Perimeter-configuration) facility layout problem.

碩士
中原大學
工業與系統工程研究所
98
Genetic algorithm (GA) is used to solve the facility planning problems of TFT-LCD array fab in this study. It minimizes glass substrate’s average moving distance as the objective function. Research model is formed by Evolver. The model produces four optimal layouts with the shortest distance from the arrangement of transport from four types of product mix, and it yields the best performance across four scenarios in terms of the distance. Results indicate that the layout of product mix 1:1:1 is better than other layouts in shortening the average sheet moving distance. The proposed GA method outperformed the Fab Design Procedure (FDP), a step-by-step approach to conduct quick calculations to develop and evaluate the initial design alternatives for TFT-LCD array fab, proposed by Yang in 2008.

碩士
中原大學
工業與系統工程研究所
100
Nowadays, facility layout problems exist in places like companies or even countries. In the past, researches are conducted on Static Facility Layout Problem (SFLP); later, the focus has been shifted to Dynamic Facility Layout Problem (DFLP). In the past, most researches are about Equal-Area Static Facility Layout Problem (EA-SFLP) or Unequal-Area Static Facility Layout Problem (UA-SFLP) and Equal-Area Dynamic Facility Layout Problem (EA-DFLP). A few journal articles are published about Unequal-Area Dynamic Facility Layout Problem (UA-DFLP). In reality, generally the areas of facilities and departments are unequal in sizes. Therefore, this research will be conducted on Unequal-Area Dynamic Facility Layout Problem to better reflect the real situation. This research applies the method of Flexible Bay Structure (FBS) to solve the unequal area aspect of UN-DFLP with consideration of flow line for each department. Regarding the rearrangement cost, previous researches take the centroid-to-centroid approach for interdepartmental rearrangement. However, in reality there are aisles along each department; the consideration is part of the research. Because the problem is a NP-hard problem, we apply the Particle Swarm Optimization (PSO) to find the near-optimal solution and compare it with the Hill Climbing heuristic. Based on the result, PSO is proven to be better than Hill Climbing. A case study is also presented to illustrate the practical use of the proposed ideas and techniques.

碩士
中原大學
工業與系統工程研究所
100
As the world economy moves toward globalization, the increasing competition between enterprises has been becoming fierce. Enterprises, in order to survive, must continually update production strategy and improve production efficiency while reducing costs. One of important factors that impact production efficiency is the design of facilities. Currently, little attention is given to considering the Unequal-Area Problem (UAP) and the Dynamic Facility Layout Problem (DFLP) at the same time. However, in the real environment, companies often will update production strategies and rearrange departments in sequence. And in the enterprise, department areas typically are not all equal. Therefore, this study takes Flexible Bay Structure (FBS) approach to consider Unequal-Area and Dynamic Facility Layout at the same time. Taking a layout’s costs into account, most literatures take the centroid-to-centroid approach to compute costs after departmental exchanges; nevertheless, that approach is abstracted from the real-world scenario, and some distances are skipped from consideration. Accordingly, this study sets the departmental exit points and measures the distances for transportation along aisles to the entry points of some other departments. Facility Layout Problem is a NP-hard problem. In this study, the Ant Colony Optimization (ACO) is used on the facility layout problem and compared with the Particle Swarm Optimization over data from a metal parts factory. The findings from the study have shown that Ant Colony Optimization is better than Particle Swarm Optimization and is promising to solve the unequal, dynamic facility layout problem in a real-world situation.

碩士
元智大學
工業工程與管理學系
93
In the facility layout problems, the objective functions can be classified into either quantitative or qualitative factors in nature. The quantitative factors include distance, flow, or cost. However, the quantitative factors may include the departmental relationships, or environmental effects. In the past, the researches tend to focus on the quantitative factors with single or multiple objectives. With the rapid growth of the service industry, the focus of the facility layout problem is concerned with the best allocation of the offices and service areas. However, this problem does not have the flow information and should take the departmental relationship instead. This research tried to find an appropriate model which focused on the departmental relationship with single objective. An Ant Colony Optimization (ACO) heuristics was developed to find the best layout alternative with the aid of the space filling curve in the departmental generation and allocation. The results showed that this performance rating of the proposed heuristic (Z) performed evenly with the TCR rating, while the performance rating (Z) would perform better with the WCR rating. We also applied the Taguchi method to find the best design parameters of the ACO heuristic so that a better solution can be found. The solution quality was affected by the number of departments, and can be improved by increasing either the generation or the number of the ants.

碩士
國立屏東科技大學
工業管理系所
95
Facilities planning is the major and critical among all the production activities. With well-organized facility layout environment, it could not only increase the general and machine productivity, but could also decrease the costs of transportation and production, and it could enhance the competitive ability of corporates. In the TFT-LCD related industry, the investment is mostly aiming on machines and building the clean rooms. A good facility layout takes even more important role in the whole errands. Thus this research is aiming on the facility layout for the back-light module lab in TFT-LCD related industry. With the past experiences, when we are processing the department relation assessment of facility layout, it is frequently planned without noticing the relation scale between departments. This research is to adapt the concept of fuzzy theory to study the identify and quantify relation scale, and to demonstrate the activity-related scale between departments by Fuzzy Linguistic Variable. By the procedure of defuzzify, the gualitation and quautitative activity relationship between departments can be transtered into a crisp value. The last procedure is to divide the activity relation scale between departments into three different types and have the SPIRAL system simulation. These types are: Identify factor input for activity relation scale between departments, quantify factor input for activity relation scale, and integrated relation scale between departments for identify and quantify. By adopting the system to simulate, we could learn the best layout method from the sum of shortest distance. Then analyze these three layout methods to compare the presence one in order to attain the best layout method. Meanwhile, we will also study on the SPIRAL parameter condition settings of the best layout method for the future researchers’ reference.

Significant improvements in production effectiveness have resulted from implementing cellular manufacturing systems (CMS). Following the cell formation, an important issue that needs to be addressed is the unequal cell (or department/facility) layout problem, which is the sub-issue in the CF problem. The work reported in this thesis illustrates the assignment of unequal cell locations in dealing with the known traffic movements on a shop floor. In addition, this research addresses the impact of the geometry or shape of the department as an important design factor in the unequal area facility layout problem, an issue that has not been addressed by the previous researchers. The problem is formulated as a mixed-binary non-linear programming model and is proven to be NP-hard in the strong sense. Due to its computational complexity, a higher-level heuristic, based on a concept known as tabu-search, is proposed to efficiently solve the problem. Six different versions of the tabu search-based heuristic algorithm are tested on three different problem structures. The results obtained from performing the experiment concluded that the tabu search-based heuristic using short-term memory and variable tabu-list sizes is preferred over other heuristics as the problem size increases. The performance comparison between the current and the previous research shows that the solution obtained for the well-known problems in this research are better than that obtained in the past.
Graduation date: 2002

碩士
中原大學
土木工程研究所
99
In this thesis, a flexible bay structure (FBS) and hybrid ant colony algorithm (HACO) are proposed for solving unequal-area facility layout problem. Hybrid ant colony algorithm is based on ant colony optimization (ACO) and ACO are combined with clonal selection algorithm (CSA). Four characteristics of CSA, clone, mutation, memory cells, and suppressor cells, are introduced to improve the solution quality of initial solutions and to increase differences among each ant solution. Several international benchmark problems are used to test the algorithm efficiency of HACO. Compared with other studies of unequal-area facility layout problem, HACO can obtain the same or better solutions to some benchmark problems. In addition, HACO can get the same solution as ACO with less computational time.

碩士
國立中央大學
工業管理研究所
96
In semiconductor manufacturing, getting high performance in low cost such as reducing work in process, delivery distance or delivery time, cycle time and increase yield is the most important purpose. How to get the high performance is the question. The facility layout design and AMHS, doing the best in finite space, are the questions to achieve a successful 300mm fab. The purpose on this paper is that the products to process of the Bay must pass through the Stocker, it is almost cost a lot of time. If we can set up a Direct Transport Track within Bays to make the products pass through without Stocker. We trust that set up a Direct Transport Track can reduce transportation distance and save a lot of time. For this reason to plan the best Direct Transport Track, we must consider the IntraBay and InterBay layout. The paper focuses on spine configuration in fab layout, and in different of other papers, it considers the IntraBay and InterBay defined. To achieve a short transportation distance both in IntraBay and InterBay, we using heuristic algorithm and mathematical model. First, we defined the machine layout of Bay by FLA method, Simulated Annealing, and Extra cost. Second, we defined the Bay layout by Visual C++ and mathematical model using CPLEX 7.0. Final, we find the Direct Transport Track also by mathematical model. Based on this analysis, we expect that the facility layout will reduce transportation distance of wafer lots, and increase equipment utility.

碩士
國立交通大學
交通運輸研究所
86
The problem for facility planning is considered for get minimize cost of the facility layout. There have been many other proposed applications of these, forexample, factory layout problems, circuit layout on PCB, plannar facility layout, information retrieval for storage facility and site position in network., etc. We can find this kind problem can be modelled as a Quadratic Assignment Problem (QAP).Quadratic assignment problem is a discrete, nonlinear, nonconvex problem. Sahni and Gonzale have been proved it belong to the class of NP-hard problems, which are not likely to be solved exactly in the reasonable time. And most traditional heuristic can only offer the technical for local search method. Get the cost can only be optimal solution.In this research, the main purpose is try to solve the problem of facility planning, using these AI heuristic that developed in recently, Threshold Accepting (TA), Record to Record Traveling (RRT), to be the kind technology for global searching. Use testing problems in QAPLIB for test AI heuristic efficient and cost. When considering the practical problem will meet the situation for site constraint , therefore we make a new mathematical model for solve this problem. After modelling, use an example from factory of the mass rapid transit, then use the AI heuristics that we developed for solve this example. lity planning is considered for get minimize cost of the