To see the other types of publications on this topic, follow the link: Layout problems.
Dissertations / Theses on the topic 'Layout problems'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Layout problems.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Narayanan, Venkataramani. "Design of hybrid layouts for large size facility layout problems." Thesis, Wichita State University, 2007. http://hdl.handle.net/10057/1544.
Full textAbstract:
Generally facility layout problems are solved traditionally using assembly layout or process layout or cellular layout. Hybrid layouts are layouts that combine all three traditionally layouts considering product characteristics and capacity requirements. In this research, a systematic methodology to design the hybrid layouts is performed. The need for developing a hybrid layout is justified based on the product routing and layout requirements. The size of the problem is minimized using product analysis techniques
which also minimizes the computational time. New similarity measures are developed to
consider the missing entities of the previous research works. Products and machines are segregated for different type of layouts (assembly layout, process layout and distributed layout) based on machine utilization and the similarities between the products. Mathematical models are developed to arrange machines that are segregated for the different types of layouts. The computational time of the mathematical models are also minimized by introducing the product machine incidence matrix as the input data. The effective utilization of the machines is maximized by sharing the machines between the layouts. The proposed methodology is evaluated by two case studies. It is proved that the methodology is effective to solve large sized facility layout problems.Thesis (M.S)--Wichita State University, College of Engineering, Dept. of Industrial and Manufacturing Engineering
"December 2007."
2
Narayanan, Venkataramani Krishnan Krishna K. "Design of hybrid layouts for large size facility layout problems /." Thesis, A link to full text of this thesis in SOAR, 2007. http://hdl.handle.net/10057/1544.
Full text
3
Sprague, Alan P. "Problems in VLSI layout design /." The Ohio State University, 1988. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487597424138645.
Full text
4
Ren, Jintong. "Optimization algorithms for graph layout problems." Thesis, Angers, 2020. https://tel.archives-ouvertes.fr/tel-03178385.
Full textAbstract:
Cette thèse considère deux problèmes de disposition des graphes : le problème de la bande passante cyclique (CBP) et le problème de l’agencement linéaire minimum (MinLA). Le CBP est une extension naturelle du problème de minimisation de la bande passante (BMP) et le MinLA est un problème de somme minimale. Ces problèmes sont largement appliqués dans la vie réelle. Puisqu’ils sont NP-difficile, il est difficile de les résoudre dans le cas général. Par conséquent, cette thèse est consacrée au développement d’algorithmes heuristiques efficaces pour faire face à ces problèmes. Plus précisément, nous introduisons deux algorithmes de recherche locale itétée, un algorithme mémétique avec différents opérateurs de recombinaison pour le CBP et une heuristique de voisinage basée sur un ensemble pour résoudre le MinLA. On montre expérimentalement que pour le CBP, les deux algorithmes de recherche locale itéré pouvaient concurrencer favorablement les méthodes de l’état de l’art, le croisement approprié est identifié pour l’algorithme mémétique. On montre également que pour le MinLA, l’heuristique de voisinage basée sur l’ensemble s’est avérée plus efficace que des algorithmes avec voisinage traditionnel à 2-flipThis thesis considers two graph layout problems: the cyclic bandwidth problem (CBP) and the minimum linear arrangement problem (MinLA). The CBP is a natural extension of the bandwidth minimization problem (BMP) and the MinLA is a min-sum problem. These problems are widely applied in the real life. Since they are NP-hard problems, it is computational difficult to solve them in the general case. Therefore, this thesis is dedicated to developing effective heuristic algorithms to deal with these challenging problems.Specifically, we introduce two iterated local search algorithms, a memetic algorithm with different recombination operators for the CBP and a set based neighborhood heuristic algorithm to solve the MinLA. The two iterated local search algorithms are experimentallydemonstrated to be able to compete favourably with state-of-the-art methods, the feature of a suitable crossover for the memetic algorithm is identified for the CBP and the set based neighborhood heuristic algorithm is proven to be more efficient than the traditional 2-flip neighborhood algorithm
5
Dahlbeck, Mirko [Verfasser]. "Solution approaches for facility layout problems / Mirko Dahlbeck." Göttingen : Niedersächsische Staats- und Universitätsbibliothek Göttingen, 2021. http://d-nb.info/1226425682/34.
Full text
6
Traversi, Emiliano <1981>. "Orientation and layout problems on graphs, with applications." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2010. http://amsdottorato.unibo.it/2637/2/traversi_emiliano_tesi.pdf.
Full text
7
Traversi, Emiliano <1981>. "Orientation and layout problems on graphs, with applications." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2010. http://amsdottorato.unibo.it/2637/.
Full text
8
Gamot, Juliette. "Algorithms for Conditional Search Space Optimal Layout Problems." Electronic Thesis or Diss., Université de Lille (2022-....), 2023. http://www.theses.fr/2023ULILB042.
Full textAbstract:
Cette thèse s'inscrit dans le cadre de l'optimisation d'agencement, une étape importante dans la conception de systèmes multidisciplinaires complexes tels que les véhicules aérospatiaux. Les problèmes d'agencement optimal (OLP) consistent à trouver la meilleure disposition d'un ensemble de composants dans un système ou un espace, afin d'atteindre certains objectifs (réduction des coûts, amélioration des performances, etc.) tout en satisfaisant diverses contraintes (géométriques, fonctionnelles, etc.). Le traitement des OLP est encore un défi aujourd'hui, tant en termes de formulation que de résolution. En effet, les OLP sont souvent très contraints et impliquent de nombreuses variables de décision (continues, discrètes, catégorielles), qui peuvent être fixes ou conditionnelles. Les variables conditionnelles sont utiles pour définir différents choix de conception qui doivent être faits en même temps que l'optimisation de l'agencement des composants. Ainsi, la résolution des OLP nécessite l'utilisation d'algorithmes d'optimisation avancés combinant différentes catégories de méthodes, comme par exemple les métaheuristiques et l'optimisation bayésienne.L'objectif global de la thèse est d'étudier les OLP, leur formulation dans différents contextes, leur résolution à l'aide de diverses méthodes d'optimisation et hybridations, ainsi que la validation de ces méthodes dans le cadre de la conception de véhicules aérospatiaux. Les contributions de la thèse sont organisées en deux parties correspondant à deux types d'OLP. Dans la première (respectivement deuxième) partie, la liste de composants à agencer est fixe (resp. variable), impliquant des OLP à espace de recherche fixe ou FSS-OLP, (resp. des OLP à espace de recherche conditionnel ou CSS-OLP). Dans les deux cas, le système/l'espace dans lequel les composants sont agencés est considéré comme mono ou multi-contenant.Dans la première partie, une étude des FSS-OLP est proposée, incluant leurs formulations génériques, leurs applications et méthodes de résolution, avec un focus particulier sur les méthodes quasi-physiques et les métaheuristiques. Basés sur un système de force virtuelle (VF), les algorithmes quasi-physiques simulent les lois de la dynamique et traitent efficacement les problèmes fortement contraints. Une variante (nommée CSO-VF) de de ces algorithmes est développée afin de résoudre les FSS-OLP à un seul contenant. Dans CSO-VF, la position et l'orientation des composants évoluent grâce au VF. Pour traiter les systèmes multi-contenants, CSO-VF est hybridé à un algorithme génétique (GA) dans un algorithme à deux étages qui affecte les composants aux contenants puis optimise leur disposition dans chacun des contenants. Ces deux algorithmes sont évalués grâce à des problèmes d'agencement de satellites.Dans la deuxième partie, une étude des CSS-OLP est proposée avec la même approche que dans la première partie. Les variables conditionnelles engendrent des OLP plus complexes. Par exemple, dans le contexte de la conception aérospatiale, une quantité donnée de carburant peut être incluse dans le système, soit dans un grand réservoir, soit dans deux plus petits. Par conséquent, le nombre de composants à positionner n'est pas le même dans les deux cas et le nombre de variables de conception et de contraintes varie donc au cours du processus d'optimisation. Deux approches ont été développées pour traiter les CSS-OLP à un seul contenant : la première est un GA modifié pour introduire des variables cachées dans les chromosomes. La seconde est une approche bi-niveaux combinant optimisation bayésienne et l'algorithme CSO-VF. L'optimisation bayésienne sélectionne les composants et CSO-VF optimise leur agencement. Cette dernière approche a été hybridée avec un GA dans un algorithme tri-niveaux afin de traiter les CSS-OLP multi-contenants. Enfin, tous les algorithmes sont évalués et comparés grâce à des problèmes d'agencement de satellitesThis thesis falls within the scope of layout optimization, which is an important stage in the design of complex multidisciplinary engineering systems such as aerospace vehicles. Optimal layout problems (OLPs) involve finding the best arrangement of a set of components within a single- or multi-container system or space to meet specific objectives (cost reduction, performance enhancement, etc.) while satisfying various constraints (geometrical, functional, etc.). Dealing with OLPs is challenging both in terms of their formulation and their efficient and effective resolution. Actually, OLPs are often highly constrained and involve many mixed decision variables (continuous, discrete/categorial) which may be fixed or conditional. Conditional variables are highly useful to define different design choices when the set of components to be arranged is variable and dynamic. Consequently, their resolution requires the use of advanced optimization algorithms combining different classes of (mixed-variable) methods including metaheuristics and Bayesian optimization.The overall objective of the thesis is to investigate OLPs, their formulation in different contexts, their resolution using various optimization methods and their hybridization, and their validation within the framework of aerospace vehicle design. The contributions of the thesis are organized in two parts corresponding to two types of OLPs. In the first (resp. second) part, the set of components to be arranged is fixed (variable or conditional) involving fixed search space OLPs or FSS-OLPs (resp. conditional search space OLPs or CSS-OLPs). In both cases, the system/space in which the components are arranged is considered single- or multi-container.In the first part, a survey of constrained mixed-variable FSS-OLPs is proposed including their generic formulations, applications and resolution methods with a particular focus on quasi-physical methods and population-based metaheuristics. Based on a virtual force system (VF) quasi-physical algorithms emulate the principle of physical laws in system dynamics and deal efficiently with highly constrained problems. A variant (namely CSO-VF) of these algorithms is devised for solving single-container FSS-OLPs. In CSO-VF, the positions and orientations of the components are evolved using VF. To deal with multi-container systems, CSO-VF is combined with a Genetic Algorithm (GA) in a two-stage algorithm that assigns the components to the containers and optimizes their layout. These single- and multi-container algorithms are assessed considering satellite module FSS-OLPs that are representative benchmarks.In the second part, a survey of constrained mixed-variable CSS-OLPs is proposed in the same way than in the first part. Conditional variables involve more complex OLPs. Actually, for instance, in the context of aerospace concept design, a given amount of fuel could be included in a container in either one large tank or two smaller ones. Therefore, as the number of components to position is not the same in both cases the number of design variables as well as constraint functions vary during the optimization process. To deal with single-container CSS-OLPs, two approaches have been investigated: the first one is a GA revisited considering hidden variables, leading to variable-geometry OLPs (in objective and constraint functions). The second approach is a two-stage surrogate guided-CSO-VF algorithm combining Bayesian Optimization with CSO-VF. Bayesian Optimization selects the components with are considered by CSO-VF for layout optimization. This latter approach has been extended with a GA in a three-stage algorithm to tackle multi-container CSS-OLPs. Finally, all the algorithms are evaluated and compared based on their application to CSS variants of satellite module OLPs
9
Freire, Marco. "Layout problems under topological constraints for computational fabrication." Electronic Thesis or Diss., Université de Lorraine, 2024. http://www.theses.fr/2024LORR0073.
Full textAbstract:
Les problèmes d'agencement surviennent dans de nombreux contextes en ingénierie et en informatique. Typiquement, la résolution d'un problème d'agencement consiste en l'organisation spatiale et l'interconnexion d'un ensemble d'éléments dans un espace. Cet espace et ces interconnexions peuvent être de complexité très variable. Un ensemble de contraintes et d'objectifs complémentent la description du problème, tels que minimiser la longueur ou la surface des interconnexions, ou fixer la position de certains éléments. La planification des étages en architecture, de niveaux de jeux vidéo, l'agencement d'installations industrielles ou de circuits électroniques, sont tous des exemples de problèmes d'agencement. Les contraintes topologiques jouent un rôle important dans l'agencement. La topologie considère des objets définis par les voisinages de leurs éléments, sans s'attarder sur leur géométrie spécifique. Par exemple, un graphe est une entité topologique, constituée uniquement des liens entre ses nœuds. Au contraire, dessiner un graphe est une opération géométrique, puisqu'elle demande de spécifier la position des nœuds. Cette thèse se focalise sur la résolution de deux problèmes d'agencement spécifiques liés à la fabrication et la conception computationnelles sujets à des contraintes topologiques. Plus particulièrement, il s'agit de la génération d'agencements de circuits électroniques et la génération de supports pour l'impression 3D. La première contribution est un système pour la conception d'écrans surfaciques constitués de DEL RVB à travers l'utilisation de circuits imprimés pliables. Nous plions les circuits imprimés traditionnels en utilisant des motifs de découpe localisés, créant ainsi des `charnières' dans la plaque. Le système prend en entrée un maillage basse-résolution et produit des plans pouvant être envoyés à des services en ligne de fabrication de circuits. Suite à la fabrication, l'écran est assemblé en pliant le circuit sur une impression 3D du maillage d'origine. Les écrans fabriqués peuvent être contrôlés à travers une interface similaire à des shaders pour créer des effets lumineux impressionnants. Le problème global est découpé en sous-problèmes locaux grâce à la topologie chaînée du circuit, les plans finaux étant obtenus en `recousant' les solutions aux sous-problèmes. Au lieu de suivre la méthode traditionnelle d'agencement électronique (concevoir le schéma électrique, placer et connecter les composants); nous décidons du nombre de composants, leur placement et leur routage séparément pour chaque triangle au moment-même de la génération. La deuxième contribution est un algorithme procédural pour la génération de supports pour l'impression 3D sous forme d'échafaudages. Ces supports s'impriment de manière fiable et sont stables [DHL14]. L'algorithme précédent ne considère pas les intersections entre les supports et l'objet imprimé, laissant des marques indésirables sur la surface de l'objet. De plus, la complexité de l'algorithme dépend du nombre de points à porter. Nous proposons un nouvel algorithme inspiré du emph{Model Synthesis} (MS) [Mer09]. Il évite implicitement les intersections et sa complexité est indépendante du nombre de points à porter. Les supports sont représentés indirectement à travers un ensemble d'étiquettes, chacune représentant une partie de la structure (par exemple une partie de pilier, de pont, ou une jonction); et un ensemble de contraintes d'adjacence déterminant quelles combinaisons d'étiquettes sont possibles dans toutes les directions. Les supports sont générés de haut en bas en attribuant de façon répétée une étiquette à un voxel, puis en propageant les contraintes afin d'éliminer les étiquettes rendues impossibles. Cet algorithme, les contraintes d'adjacences et les heuristiques utilisées sont conçues ensemble pour générer des supports sans essai-erreur ou retours arrière, typiques du MS et autres méthodes similairesLayout problems appear in many areas of engineering and computer science. Typically, a layout problem requires to spatially arrange and interconnect a number of geometric elements in a domain. The elements can have a fixed or variable size, as well as an arbitrary shape. The domain may be be a volume, a planar region or a surface. It may be fixed or allowed to reshape. The interconnections may be simple paths, shared contact regions, or both. A set of constraints and objectives complement the problem definition, such as minimizing interconnection length, fixed positions for some elements, and many others. Layout problems are ubiquitous: floorplanning in architectural design, video game level design, industrial facility layout planning, electronics physical layout design, and so on. Topological constraints often arise in layout problems. Topology considers objects as defined by their elements' neighborhoods, without consideration for their specific geometry of placement. For example, a graph is a purely topological structure, consisting only of the relationships between its nodes. On the other hand, a graph drawing needs to specify the position of its nodes, i.e. the geometry of the graph. This thesis focuses on tackling two specific layout problems subject to topological constraints arising in computational design and fabrication. These are electronic circuit physical layout generation and 3D printing support generation. The first contribution is an entire system for the design of freeform RGB LED displays through bendable circuit boards. Typical rigid PCBs are made to bend by strategically using kerfing, i.e. cutting patterns into the board to create `hinges' where it needs to fold. The system takes a low-poly mesh as an input and outputs fabrication-ready blueprints, that can be sent to any online PCB manufacturer. After fabrication, the display is obtained by folding the circuit over the 3D printed mesh. The LEDs are commonly found on commercially available LED strips and are easy to control. Thus, the display can be used through a programmable interface to generate impressive lighting effects in real time. The global layout problem is decomposed into local per-triangle sub-problems by exploiting the chain topology of the electronic circuit, the final layout being obtained by stitching the local solutions. Instead of traditionally following the physical design pipeline, i.e. schematics design, component placement and routing; we decide the number of components, their placement and their routing per-triangle on the fly. The second contribution is a procedural algorithm for generating bridges-and-pillars supports for 3D printing. These supports have been shown to print reliably and in a stable manner in [DHL14]. Unfortunately, the previous algorithm struggles to generate supports that do not intersect the object, leaving visible scars on its surface after support removal. Additionally, its complexity scales with the number of points to support. We propose an algorithm based on emph{Model Synthesis} (MS) [Mer09] to generate these supports, with an implicit knowledge of object avoidance and a complexity independent of the number of points to support. Our algorithm works on a voxelized representation of the object. The supports are encoded in the algorithm with a set of labels, each representing a part of the structure (e.g. a pillar block, a bridge block, a pillar-bridge junction); and a set of adjacency constraints defining all possible label combinations in every direction. The supports for an object are generated top to bottom by repeatedly assigning labels to voxels and propagating constraints to remove inconsistent labels in the domain. The algorithm, adjacency constraints and heuristics are co-designed to avoid the need for trial-and-error or backtracking, typical of MS and similar approaches
10
Finney, Andrew Martin. "The application of graph algorithms to VLSI layout." Thesis, Brunel University, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.235887.
Full text
11
Jaganathan, Jai Kannan Janaki Krishnan Krishna K. "Solution to large facility layout problems using group technology." Diss., A link to full text of this thesis in SOAR, 2007. http://soar.wichita.edu/dspace/handle/10057/1139.
Full textAbstract:
Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Industrial and Manufacturing Engineering."May 2007." Title from PDF title page (viewed on Dec. 26, 2007). Thesis adviser: Krishna K. Krishnan. Includes bibliographic references (leaves 113-120).
12
Ferreira, Fialho dos Anjos Miguel Nuno. "New convex relaxations for the maximum cut and VLSI layout problems." Thesis, Waterloo, Ont. : University of Waterloo, 2001. http://etd.uwaterloo.ca/etd/manjos2001.pdf.
Full textAbstract:
Thesis (Ph.D.) - University of Waterloo, 2001."A thesis presented to the University of Waterloo in fulfilment of the thesis requirement for the degree of Doctor of Philosophy in Combinatorics and Optimization". Includes bibliographical references. Also available in microfiche format.
13
Nayak, Chandan N. "Solutions to dynamic facility layout problems: Development of Dynamic From Between Chart (DFBC) and its applications to continuous layout modeling." Diss., Wichita State University, 2007. http://hdl.handle.net/10057/1493.
Full textAbstract:
Manufacturing facility layout is determined by minimizing the Material Handling (MH) cost associated with the manufacturing of products. A manufacturing facility operates in a dynamic environment where the production rates and product mix are continuously changing. In addition, the introduction of new products/machines and removal of existing products/machines render the existing layout completely unreliable to yield improved productivity. Hence, it is often necessary to analyze the current layout and redesign the layout in accordance with the constantly changes in demand. Existing methods for the analysis of redesign uses multiple, static, and tabular from-to charts. These charts assume and exhibit the timely demand as a discrete invariable quantity. A new tool, “Dynamic From Between Chart (DFBC)” that allows easier visualization of the changes in product rates and mix is introduced and developed in this research. DFBC models the production rate changes using a continuous function. The development process of the new tool, the formulation of the cost function and its application to the solution of Dynamic Facility Layout Problems (DFLP) for multiple time periods is presented with the use of a case study. The solution methodology uses a tradeoff analysis between increased MH cost and the rearrangement cost for the transition from existing layout to a new layout. To further authenticate and strengthen the developed methodology, real world case studies are considered and evaluated. Importance of any department flow over the other departments (crossover) occurs only if there is variation in the flow volumes between relative departments. In previous research, the redesign is carried out at the end of specific time period in a given time horizon. In most instances, the need for redesign or change in flow occurs somewhere during the period and identifying such crossover points will assist to yield better savings. In addition, the exact time at which the layout should be modified can be determined. For large size problems, the number of crossover points sited in DFBC will be large and evaluating each of these points to identify the point of change in layout will be tedious and time consuming. Thus, along with the methodology to identify the crossover points a concept of Upper bound and Lower bound (UB–LB) to discover the set of redesign points which may warrant a change in layout has been developed. Further analysis is necessary to detect the point(s) that initiate the change. Limiting the solution space facilitates the evaluation of large size problems by reducing and simplifying the computation. Multiple case studies are considered and evaluated to indicate the applicability of the concept. It is also evident in current manufacturing paradigms that the introduction of new products/machines and removal of existing products/machines in-between the time horizon induces huge flow variations between departments. Previous research on DFLP does not deal with models which adopt such scenarios. In this research the application of DFBC to analyze the impact of introduction of new products/machines and removal of existing products/machines in between the time horizon is considered. The ability of the DFBC to address such scenarios is evaluated using a case study. Finally, the possible extensions of this research are listed along with the conclusions on the proposed approach.Thesis (Ph.D.)--Wichita State University, College of Engineering, Dept. of Industrial and Manufacturing Engineering
"December 2007."
14
Nayak, Chandan N. Krishnan Krishna. "Solutions to dynamic facility layout problems: Development of Dynamic From Between Chart (DFBC) and its applications to continuous layout modeling /." Diss., A link to full text of this thesis in SOAR, 2007. http://hdl.handle.net/10057/1493.
Full text
15
Mitwasi, Mousa George 1964. "INTEGRATED FORMULATION FOR THE FACILITIES LAYOUT, PROCESS SELECTION, AND PRODUCTION PLANNING PROBLEMS." Thesis, The University of Arizona, 1987. http://hdl.handle.net/10150/276477.
Full textAbstract:
In this thesis we present an integrated formulation for production planning, facilities layout and process selection and provide two heuristics for solving the integrated problem. The traditional solution procedures to each of the subproblems are discussed. The decisions modeled in these three problems are interrelated and, in some cases, share overlapping data requirements. The integrated formulation provided is a mixed integer program. Solving this mixed integer program optimally is a hard problem. Thus, in this thesis we only provide heuristic solutions. An optimal branch and bound algorithm is suggested. Both heuristic solutions are demonstrated on a sample problem. The results of testing eight problems is recorded. Further suggestions for improving the heuristic solutions are also provided.
16
Wang, Yuqiang. "Models and Algorithms for Some Combinatorial Optimization Problems: University Course Timetabling, Facility Layout and Integrated Production-Distribution Scheduling." Diss., Virginia Tech, 2007. http://hdl.handle.net/10919/28757.
Full textAbstract:
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.
17
Fraticelli, Barbara M. P. "Semidefinite Cuts and Partial Convexification Techniques with Applications to Continuous Nonconvex Optimization, Stochastic Integer Programming, and Facility Layout Problems." Diss., Virginia Tech, 2001. http://hdl.handle.net/10919/27293.
Full textAbstract:
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.
18
Daraei, Maryam. "Warehouse Redesign Process: A case study at Enics Sweden AB." Thesis, Mälardalens högskola, Akademin för innovation, design och teknik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-19508.
Full textAbstract:
Nowadays warehousing became one of the most important and critical part in supply chain systems due to the fact that it consumes a considerable part of logistic cost. Designing phase of warehousing system is the most important part in warehousing since most of the strategic and tactical decisions should be taken in this phase. Majority of academic papers are primarily analysis oriented and does not give a systematic method and techniques as a basis for warehouse redesign. So there is a need to develop a structured procedure that can be applied for different type of warehouses. Therefore the purpose of this thesis is to develop a process for redesigning production warehouses, and analyzing major problems during redesign steps. The thesis is designed as a case study, and a mix of quantitative and qualitative methods were used for data collection and data analysis. The methodology focuses around the warehousing process and redesign steps as described in the literature. Results of the thesis develop a seven steps procedure for redesigning of the production warehouse, also different problems and challenges are faced during redesign steps. It was tried to choose the best redesigning method which fit with the characteristics of the warehouse, in order to cover the space reduction of the warehouse with the consideration of existing facilities and reducing of cost. In addition, the performance of the current warehouse system was evaluated based on current design of the warehouse in order to avoid repeating of same mistake in redesign process. Storage assignment policy as one of the redesign steps was discussed and a framework for storage system of the components were suggested. The findings of the thesis to some extent can be applicable to other production warehouses. Further research is suggested for more specific results and new developed redesign methods for all types of warehouses.
19
Theophil, Sebastian Christoph [Verfasser], Hans-Dieter [Akademischer Betreuer] Burkhard, Markus [Akademischer Betreuer] Hannebauer, and Irfan [Akademischer Betreuer] Essa. "Sketching Slides : interactive creation and automatic solution of constrained document layout problems / Sebastian Christoph Theophil. Gutachter: Hans-Dieter Burkhard ; Markus Hannebauer ; Irfan Essa." Berlin : Humboldt Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2011. http://d-nb.info/1015169252/34.
Full text
20
Jaramillo, Juan R. "The generalized machine layout problem." Morgantown, W. Va. : [West Virginia University Libraries], 2007. https://eidr.wvu.edu/etd/documentdata.eTD?documentid=5504.
Full textAbstract:
Thesis (Ph. D.)--West Virginia University, 2007.Title from document title page. Document formatted into pages; contains xi, 86 p. : ill. Includes abstract. Includes bibliographical references (p. 82-86).
21
Kanya, Denise L. "Preprocessing rules for the dynamic layout problem." Ohio : Ohio University, 1994. http://www.ohiolink.edu/etd/view.cgi?ohiou1177533808.
Full text
22
St, Sauver Joseph E. "Parallel approaches to the facilities layout problem /." view abstract or download file of text, 1999. http://wwwlib.umi.com/cr/uoregon/fullcit?p9948030.
Full textAbstract:
Thesis (Ph. D.)--University of Oregon, 1999.Typescript. Includes vita and abstract. Includes bibliographical references (leaves 168-173). Also available for download via the World Wide Web; free to University of Oregon users. Address: http://wwwlib.umi.com/cr/uoregon/fullcit?p9948030.
23
Bark, Ondřej. "Analysis of tracing and capacity utilization by handlers in production." Master's thesis, Vysoká škola ekonomická v Praze, 2015. http://www.nusl.cz/ntk/nusl-206141.
Full textAbstract:
The diploma thesis focuses on tracing in layout by handlers between assembly lines in new plant for corporation Continental Automotive Czech Republic ltd, where boosters are produced. The theoretical part involves definitions of logistics, supply chain, material flow and handling equipment. Furthermore, methods of mathematic programming and software equipment are described, such as quadratic assignment problem, knapsack problem, travelling salesman problem from graph theory. In the practical part the situation in corporation has been analyzed and the data prepared for further examination. Then layout of plant and internal processes are evaluated and an appropriate model or concept of solution is selected. Subsequently, application in MS Excel is created with support of VBA scripts (3 kinds of layouts). The user manipulates with application followed by Solver for implementation of a new solution into practice. Finally, the models are interpreted and verified by Lingo. The focus of the thesis is the design of a layout change of a new plant including the description of tracing.
24
CELLIN, B. P. "Métodos para Resolução eficiente de Problemas de Layout." Universidade Federal do Espírito Santo, 2017. http://repositorio.ufes.br/handle/10/9845.
Full textAbstract:
Made available in DSpace on 2018-08-02T00:03:48Z (GMT). No. of bitstreams: 1
tese_11024_Versão final20171016-125639.pdf: 596775 bytes, checksum: a1c4f15b568902f72ff12a0c184c56a6 (MD5)
Previous issue date: 2017-03-30Em sistemas produtivos onde a diminuição dos custos de produção é vista como peça chave na estratégia competitiva, a otimização entra como uma importante ferramenta para auxiliar as empresas nesse processo de sobrevivência e expansão no mercado. Na indústria surgem muitos problemas de Layout, os quais são problemas de otimização que se caracterizam pelo arranjo físico de facilidades ao longo de uma determinada área, formando um Layout. Problemas de Layout são difíceis e complexos de serem resolvidos do ponto de vista computacional. Por motivação de origem econômica e acadêmica, os problemas de Layout vêm sendo estudados há décadas. Esta dissertação propõe métodos heurísticos e híbridos para a resoluções da alguns destes problemas encontrados na literatura, como os Layouts de facilidades em duas ou mais linhas paralelas. Mais especificamente, são implementados métodos baseados nas meta-heurísticas Simulated Annealing, Variable Neighborhood Search e Iterated Local Search para resolver tais problemas. Além de meta-heurísticas, também é utilizado um modelo de Programação Linear.
25
Kirkizoglu, Zeynep. "Modeling And Analysis Of The Facility Layout Problem." Master's thesis, METU, 2006. http://etd.lib.metu.edu.tr/upload/12607427/index.pdf.
Full textAbstract:
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.
26
Liu, Wen-Hsing. "Tabu search heuristics for the dynamic facility layout problem." Morgantown, W. Va. : [West Virginia University Libraries], 2005. https://eidr.wvu.edu/etd/documentdata.eTD?documentid=3973.
Full textAbstract:
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).
27
Loharjun, Pasu. "A decision theoretic approach to the general layout problem." Diss., Virginia Polytechnic Institute and State University, 1986. http://hdl.handle.net/10919/49824.
Full text
28
Oheba, Jamal Bashir. "A new framework considering uncertainty for facility layout problem." Thesis, University of Manchester, 2012. https://www.research.manchester.ac.uk/portal/en/theses/a-new-framework-considering-uncertainty-for-facility-layout-problem(7e0b665d-ed10-4355-a200-70d52d93eefe).html.
Full textAbstract:
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
29
Kuppusamy, Saravanan. "Simulated annealing heuristics for the dynamic facility layout problem." Morgantown, W. Va. : [West Virginia University Libraries], 2001. http://etd.wvu.edu/templates/showETD.cfm?recnum=2138.
Full textAbstract:
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).
30
Shang, Jin. "Ant colony heuristics for the dynamic facility layout problem." Morgantown, W. Va. : [West Virginia University Libraries], 2002. http://etd.wvu.edu/templates/showETD.cfm?recnum=2579.
Full textAbstract:
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).
31
Marinchek, Dean A. "Manufacturing Facility Layout: A Methodology Incorporating Rotated Aisles into Layout Design." Ohio University / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1417537173.
Full text
32
PERMANHANE, R. M. "Problemas de Layout: Aplicações para CAP e para o DRLP." Universidade Federal do Espírito Santo, 2016. http://repositorio.ufes.br/handle/10/9841.
Full textAbstract:
Made available in DSpace on 2018-08-02T00:03:48Z (GMT). No. of bitstreams: 1
tese_10473_Rafael Marin.pdf: 645952 bytes, checksum: fb1d2d215c00488c495d10075dccff4a (MD5)
Previous issue date: 2016-11-08Foram estudados alguns problemas de layout e escolhidos dois deles:o Corridor Allocation Problem (CAP) e o Doble Row Layout Problem (DRLP). O CAP e o DRLP são NP-Difíceis em diversas situações do mundo real. Os problemas foram resolvidos com a utilização das metas-heurísticas Iterated Local Search e Variable Neighbouhood Descent e a sua hibridização.
33
Jariwala, Anish. "Efficient branch and bound algorithm for the dynamic layout problem." Ohio : Ohio University, 1995. http://www.ohiolink.edu/etd/view.cgi?ohiou1179426531.
Full text
34
Kusumah, Yaya S. "Graph theoretic based heuristics for the facility layout design problem." Thesis, Curtin University, 2001. http://hdl.handle.net/20.500.11937/1059.
Full textAbstract:
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.
35
Kusumah, Yaya S. "Graph theoretic based heuristics for the facility layout design problem." Curtin University of Technology, Department of Mathematics and Statistics, 2001. http://espace.library.curtin.edu.au:80/R/?func=dbin-jump-full&object_id=15301.
Full textAbstract:
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.
36
Ivanqui, Ivan Ludgero. "Um modelo para solução do problema de arranjo físico de instalações interligadas por corredores /." Florianópolis, SC, 1997. http://repositorio.ufsc.br/xmlui/handle/123456789/77147.
Full textAbstract:
Tese (Doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico.Made available in DSpace on 2012-10-17T01:18:12Z (GMT). No. of bitstreams: 0Bitstream added on 2016-01-08T22:36:52Z : No. of bitstreams: 1 138083.pdf: 2606826 bytes, checksum: 9d4f32b3f343f3ec129e261d64218ca7 (MD5)
37
Hakobyan, Artak. "Heuristics for the dynamic facility layout problem with unequal area departments." Morgantown, W. Va. : [West Virginia University Libraries], 2008. https://eidr.wvu.edu/etd/documentdata.eTD?documentid=5699.
Full textAbstract:
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).
38
Mai, Dung Hoang. "A Heuristic for the Constrained One-Sided Two-Layered Crossing Reduction Problem for Dynamic Graph Layout." NSUWorks, 2011. http://nsuworks.nova.edu/gscis_etd/225.
Full textAbstract:
Data in real-world graph drawing applications often change frequently but incrementally. Any drastic change in the graph layout could disrupt a user's "mental map." Furthermore, real-world applications like enterprise process or e-commerce graphing, where data change rapidly in both content and quantity, demand a comprehensive responsiveness when rendering the graph layout in a multi-user environment in real time. Most standard static graph drawing algorithms apply global changes and redraw the entire graph layout whenever the data change. The new layout may be very different from the previous layout and the time taken to redraw the entire graph degrades quickly as the amount of graph data grows. Dynamic behavior and the quantity of data generated by real-world applications pose challenges for existing graph drawing algorithms in terms of incremental stability and scalability.
A constrained hierarchical graph drawing framework and modified Sugiyama heuristic were developed in this research. The goal of this research was to improve the scalability of the constrained graph drawing framework while preserving layout stability. The framework's use of the relational data model shifts the graph application from the traditional desktop to a collaborative and distributed environment by reusing vertex and edge information stored in a relational database. This research was based on the work of North and Woodhull (2001) and the constrained crossing reduction problem proposed by Forster (2004). The result of the constrained hierarchical graph drawing framework and the new Sugiyama heuristic, especially the modified barycenter algorithms, were tested and evaluated against the Graphviz framework and North and Woodhull's (2001) online graph drawing framework.
The performance test results showed that the constrained graph drawing framework run time is comparable with the performance of the Graphviz framework in terms of generating static graph layouts, which is independent of database accesses. Decoupling graph visualization from the graph editing modules improved scalability, enabling the rendering of large graphs in real time. The visualization test also showed that the constrained framework satisfied the aesthetic criteria for constrained graph layouts. Future enhancements for this proposed framework include implementation of (1) the horizontal coordinate assignment algorithm, (2) drawing polylines for multilayer edges in the rendering module, and (3) displaying subgraphs for very large graph layouts.
39
Ozen, Aykut. "Material Flow Cost Versus Congestion In Dynamic Distributed Facility Layout Problem." Master's thesis, METU, 2008. http://etd.lib.metu.edu.tr/upload/12609602/index.pdf.
Full textAbstract:
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.
40
Hasda, Ranjan Kumar. "Contribution to the optimization of Unequal Area Rectangular Facility Layout Problem." Thesis, Ecole centrale de Nantes, 2017. http://www.theses.fr/2017ECDN0026.
Full textAbstract:
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 existantesA 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
41
Almeida, Sheila Souza de. "Otimização de layout de plantas quimicas utilizando o problema de designação quadratica." [s.n.], 2008. http://repositorio.unicamp.br/jspui/handle/REPOSIP/267187.
Full textAbstract:
Orientador: Reginaldo GuirardelloDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Quimica
Made available in DSpace on 2018-08-12T13:45:38Z (GMT). No. of bitstreams: 1 Almeida_SheilaSouzade_M.pdf: 1636225 bytes, checksum: 745e0149ac6b7b1271674496404c47e9 (MD5) Previous issue date: 2008
Resumo: O Layout de uma indústria é de grande preocupação no seu desenvolvimento e, por este motivo, engenheiros e pesquisadores vêm cada vez mais se aprofundando no assunto. A escolha de um bom Layout tem influência nos custos, na segurança, operação e manutenção que são fatores de grande importância para o projeto de planta industrial. Este trabalho tem como objetivo o desenvolvimento da metodologia através de um modelo matemático de otimização para a definição de um Layout industrial através da minimização da função custo, tendo como restrições os critérios de espaço para a segurança, operação e manutenção da planta. Será utilizado como modelo de otimização o problema de atribuição quadrático (QAP), onde se alocam os elementos em uma malha de posições predeterminadas, minimizando a função objetivo. Como este modelo tem uma grande dificuldade em encontrar soluções exatas em tempo viável para a otimização de problemas com grande número de elementos, será utilizado como alternativa métodos heurísticos, que são métodos que encontram soluções rápidas em tempo curto, encontrando uma aproximação para a solução ótima, de fácil implementação e pouco espaço de memória. Dentre as técnicas heurísticas encontra-se o algoritmo Simulated Annealing, um método no qual a solução ótima pode não ser obtida, mas soluções muito próximas a ela são geradas em um tempo de execução muito menor que outras técnicas. Uma característica típica do algoritmo de Simulated Annealing é que além de aceitar soluções que representam melhoramentos no custo, também aceita "deteriorações" (soluções com custo maior) com um certo limite. O mecanismo de geração de soluções escolhido neste trabalho foi a troca de posições entre pares de elementos. A planta escolhida para este estudo foi a de produção de poliéster com 50 equipamentos. Foi necessário estimar com precisão o tamanho e a geometria da rede, para que o tempo computacional fosse o melhor para cada caso. Os resultados indicam que o método escolhido mostrou-se adequado e os Layouts obtidos foram satisfatórios.
Abstract: The layout of an industry is of great concern to its development, and for this particular reason, engineers and researchers are increasingly diving deeper into the subject. Choosing a good layout has a direct influence on costs, security, operations and maintenance, which are all factors of large importance for the project of an industrial plant. This study aims at the development of the methodology through a mathematical optimization model for the definition of an industrial layout by minimizing the cost function, with the restrictions of space criteria for safety, operation and maintenance of the plant. The quadratic assignment problem (QAP), which allocates the elements on to a mesh of preset positions thus minimizing the objective function, will be used as an optimization model. Layout problems usually have great difficulty to encounter exact solutions in viable time for the optimization of problems containing a large numbers of elements; therefore, the alternative heuristic method will be used. This method encounters rapid solutions in short timeframes, finding an approximation for an optimal solution, easy to implement and requires a small amount of storage space. Among the heuristic techniques is the Simulated Annealing algorithm, a method in which an optimal solution may not be obtained, however solutions very close to it are generated in an execution time much smaller than other techniques. A typical characteristic of the Simulated Annealing algorithm is that in addition to accepting solutions that represent improvements in cost, it also accepts deterioration (solutions with greater costs) within a certain limit. The mechanism of generation of new solutions chosen in this study was to change positions between the pairs of elements. In order to demonstrate the proposed approach, a polyester production plant with 50 pieces of equipment was chosen. It was necessary to estimate with precision the size and geometry of the network, so that the computational time was the best for each case. The results indicate that the chosen method proved to be appropriate and the layouts obtained were satisfactory.
Mestrado
Desenvolvimento de Processos Químicos
Mestre em Engenharia Química
42
Davi, André da Silva. "Uma aplicação de metaheurísticas na abordagem do problema de layout de armazém." Universidade do Vale do Rio dos Sinos, 2017. http://www.repositorio.jesuita.org.br/handle/UNISINOS/6802.
Full textAbstract:
Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2017-11-29T16:00:55Z
No. of bitstreams: 1
André da Silva Davi_.pdf: 2370087 bytes, checksum: dcaf9c82247a500748da7c104102054b (MD5)Made available in DSpace on 2017-11-29T16:00:55Z (GMT). No. of bitstreams: 1 André da Silva Davi_.pdf: 2370087 bytes, checksum: dcaf9c82247a500748da7c104102054b (MD5) Previous issue date: 2017-09-12
Nenhuma
Neste trabalho foi desenvolvido um modelo computacional para a otimização de layout de um Armazém. Além da abordagem do Problema de Layout de Armazém, também é abordado o Problema de Família de Partes. Para o desenvolvimento do modelo foi aplicada a metaheurística Algoritmo Genético. O objetivo do estudo é projetar a configuração de um armazém que otimize a alocação de mercadorias nas prateleiras tal que proporcione a minimização da movimentação das mesmas durante a seleção de pedidos, pois a operação e a gerência são partes essenciais das operações e serviços realizados. Para isto, as variáveis de decisão são: a distância absoluta da localização da mercadoria e o número de pedidos por dia. O resultado deste trabalho é a geração de um layout capaz de comportar as mercadorias de acordo com as necessidades de alocação, realizando uma otimização de aproximadamente 15%.
In this work a computational model was developed for a warehouse layout optimization. In addition to the Warehouse Layout Problem approach, the Part Family Problem is also addressed. For the development of the model was applied the metaheuristic Genetic Algorithm. The objective of the study is to design the configuration of a warehouse that optimizes an allocation of goods on the shelves that provides a minimization of the warehouse's movement during order selection, operation and management with essential uses of the operations and services performed. The decision variables are: the absolute distance of the location of the merchandise and the number of requests per day. The result is a set of new layouts, according to the conditions of service and the realization of an optimization of approximately 15%.
43
Franceira, Sergio Norival. "Otimização de layout de plantas quimicas utilizando o problema de designação quadratico." [s.n.], 2001. http://repositorio.unicamp.br/jspui/handle/REPOSIP/266421.
Full textAbstract:
Orientador: Reginaldo GuirardelloDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Quimica
Made available in DSpace on 2018-07-27T15:25:01Z (GMT). No. of bitstreams: 1 Franceira_SergioNorival_M.pdf: 3731488 bytes, checksum: d7857c421064b5382fefae40ea456256 (MD5) Previous issue date: 2001
Resumo
Abstract
Mestrado
Desenvolvimento de Processos Químicos
Mestre em Engenharia Química
44
Zhao, Zhengyang. "Optimizing Task Sequence and Cell Layout for Dual Arm Robot Assembly Using Constraint Programming." Thesis, KTH, Skolan för informations- och kommunikationsteknik (ICT), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-186593.
Full textAbstract:
Nowadays, assembly robots are increasingly used in the manufacturing industry to replace or collaborate with human labors. This is the goal of the dual arm assembly robot developed by ABB. With the rapid upgrading in consumer electronics products, the lifetime of an assembly line could be only a few months. However, even for experienced programmers, to manually construct a good enough assembly sequence is time consuming, and the quality of the generated assembly sequence is not guaranteed. Moreover, a good robot assembly sequence is important to the throughput of an assembly line. For dual arm robots, it is also important to obtain a balance between the two arms, as well as handling scheduling conflicts and avoiding collisions in a crowded environment. In this master thesis, a program is produced to automatically generate the optimal assembly sequence for a class of real-world assembly cases. The solution also takes the layout of the assembly cell into account, thus constructing the best combination of cell layout, workload balancing, task sequence and task scheduling. The program is implemented using Google OR-Tools – an open-source support library for combinatorial optimization. A customized search strategy is proposed and a comparison between this strategy and the built-in search strategy of Google OR-Tools is done. The result shows that the used approach is effective for the problem study case. It takes about 4 minutes to find the optimal solution and 32 minutes to prove its optimality. In addition, the result also shows that the customized search strategy works consistently with good performance for different problem cases. Moreover, the customized strategy is more efficient than built-in search strategy in many cases.Numera används monteringsrobotar alltmer inom tillverkningsindustrin för att ersätta eller samarbeta med människor. Detta är måluppgiften för den tvåarmiga monteringsroboten, YuMi, som utvecklats av ABB. Med den korta produktlivslängden för hemelektronikprodukter kan livslängden för en monteringslinje vara ett fåtal månader. Även för erfarna robotprogrammerare är det svårt och tidsödande att manuellt konstruera en tillräckligt bra monteringsordning, och dessutom kan resultatets kvalitet inte garanteras. En bra monteringsordning är nödvändig för genomströmningen i en monteringslinje. För tvåarmiga robotar, är det också viktigt att få en balans mellan de två armarna, samt hantering av schemakrockar och undvika kollisioner i en trång miljö. I detta examensarbete har ett program skrivits, som automatiskt genererar optimala lösningar för en klass av verkliga monteringsfall. Lösningen tar hänsyn till utformningen av monteringscellen och arrangerar cellen på bästa sätt, balanserar arbetsbelastningen, ordnar och tidsbestämmer uppgifter. Programmet använder sig av Google OR-Tools – ett öppet kodbibliotek för kombinatorisk optimering. Dessutom föreslås en skräddarsydd sökstrategi, som jämförs med Google OR-Tools inbyggda sökstrategi. Resultatet visar att den använda metoden är effektiv för problemtypen. Det tar ungefär 4 minuter att hitta den optimala lösningen och 32 minuter för att bevisa optimalitet. Dessutom visar resultatet att den anpassade sökstrategin konsekvent har en bra prestanda för olika problemfall. Dessutom är den anpassade strategin effektivare än den inbyggda sökstrategin i många fall.
45
Afsharian, Mohsen [Verfasser]. "The Two-Dimensional, Rectangular, Guillotineable-Layout Cutting Problem with Defects / Mohsen Afsharian." Aachen : Shaker, 2013. http://d-nb.info/1051575575/34.
Full text
46
Dahlbeck, Mirko. "Solution approaches for facility layout problems." Doctoral thesis, 2021. http://hdl.handle.net/21.11130/00-1735-0000-0005-155E-B.
Full text
47
Lu, Ying-I., and 呂英毅. "Assembly Layout Problems for Secondary Battery Products." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/57k62d.
Full textAbstract:
碩士逢甲大學
工業工程學所
90
Abstract We have developed an solution framework for solving assembly layout problems of secondary battery products. A two-stage approach have been proposed to resolve this problem. In the first stage, a heuristic is developed that finds an initial group of products. Then an optimal group of production lines is obtained under the consideration of factory area and capacity constraints and the minimum invest cost. This approach reduces set-up time while fixing the machine position. Such a solution can avoid any damage that might result from moving machines during product transfer in the same production line. In the second stage, I apply the line balancing theory to reduce the cycle time. The result not only provides a guideline for investing a new battery assembly factory but also resolves the problem of machine layout. The proposed heuristic is coded using Java computer language. Finally, a case study is performed by implementing the proposed approach in a secondary battery factory. The results obtained suggest that the proposed solution framework can be beneficial for solving the assembly layout problems of secondary battery.
48
Chih-Tsung, Tsai, and 蔡志宗. "A study of space layout planning problems." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/9hve83.
Full textAbstract:
碩士國立臺北科技大學
經營管理系碩士班
103
A space layout planning problem focuses on how to find an optimal layout of a given space in the limited resources and specific conditions. Although many methods have been proposed to solve this problem, for example: the enumerative method and various heuristic algorithms, they cannot guarantee the quality of the solution obtained or solve the problem efficiently. Therefore, how to find an optimal space layout within a reasonable time becomes an important issue. This study proposes a deterministic optimization approach to solve this problem. According to the users needs and constraints, we construct a mathematical model and solve the model for finding the feasible solution. Moreover, this study derives multiple feasible solutions with the same objective value such that decision makers can flexibly choose an optimal layout for more practical considerations. Several examples are presented to illustrate the usefulness and effectiveness of the proposed method.
49
Yang, Feng-Kai, and 楊豐愷. "Study of Facility Layout Problems with Aisle Construction." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/87251415014352203769.
Full textAbstract:
碩士華梵大學
工業管理學系碩士班
90
This thesis proposes an intelligent aisle construction system for automated facility layout problem with indoor and outdoor consideration. So the proposed system not only generates a layout but also suggests the space and distribution of aisles and indoors. The objective function is to minimize material handling cost and aisle space requirement. Therefore, the theory of shortest path, genetic algorithm (GA), and heuristic rules were combined to derive a hybrid genetic algorithm (HGA), which will efficiently suggest layouts with door and aisle structure. A software system was implemented, based on the proposed algorithm, to simulate examples of layouts. The proposed software system also contains an interactive user interface to help the modification of the suggested layouts, including the locations of sub-facility, the number and locations of doors, and the space and distribution of aisles. This proposed research derive an efficient algorithm and implement a software system, includes the design of interactive user interface, to simulate examples of facility layout problems with door and aisle structure. So, the proposed intelligent aisle construction system for automated facility layout will be very efficient and practicable.
50
Jaganathan, Jai Kannan Janaki. "Solution to large facility layout problems using group technology." Thesis, 2007. http://hdl.handle.net/10057/1139.
Full textAbstract:
In this work, a systematic methodology to construct cellular layouts using GT technique for large size problems has been developed. Previous researches in this field have addressed heuristics that can be used to solve only medium size problems. A mathematical model that uses reduced intercellular count as a criterion for cell formation is developed. The developed model includes details like machine sequence, production volume and machine revisits for formation of cells. A performance measure that is used to evaluate the cells being formed is proposed after some modifications in the existing method from Nair & Narendran (1998). Once the cell configurations are evaluated, separate layouts are developed for each cell depending on the amount of flow between machines within their respective cell. The best configuration is selected based on the least material handling cost that a configuration accounts for. This process defines entire steps of the proposed approach. The validity of the proposed approach was verified using small, medium and large case studies. From the case study results, it is concluded that the proposed methodology can be used to solve large facility layout problems using GT. The developed model proved to be efficient irrespective of the size of the problem considered, even after inclusion of details such as machine sequence, production volume and machine revisits along with the performance measure for the cells formed. By restricting the number of cell configurations between an upper and lower limit, the model eliminated the possibility of unwanted configurations that increases the complexity of the problem. So for a large size facility layout problem, the proposed method can be used to get the actual number of intercellular movement between cells and also can be used to select the best configuration for a given production plan using reduced material handling cost as the criteria.Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Industrial and Manufacturing Engineering