To see the other types of publications on this topic, follow the link: Bin packing.
Dissertations / Theses on the topic 'Bin packing'
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 'Bin packing.'
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
Burcea, Mihai. "Online dynamic bin packing." Thesis, University of Liverpool, 2014. http://livrepository.liverpool.ac.uk/2005382/.
Full textAbstract:
In this thesis we study online algorithms for dynamic bin packing. An online algorithm is presented with input throughout time and must make irrevocable decisions without knowledge of future input. The classical bin packing problem is a combinatorial optimization problem in which a set of items must be packed into a minimum number of uniform-sized bins without exceeding their capacities. The problem has been studied since the early 1970s and many variants continue to attract researchers’ attention today. The dynamic version of the bin packing problem was introduced by Coffman, Garey and Johnson in 1983. The problem is a generalization of the bin packing problem in which items may arrive and depart dynamically. In this setting, an online algorithm for bin packing is presented with one item at a time, without knowledge of its departure time, nor arrival and departure times of future items, and must decide in which bin the item should be packed. Migration of items between bins is not allowed, however rearrangement of items within a bin is permitted. The objective of problem is to minimize the maximum number of bins used over all time. In multi-dimensional generalizations of the problem, multi-dimensional items must be packed without overlap in multi-dimensional bins of uniform size in each dimension. In this work, we study the setting where items are oriented and cannot be rotated. We first consider online one-dimensional dynamic bin packing and present a lower bound of 8/3 ∼ 2.666 on the achievable competitive ratio of any deterministic online algorithm, improving the best known 2.5-lower bound. Since the introduction of the problem by Coffman, Garey and Johnson, the progress on the problem has focused on improving the original lower bound of 2.388 to 2.428, and to the best known 2.5-lower bound. Our improvement from 2.5 to 8/3 ∼ 2.666 makes a big step forward in closing the gap between the lower bound and the upper bound, which currently stands at 2.788. Secondly we study the online two- and three-dimensional dynamic bin packing problem by designing and analyzing algorithms for special types of input. Bar-Noy et al. initiated the study of the one-dimensional unit fraction bin packing problem, a restricted version where all sizes of items are of the form 1/k, for some integer k > 0. Another related problem is for power fraction items, where sizes are of the form 1/2k, for some integer k ≥ 0. We initiate the study of online multi-dimensional dynamic bin packing of unit fraction items and power fraction items, where items have lengths unit fraction and power fraction in each dimension, respectively. While algorithms for general input are suitable for unit fraction and power fraction items, their worst-case performance guarantees are the same for special types of input. For unit fraction and power fraction items, we design and analyze online algorithms that achieve better worst-case performance guarantees compared to their classical counterparts. Our algorithms give careful consideration to unit and power fraction items, which allows us to reduce the competitive ratios for these types of inputs. Lastly we focus on obtaining lower bounds on the performance of the family of Any- Fit algorithms (Any-Fit, Best-Fit, First-Fit, Worst-Fit) for online multi-dimensional dynamic bin packing. Any-Fit algorithms are classical online algorithms initially studied for the one-dimensional version of the bin packing problem. The common rule that the algorithms use is to never pack a new item to a new bin if the item can be packed in any of the existing bins. While the family of Any-Fit algorithms is always O(1)-competitive for one-dimensional dynamic bin packing, we show that this is no longer the case for multi-dimensional dynamic bin packing when using Best-Fit and Worst-Fit, even if the input consists of power fraction items or unit fraction items. For these restricted inputs, we prove that Best-Fit and Worst-Fit have unbounded competitive ratios, while for First-Fit we provide lower bounds that are higher than the lower bounds for any online algorithm. Furthermore, for general input we show that all classical Any-Fit algorithms are not competitive for online multi-dimensional dynamic bin packing.
2
Nielsen, Torben Noerup. "Combinatorial Bin Packing Problems." Diss., The University of Arizona, 1985. http://hdl.handle.net/10150/187536.
Full textAbstract:
In the past few years, there has been a strong and growing interest in evaluating the expected behavior of what we call combinatorial bin packing problems. A combinatorial bin packing problem consists of a number of items of various sizes and value ratios (value per unit of size) along with a collection of bins of fixed capacity into which the items are to be packed. The packing must be done in such a way that the sum of the sizes of the items into a given bin does not exceed the capacity of that bin. Moreover, an item must either be packed into a bin in its entirety or not at all: this "all or nothing" requirement is why these problems are characterized as being combinatorial. The objective of the packing is to optimize a given criterion Junction. Here optimize means either maximize or minimize, depending on the problem. We study two problems that fit into this framework: the Knapsack Problem and the Minimum Sum of Squares Problem. Both of these problems are known to be in the class of NP-hard problems and there is ample reason to suspect that these problems do not admit of efficient exact solution. We obtain results concerning the performance of heuristics under the assumption that the inputs are random samples from some distribution. For the Knapsack Problem, we develop four heuristics, two of which are on-line and two off-line. All four heuristics are shown to be asymptotically optimal in expectation when the item sizes and value ratios are assumed to be independent and uniform. One heuristic is shown to be asymptotically optimal in expectation when the item sizes are uniformly distributed and the value ratios are exponentially distributed. The amount of time required by these heuristics is no more than proportional to the amount of time required to sort the items in order of nonincreasing value ratios. For the Minimum Sum of Squares Problem, we develop two heuristics, both of which are off-line. Both of these heuristics are shown to be asymptotically optimal in expectation when the sizes of the items input are assumed uniformly distributed.
3
BALDI, MAURO MARIA. "Generalized Bin Packing Problems." Doctoral thesis, Politecnico di Torino, 2013. http://hdl.handle.net/11583/2507776.
Full textAbstract:
Packing problems make up a fundamental topic of combinatorial optimization. Their importance is confirmed both by their wide range of scientific and technological applications they are able to address and by their theoretical implications. In fact, they are exploited in many fields such as computer science and technologies, industrial applications, transportation and logistics, and telecommunications. From a theoretical perspective, packing problems often appear as sub-problems in order to iteratively solve bigger problems.
Although packing problems play a fundamental role in all these settings, there is a gap in terms of comprehensive study in the literature. In fact, the joint presence of both compulsory and non-compulsory items has not been considered yet. This particular setting arises in many real-life applications, not yet addressed or only partially addressed by the current state-of-the-art packing problems.
Furthermore, little has been done in terms of unified methodologies, and different techniques have been used in order to solve packing problems with different objective functions. In particular, none of these techniques is able to address the presence of compulsory and non-compulsory items at the same time.
In order to overcome a noteworthy portion of this gap, we formulated a new packing problem, named the Generalized Bin Packing Problem (GBPP), characterized by both compulsory and non-compulsory items, and multiple item and bin attributes.
Packing problems have also been studied within stochastic settings where the items are affected by uncertainty. In these settings, there are fundamentally two kinds of stochasticity concerning the items: 1) stochasticity of the item attributes, where one attribute is affected by uncertainty and modeled as a random variable or 2) stochasticity of the item availability, i.e., the items are not known a priori but they arrive on-line in an unpredictable way to a decision maker.
Although packing problems have been studied according to these stochastic variants, the GBPP with uncertainty on the items is still an open problem. Therefore, we have also studied two stochastic variants of the GBPP, named the Stochastic Generalized Bin Packing Problem (S-GBPP) and the On-line Generalized Bin Packing Problem (OGBPP).
Our main results concern the development of models and unified methodologies of these new packing problems, making up, as done for the Vehicle Routing Problem (VRP) with the definition of the so called Rich Vehicle Routing Problems, a new family of advanced packing problems named Generalized Bin Packing Problems.
4
Ilicak, Isil. "Bi-objective Bin Packing Problems." Master's thesis, METU, 2003. http://etd.lib.metu.edu.tr/upload/2/1079987/index.pdf.
Full textAbstract:
In this study, we consider two bi-objective bin packing problems that assign a number of weighted items to bins having identical capacities.
Firstly, we aim to minimize total deviation over bin capacity and minimize number of bins. We show that these two objectives are conflicting. Secondly, we study the problem of minimizing maximum overdeviation and minimizing the number of bins. We show the similarities of these two problems to parallel machine scheduling problems and benefit from the results while developing our solution approaches. For both problems, we propose exact procedures that generate efficient solutions relative to two objectives. To increase the efficiency of the solutions, we propose some lower and upper bounding procedures. The
results of our experiments show that total overdeviation problem is easier to solve compared to maximum overdeviation problem and the bin capacity, the weight of items and the number of items are important factors that effect the solution time and quality. Our procedures can solve the problems with up to 100 items in reasonable solution times.
5
Lundanes, Petter Olsen. "Bin packing problem with order constraints." Thesis, Norges teknisk-naturvitenskapelige universitet, Institutt for datateknikk og informasjonsvitenskap, 2014. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-27334.
Full textAbstract:
This paper presents an algorithm to solve a variant of the bin packing problem with additional constraints on the order of items. The performance of this algorithm is tested, both for optimal solutions and approximations given by early termination, and is found to be limited for optimal solutions, but fairly efficient for decent approximations.
6
Khan, Arindam. "Approximation algorithms for multidimensional bin packing." Diss., Georgia Institute of Technology, 2015. http://hdl.handle.net/1853/54371.
Full textAbstract:
The bin packing problem has been the corner stone of approximation algorithms and has been extensively studied starting from the early seventies.
In the classical bin packing problem, we are given a list of real numbers in the range (0, 1], the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1.
In this thesis we study approximation algorithms for three generalizations of bin packing: geometric bin packing, vector bin packing and weighted bipartite edge coloring.
In two-dimensional (2-D) geometric bin packing, we are given a collection of rectangular items to be packed into a minimum number of unit size square bins. Geometric packing has vast applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems.
We consider the widely studied orthogonal packing case, where the items must be placed in the bin such that their sides are parallel to the sides of the bin.
Here two variants are usually studied, (i) where the items cannot be rotated, and (ii) they can be rotated by 90 degrees. We give a polynomial time algorithm with an asymptotic approximation ratio of
$\ln(1.5) + 1 \approx 1.405$ for the versions with and without rotations.
We have also shown the limitations of rounding based algorithms, ubiquitous in bin packing algorithms. We have shown that any algorithm that
rounds at least one side of each large item to some number in a constant size collection values chosen independent of the problem instance, cannot achieve an asymptotic approximation ratio better than 3/2.
In d-dimensional vector bin packing (VBP), each item is a d-dimensional vector that needs to be packed into unit vector bins. The problem is of great significance in resource constrained scheduling and also appears in recent virtual machine placement in cloud computing. Even in two dimensions, it has novel applications in layout design, logistics, loading and scheduling problems.
We obtain a polynomial time algorithm with an asymptotic approximation ratio of $\ln(1.5) + 1 \approx 1.405$ for 2-D VBP. We also obtain a polynomial time algorithm with almost tight (absolute) approximation ratio of $1+\ln(1.5)$ for 2-D VBP.
For $d$ dimensions, we give a polynomial time algorithm with an asymptotic approximation ratio of $\ln(d/2) + 1.5 \approx \ln d+0.81$.
We also consider vector bin packing under resource augmentation. We give a polynomial time algorithm that packs vectors into $(1+\epsilon)Opt$ bins when we allow augmentation in (d - 1) dimensions and $Opt$ is the minimum number of bins needed to pack the vectors into (1,1) bins.
In weighted bipartite edge coloring problem, we are given an edge-weighted bipartite graph $G=(V,E)$ with weights $w: E \rightarrow [0,1]$. The task is to find a proper weighted coloring of the edges with as few colors as possible. An edge coloring of the weighted graph is called a proper weighted coloring if the sum of the weights of the edges incident to a vertex of any color is at most one. This problem is motivated by rearrangeability of 3-stage Clos networks which is very useful in various applications in interconnected networks and routing.
We show a polynomial time approximation algorithm that returns a proper weighted coloring with at most $\lceil 2.2223m \rceil$ colors where $m$ is the minimum number of unit sized bins needed to pack the weight of all edges incident at any vertex.
We also show that if all edge weights are $>1/4$ then $\lceil 2.2m \rceil$ colors are sufficient.
7
Shor, Peter Williston. "Random planar matching and bin packing." Thesis, Massachusetts Institute of Technology, 1985. https://hdl.handle.net/1721.1/128792.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1985.Bibliography: leaves 123-124.
by Peter Williston Shor.
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1985.
8
Clautiaux, François. "New collaborative approaches for bin-packing problems." Habilitation à diriger des recherches, Université de Technologie de Compiègne, 2010. http://tel.archives-ouvertes.fr/tel-00749419.
Full textAbstract:
Ce document décrit de nouvelles modélisations et approches de résolution que nous appliquons à des problèmes de découpe et de conditionnement. Nous étudions dans un premier temps plusieurs techniques de décomposition alliées à différentes méta-heuristiques basées sur des stratégies d'oscillation. Nous étudions ensuite le concept de fonctions dual-réalisables qui permettent d'obtenir des évaluations par défaut polynomiales pour des problèmes de conditionnement. Finalement, nous proposons des modèles originaux pour des problèmes de placement de rectangles. Nous utilisons ces modèles dans des méthodes de programmation par contraintes.
9
Ben, Mohamed Ahmed Mohamed Abdellahi. "Résolution approchée du problème de bin-packing." Le Havre, 2009. http://www.theses.fr/2009LEHA0031.
Full text
10
Pasha, Arfath. "Geometric bin packing algorithm for arbitrary shapes." [Gainesville, Fla.] : University of Florida, 2003. http://purl.fcla.edu/fcla/etd/UFE0000907.
Full text
11
Sadones, Sylvie. "A new two-phase heuristic for two-dimensional rectangular bin-packing and strip-packing /." Thesis, McGill University, 1985. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=66036.
Full text
12
Braithwaite, Todd Arthur. "Two-dimensional bin packing, innovations and statistical analysis." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp01/MQ30932.pdf.
Full text
13
Souissi, Salma. "Problème du Bin Packing probabiliste à une dimension." Versailles-St Quentin en Yvelines, 2006. http://www.theses.fr/2006VERS0052.
Full textAbstract:
Le Problème de Bin Packing Probabiliste (PBPP) tient compte de la disparition de certains objets après avoir été placés dans les boîtes. Le problème consiste à réarranger les objets restants en utilisant la solution a priori. L’arrangement initial est effectué en utilisant l’heuristique Next Fit Decreasing (NFD). Nous considérons deux stratégies de résolution: la stratégie de redistribution suivant NFD et la stratégie a priori. Dans la première, l’algorithme Next Fit est appliqué à la nouvelle liste. Dans la seconde, des groupes successives de boîtes sont réarrangés d’une façon optimale. Dans les deux cas, nous développons une analyse en moyenne pour le PBPP. Nous prouvons la loi des grands nombres et le théorème central limite pour le nombre de boîtes obtenu par chacune de ces stratégies quand le nombre d’objets initial tend vers l’infini. Nous vérifions ces résultats théoriques par simulationIn the Probabilistic Bin Packing Problem (PBPP) the random deletion of some items once placed into bins. The problem is to rearrange the residual items, using the a priori solution. The initial arrangement being done with the Next Fit Decreasing Heuristic (NFD). We propose two resolution methodologies: the redistribution strategy according to NFD and the a priori strategy. In the first one, the Next fit algorithm is applied to the new list. In the second one, successive groups of bins are optimally rearranged. In both cases, we develop an average case analysis for the (PBPP). We prove the law of large numbers and the central limit theorem for the number of occupied bins as the initial number of items tends to infinity. We verify these theoretical results by simulation
14
Pietrobuoni, Enrico <1986>. "Two-Dimensional Bin Packing Problem with Guillotine Restrictions." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6810/1/PhD_Pietrobuoni.pdf.
Full textAbstract:
This thesis, after presenting recent advances obtained for the two-dimensional bin packing problem, focuses on the case where guillotine restrictions are imposed.
A mathematical characterization of non-guillotine patterns is provided and the relation between the solution value of the two-dimensional problem with guillotine restrictions and the two-dimensional problem unrestricted is being studied from a worst-case perspective.
Finally it presents a new heuristic algorithm, for the two-dimensional problem with guillotine restrictions, based on partial enumeration, and computationally evaluates its performance on a large set of instances from the literature.
Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases.
15
Pietrobuoni, Enrico <1986>. "Two-Dimensional Bin Packing Problem with Guillotine Restrictions." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6810/.
Full textAbstract:
This thesis, after presenting recent advances obtained for the two-dimensional bin packing problem, focuses on the case where guillotine restrictions are imposed.
A mathematical characterization of non-guillotine patterns is provided and the relation between the solution value of the two-dimensional problem with guillotine restrictions and the two-dimensional problem unrestricted is being studied from a worst-case perspective.
Finally it presents a new heuristic algorithm, for the two-dimensional problem with guillotine restrictions, based on partial enumeration, and computationally evaluates its performance on a large set of instances from the literature.
Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases.
16
Matkevičius, Audrius. "Vienmačio supjaustymo uždaviniai." Master's thesis, Lithuanian Academic Libraries Network (LABT), 2005. http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2005~D_20050609_143028-57047.
Full textAbstract:
The purpose of bin packing is the effective apportionment of smaller elements in the bigger ones. The bin packing is being analysed in managment, computers, mathematics and researches of operations. The quality of the heuristic structural algorithm and time have been analysed in the work (the percent of the used material and the quality of the received waste). The results of the researches show that non-sorted bin packing algorithms cut better than bin packing sorted algorithms but the time of cutting grows longer when the number of finished products grow longer.
17
Han, Xin. "Online and approximation algorithms for bin-packing and knapsack problems." 京都大学 (Kyoto University), 2007. http://hdl.handle.net/2433/135979.
Full text
18
Junqueira, Nenina Marcia Pereira. "Algoritmos aproximados para solucionar o problema de Bin Packing unidimensional." Instituto Tecnológico de Aeronáutica, 2007. http://www.bd.bibl.ita.br/tde_busca/arquivo.php?codArquivo=375.
Full textAbstract:
Este trabalho apresenta um estudo sobre a razão assintótica de pior caso para alguns algoritmos aproximados utilizados para solucionar o problema de Bin Packing unidimensional ( BPP). Este é um problema clássico de otimização combinatória que serve de modelo para uma série de problemas que ocorrem no mundo real. No BPP, dada uma lista com n itens de tamanhos no intervalo (0,
19
Ongkunaruk, Pornthipa. "Asymptotic Worst-Case Analyses for the Open Bin Packing Problem." Diss., Virginia Tech, 2005. http://hdl.handle.net/10919/30105.
Full textAbstract:
The open bin packing problem (OBPP) is a new
variant of the well-known bin packing problem. In the OBPP, items
are packed into bins so that the total content before the last item
in each bin is strictly less than the bin capacity. The objective is
to minimize the number of bins used. The applications of the OBPP
can be found in the subway station systems in Hong Kong and Taipei
and the scheduling in manufacturing industries. We show that the
OBPP is NP-hard and propose two heuristic algorithms instead of
solving the problem to optimality. We propose two offline algorithms
in which the information of the items is known in advance. First, we
consider the First Fit Decreasing (FFD) which is a good
approximation algorithm for the bin packing problem. We prove that
its asymptotic worst-case performance ratio is no more than 3/2.
We observe that its performance for the OBPP is worse than that of
the BPP. Consequently, we modify it by adding the algorithm that the
set of largest items is the set of last items in each bin. Then, we
propose the Modified First Fit Decreasing (MFFD) as an alternative
and prove that its asymptotic worst-case performance ratio is no
more than 91/80. We conduct empirical tests to show their
average-case performance. The results show that in general, the FFD
and MFFD algorithms use no more than 33% and 1% of the number
of bins than that of optimal packing, respectively. In addition, the
MFFD is asymptotically optimal when the sizes of items are (0,1)
uniformly distributed.Ph. D.
20
Qiao, Wenxin. "An algorithm for crew scheduling problem with bin packing features." College Park, Md.: University of Maryland, 2008. http://hdl.handle.net/1903/8818.
Full textAbstract:
Thesis (M.S.) -- University of Maryland, College Park, 2008.Thesis research directed by: Dept. of Civil and Environmental Engineering . Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
21
Sim, Kevin. "Novel hyper-heuristics applied to the domain of bin packing." Thesis, Edinburgh Napier University, 2014. http://researchrepository.napier.ac.uk/Output/7563.
Full textAbstract:
Principal to the ideology behind hyper-heuristic research is the desire to increase the level of generality of heuristic procedures so that they can be easily applied to a wide variety of problems to produce solutions of adequate quality within practical timescales. This thesis examines hyper-heuristics within a single problem domain, that of Bin Packing where the benefits to be gained from selecting or generating heuristics for large problem sets with widely differing characteristics is considered. Novel implementations of both selective and generative hyper-heuristics are proposed. The former approach attempts to map the characteristics of a problem to the heuristic that best solves it while the latter uses Genetic Programming techniques to automate the heuristic design process. Results obtained using the selective approach show that solution quality was improved significantly when contrasted to the performance of the best single heuristic when applied to large sets of diverse problem instances. Although enforcing the benefits to be gained by selecting from a range of heuristics the study also highlighted the lack of diversity in human designed algorithms. Using Genetic Programming techniques to automate the heuristic design process allowed both single heuristics and collectives of heuristics to be generated that were shown to perform significantly better than their human designed counterparts. The thesis concludes by combining both selective and generative hyper-heuristic approaches into a novel immune inspired system where heuristics that cover distinct areas of the problem space are generated. The system is shown to have a number of advantages over similar cooperative approaches in terms of its plasticity, efficiency and long term memory. Extensive testing of all of the hyper-heuristics developed on large sets of both benchmark and newly generated problem instances enforces the utility of hyper-heuristics in their goal of producing fast understandable procedures that give good quality solutions for a range of problems with widely varying characteristics.
22
Ancora, Gabriele <1993>. "The three-dimensional single-bin-size bin packing problem: combining metaheuristic and machine learning approaches." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2022. http://amsdottorato.unibo.it/10476/1/tesiFrontespizioOK.pdf.
Full textAbstract:
The Three-Dimensional Single-Bin-Size Bin Packing Problem is one of the most studied problem in the Cutting & Packing category. From a strictly mathematical point of view, it consists of packing a finite set of strongly heterogeneous “small” boxes, called items, into a finite set of identical “large” rectangles, called bins, minimizing the unused volume and requiring that the items are packed without overlapping. The great interest is mainly due to the number of real-world applications in which it arises, such as pallet and container loading, cutting objects out of a piece of material and packaging design. Depending on these real-world applications, more objective functions and more practical constraints could be needed. After a brief discussion about the real-world applications of the problem and a exhaustive literature review, the design of a two-stage algorithm to solve the aforementioned problem is presented. The algorithm must be able to provide the
spatial coordinates of the placed boxes vertices and also the optimal boxes input sequence, while guaranteeing geometric, stability, fragility constraints and a reduced computational time. Due to NP-hard complexity of this type
of combinatorial problems, a fusion of metaheuristic and machine learning techniques is adopted. In particular, a hybrid genetic algorithm coupled with a feedforward neural network is used. In the first stage, a rich dataset is created starting from a set of real input instances provided by an industrial company and the feedforward neural network is trained on it. After its training, given a new input instance, the hybrid genetic algorithm is able to run using the neural network output as input parameter vector, providing as output the optimal solution. The effectiveness of the proposed works is confirmed via several experimental tests.
23
Brohm, Michael. "Analysis of Bin-packing algorithms used for steel beam cut optimazation." Thesis, University West, Department of Technology, Mathematics and Computer Science, 2004. http://urn.kb.se/resolve?urn=urn:nbn:se:hv:diva-558.
Full text
24
Jing, Chen. "Studies on Approximation Algorithms for Bin-Packing and Train Delivery Problems." 京都大学 (Kyoto University), 2016. http://hdl.handle.net/2433/215691.
Full text
25
Khanafer, Ali. "Algorithmes pour des problèmes de bin packing mono- et multi-objectif." Thesis, Lille 1, 2010. http://www.theses.fr/2010LIL10088/document.
Full textAbstract:
Le problème de bin packing consiste à déterminer le nombre minimum de conteneurs (bins) nécessaires pour ranger un ensemble d’objets. Ce problème NP- complet fait depuis de nombreuses années l’objet de multiples travaux de recherche, théoriques et pratiques. On le retrouve entre autres dans l’industrie de découpe de tissu, de l’acier, de bois et de verre. La littérature sur le problème de bin packing est riche et les algorithmes et approches de résolution sont très diverses. Cependant, les solutions proposées par ces algorithmes peuvent ne pas être utiles quand on traite des problèmes industriels réels. Dans cette thèse, nous considérons plusieurs types de contraintes liées à des incompatibilités entre objets. Ces contraintes sont inspirées de celles rencontrées lors d’une collaboration industrielle. Le sujet de recherche de cette thèse porte sur la résolution d’une variété de problèmes de bin packing. Nous nous intéressons à des bornes inférieures et supérieures pour les trois problèmes suivants : un problème de bin packing avec conflits dans lequel des relations de compatibilité sont exprimées entre les couples d’objets ; un problème de bin packing bi-objectif dans lequel deux critères sont à minimiser, le nombre de bins utilisés et le nombre de couples en conflit placés dans le même bin ; un problème de bin packing avec objets fragiles dans lequel la somme des tailles des objets placés dans un bin ne dépasse la fragilité d’aucun de ces objetsThe bin packing problem consists in minimizing the number of containers (bins) needed to place a set of objects. This NP-complete problem has been, for many years, the subject of multiple theoretical and practical researches. It appears in many industrial applications such as cutting steel, wood and glass. The literature on the bin packing problem is rich and the algorithms and resolution approaches are also very are very diversified. However, solutions offered by these algorithms may not be useful when we deal with real industrial problems. In this thesis, we consider several types of constraints such as compatibility relations between objects. These constraints are issued from real life industrial applications. The research topic of this thesis focuses on solving a variety of bin packing problems. We are interested in lower and upper bounds for three problems: a bin packing problem with conflicts in which some compatibility relations exist between pairs of objects, a problem bi-objective bin packing in which two criteria are to minimize: the number of bins used and the number of conflicting couples of objects placed in the same bin, a problem of bin packing with fragile objects in which the sum of the sizes of objects placed in a bin does not exceed the fragility of any of these objects
26
Ortmann, Frank. "Heuristics for offline rectangular packing problems." Thesis, Stellenbosch : University of Stellenbosch, 2010. http://hdl.handle.net/10019.1/3992.
Full textAbstract:
Thesis (PhD (Logistics))--University of Stellenbosch, 2010.ENGLISH ABSTRACT: Packing problems are common in industry and there is a large body of literature on the subject. Two packing problems are considered in this dissertation: the strip packing problem and the bin packing problem. The aim in both problems is to pack a speci ed set of small items, the dimensions of which are all known prior to packing (hence giving rise to an o ine problem), into larger objects, called bins. The strip packing problem requires packing these items into a single bin, one dimension of which is unbounded (the bin is therefore referred to as a strip). In two dimensions the width of the strip is typically speci ed and the aim is to pack all the items into the strip, without overlapping, so that the resulting packing height is a minimum. The bin packing problem, on the other hand, is the problem of packing the items into a speci ed set of bins (all of whose dimensions are bounded) so that the wasted space remaining in the bins (which contain items) is a minimum. The bins may all have the same dimensions (in which case the problem is known as the single bin size bin packing problem), or may have di erent dimensions, in which case the problem is called the multiple bin size bin packing problem (MBSBPP). In two dimensions the wasted space is the sum total of areas of the bins (containing items) not covered by items. Many solution methodologies have been developed for above-mentioned problems, but the scope of the solution methodologies considered in this dissertation is restricted to heuristics. Packing heuristics follow a xed set of rules to pack items in such a manner as to nd good, feasible (but not necessarily optimal) solutions to the strip and bin packing problems within as short a time span as possible. Three types of heuristics are considered in this dissertation: (i) those that pack items into levels (the heights of which are determined by the heights of the tallest items in these levels) in such a manner that all items are packed along the bottom of the level, (ii) those that pack items into levels in such a manner that items may be packed anywhere between the horizontal boundaries that de ne the levels, and (iii) those heuristics that do not restrict the packing of items to levels. These three classes of heuristics are known as level algorithms, pseudolevel algorithms and plane algorithms, respectively. A computational approach is adopted in this dissertation in order to evaluate the performances of 218 new heuristics for the strip packing problem in relation to 34 known heuristics from the literature with respect to a set of 1 170 benchmark problem instances. It is found that the new level-packing heuristics do not yield signi cantly better solutions than the known heuristics, but several of the newly proposed pseudolevel heuristics do yield signi cantly better results than the best of the known pseudolevel heuristics in terms of both packing densities achieved and computation times expended. During the evaluation of the plane algorithms two classes of heuristics were identi ed for packing problems, namely sorting-dependent and sortingindependent algorithms. Two new sorting techniques are proposed for the sorting-independent algorithms and one of them yields the best-performing heuristic overall. A new heuristic approach for the MBSBPP is also proposed, which may be combined with level and pseudolevel algorithms for the strip packing problem in order to nd solutions to the problem very rapidly. The best-performing plane-packing heuristic is modi ed to pack items into the largest bins rst, followed by an attempted repacking of the items in those bins into smaller bins with the aim of further minimising wasted space. It is found that the resulting plane-packing algorithm yields the best results in terms of time and packing density, but that the solution di erences between pseudolevel algorithms are not as marked for the MBSBPP as for the strip packing problem.
AFRIKAANSE OPSOMMING: Inpakkingsprobleme kom algemeen in die industrie voor en daar is 'n aansienlike volume literatuur oor hierdie onderwerp. Twee inpakkingsprobleme word in hierdie proefskrif oorweeg, naamlik die strook-inpakkingsprobleem en die houer-inpakkingsprobleem. In beide probleme is die doel om 'n gespesi seerde versameling klein voorwerpe, waarvan die dimensies almal voordat inpakking plaasvind, bekend is (en die probleem dus 'n sogenaamde a yn-probleem is), in een of meer groter houers te pak. In die strook-inpakkingsprobleem word hierdie voorwerpe in een houer, waarvan een dimensie onbegrens is, ingepak (hierdie houer word dus 'n strook genoem). In twee dimensies word die wydte van die strook gewoonlik gespesi seer en is die doel om al die voorwerpe sonder oorvleueling op s o 'n manier in die strook te pak dat die totale inpakkingshoogte geminineer word. In die houer-inpakkingsprobleem, daarenteen, is die doel om die voorwerpe op s o 'n manier in 'n gespesi seerde aantal houers (waarvan al die dimensies begrens is) te pak dat die vermorste of oorblywende ruimte in die houers (wat wel voorwerpe bevat) 'n minimum is. Die houers mag almal dieselfde dimensies h^e (in welke geval die probleem as die enkelgrootte houer-inpakkingsprobleem bekend staan), of mag verskillende dimensies h^e (in welke geval die probleem as die veelvuldige-grootte houer-inpakkingsprobleem bekend staan, afgekort as VGHIP). In twee dimensies word die vermorste ruimte geneem as die somtotaal van daardie deelareas van die houers (wat wel voorwerpe bevat) waar daar geen voorwerpe geplaas word nie. Verskeie oplossingsmetodologie e is al vir die bogenoemde twee inpakkingsprobleme ontwikkel, maar die bestek van die metodologie e wat in hierdie proefskrif oorweeg word, word beperk tot heuristieke. 'n Inpakkingsheuristiek volg 'n vaste stel re els waarvolgens voorwerpe in houers gepak word om so spoedig moontlik goeie, toelaatbare (maar nie noodwendig optimale) oplossings tot die strook-inpakkingsprobleem en die houer-inpakkingsprobleem te vind. Drie tipes inpakkingsheuristieke word in hierdie proefskrif oorweeg, naamlik (i) heuristieke wat voorwerpe langs die onderste randte van horisontale vlakke in die houers pak (die hoogtes van hierdie vlakke word bepaal deur die hoogtes van die hoogste item in elke vlak), (ii) heuristieke wat voorwerpe op enige plek binne horisontale stroke in die houers pak, en (iii) heuristieke waar inpakking nie volgens horisontale vlakke of stroke beperk word nie. Hierdie drie klasse heuristieke staan onderskeidelik as vlakalgoritmes, pseudo-vlakalgoritmes en platvlakalgoritmes bekend. 'n Berekeningsbenadering word in hierdie proefskrif gevolg deur die werkverrigting van die 218 nuwe heuristieke vir die strook-inpakkingsprobleem met die werkverrigting van 34 bekende heuristieke uit die literatuur te vergelyk, deur al die heuristieke op 1 170 toetsprobleme toe te pas. Daar word bevind dat die nuwe vlakalgoritmes nie 'n noemenswaardige verbetering in oplossingskwaliteit in vergeleke met soortgelyke bestaande algoritmes in die literatuur lewer nie, maar dat verskeie nuwe pseudo-vlakalgoritmes wel noemenswaardige verbeteringe in terme van beide inpakkingsdigthede en oplossingstye in vergeleke met die beste bestaande algoritmes in die literatuur lewer. Assessering van die platvlakalgoritmes het gelei tot die identi kasie van twee deelklasse van algoritmes, naamlik sorteringsafhanklike- en sorteringsonafhanklike algoritmes. Twee nuwe sorteringstegnieke word ook vir die deelklas van sorteringsonafhanklike algoritmes voorgestel, en een van hulle lewer die algeheel beste inpakkingsheursitiek. 'n Nuwe heuristiese benadering word ook vir die VGHIP ontwikkel. Hierdie benadering kan met vlak- of pseudo-vlakalgoritmes vir die strook-inpakkingsprobleem gekombineer word om baie vinnig oplossings vir die VGHIP te vind. Die beste platvlakheuristiek vir die strookinpakkingsprobleem word ook aangepas om voorwerpe eers in die grootste houers te pak, en daarna in kleiner houers te herpak met die doel om vermorste ruimte verder te minimeer. Daar word bevind dat die resulterende platvlakalgoritme die beste resultate in terme van beide inpakkingsdigtheid en oplossingstyd lewer, maar dat oplossingsverskille tussen die pseudovlakalgoritmes nie so opmerklik vir die VGHIP is as wat die geval met die strookinpakkingsprobleem was nie.
27
Lemos, Felipe Kesrouani. "Problema de programação de uma operação de empacotamento não-guilhotinado em ambiente de máquina única, minimizando custos de matéria-prima e desvio de datas: formulação e solução heurística." Universidade de São Paulo, 2013. http://www.teses.usp.br/teses/disponiveis/3/3136/tde-11072014-121631/.
Full textAbstract:
A presente pesquisa tem como objetivo estudar a integração entre dois temas clássicos da literatura de pesquisa operacional e gestão de operações: problemas de corte e empacotamento; e problemas de programação da produção. Ainda que sejam duas áreas intensamente exploradas e pesquisadas, e, ainda, que seja uma situação facilmente encontrada em sistemas de produção reais, abordagens de ambos problemas de forma coordenada ainda carecem de maiores pesquisas. Neste trabalho é feita uma revisão de ambos temas, com foco em problemas de bin packing e programação em ambiente de máquina única com objetivo de minimizar soma de atrasos e adiantamentos ponderados. Uma formulação matemática linear e inteira mista é proposta para o problema, contemplando as restrições que concernem a cada um e também à sua consideração simultânea. Como se trata de um problema que une dois outros, cada um NP-hard isoladamente, um método heurístico é proposto para obter uma solução interessante em tempos computacionais bastante reduzidos. Foram obtidas propriedades físicas de definição de data ideal de programação de um conjunto de itens atribuídos a um bin. Também é proposto um método para geração de um limitante inferior melhorado em relação a pacotes de otimização de mercado para o problema. Ambos métodos foram testados em uma massa de dados de 1.152 instâncias, geradas para retratar cenários de diferentes datas de entrega, setups, custos de atraso e adiantamento em relação à matéria-prima, tamanho de itens e número de itens na instância. Os resultados mostram-se largamente superiores aos obtidos por um otimizador genérico (CPLEX), embora ainda sejam gaps excessivamente grandes, o que reforça a dificuldade do problema.The present research aims to explore the integration between two classic themes on operations research and operations management literature: cutting and packing problems; and production scheduling problems. Although they are intensive explored and researched areas and, besides, it\'s an easily found situation on real production systems, coordinated approaches of both themes still need deeper research. On this paper, it was done a review of both themes, focusing on bin packing problems and single-machine environment scheduling problems aiming to minimize total weighed earliness and tardiness. A mixed integer-linear mathematical formulation is proposed to the problem, including constraints referred to each problem and, also, to their simultaneous consideration. Once it\'s a problem that joins the other two, each one NP-hard solely, an heuristic method is proposed to obtain an interesting solution in reasonable computational times. Physical properties were identified, defining the best date to allocate a given lot of items to be processed together. Also, a lower bound generation method is proposed, improving the one generated by optimization softwares. Both methods were tested on a 1.152 instances mass of data, generated to represent well several scenarios of different due dates, setup times, earliness and tardiness costs compared to raw material, size of items and number the items the instance. Results show largely superiority the ones obtained by an optimization pack (CPLEX), although gaps are still excessively large, fact the reinforces problem\'s difficulty.
28
Aquino, Henrique Otávio Queiroz de. "Uma aplicação do algoritmo genético construtivo ao problema de "BIN-PACKING" unidimensional." Instituto Nacional de Pesquisas Espaciais (INPE), 1998. http://urlib.net/sid.inpe.br/mtc-m18@80/2009/05.14.19.18.
Full textAbstract:
Esta dissertação de mestrado tem como objetivo aplicar um método heurístico denominado Algoritmo Genético Construtivo (AGC), ao Problema de Bin Packing Unidimensional (PBP). Verificamos que através da heurística podemos gerar, combinar e selecionar uma população de esquemas (blocos construtivos) do problema, de modo que se consiga construir uma solução ótima ou, ao menos, se aproximar do menor número de caixas (bins) para distribuir e empacotar cada unidade de vários itens dados. O processo parte de uma população inicial de esquemas, através da distribuição aleatória de itens em uma certa quantidade de caixas estimada a partir de um número mínimo, conhecido como número teórico, previamente calculado. O número de caixas estimado deve, portanto, ser maior que o número teórico e posteriormente diminuído. A heurística apresenta junto aos esquemas, propriedades do problema em estudo, o que permite se fazer avaliações, determinando o quão promissor é cada um. Os esquemas são então avaliados diretamente através de funções apropriadas, sendo que os melhores são incentivados a se recombinar com outros para gerar novos esquemas ou estruturas completas. As estruturas que não conseguem obter boa avaliação são eliminadas da população, conforme a determinação de um critério de poda. Ao final do processo, estruturas de qualidade superior são obtidas. Neste trabalho, as aplicações são realizadas utilizando-se instâncias do PBP de diferentes tipos e tamanhos. Aplicamos também o AGC sobre instâncias de um Problema de (Scheduling). Os resultados são mostrados e comparados com os de outras heurísticas ("First-Fit Decreasing" - FFD e "Longest-Processing Time" - LPT ). Por fim, as conclusões, acompanhadas de algumas sugestões são apresentadas.This dissertation has as objective to apply a method heuristic denominated Constructive Genetic Algorithm (AGC), to Unidimensional Bin-Packing Problem ( BPP ). We verified that through the heuristic we can generate, to combine and to select a population of schemas (building blocks) of the problem, so that it gets to build a optimal solution or, at least, to approach of the smallest number of bins to distribute and to pack each one of several items data. The process part of an initial population of schemas through the aleatory distribution of items in a certain amount of bins starting from a minimum number, well-known as theoretical number, previously calculated. The heuristic presents the schemas that carries information about properties of the problem in study, what allows to do evaluations, determining the as promising it is each one. The schemas are then directly appraised through appropriate functions, and the best are stimulated to recombine with others to generate new schemas or complete structures. The structures that dont get to obtain good evaluation are eliminated of the population, according to the determination of a pruning approach. At the end of the process, structures of superior quality are obtained. In this work, the applications are accomplished being used instances of BPP of different types and sizes. We also applied AGC 011 instances of a Problem of Scheduling. Results are shown for instances from the literature using a microcomputer implementation and significant conclusions are described.
29
Milevičius, Vilimantas. "Dėžių pakavimo su papildomu apribojimu optimizavimo algoritmo sudarymas ir tyrimas." Master's thesis, Lithuanian Academic Libraries Network (LABT), 2007. http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2007~D_20070816_144408-66957.
Full textAbstract:
Šio darbo tikslas – sukurti trimačių dėžių su papildomu orientacijos erdvėje apribojimu pakavimo optimizavimo algoritmą, o realizavus jį programinėmis priemonėmis – ištirti jo efektyvumą su atsitiktinai sugeneruotų kraunamų dėžių rinkiniais ir prie skirtingų algoritmo veikimo parametrų. Taip pat sukurti ir pakavimo optimizavimo sprendinio vizualizavimo trimatėje erdvėje programinę įrangą.Presented work covers one of the most complex areas of combinatorial optimization – three dimensional bin packing problem. Solution methods of this problem are applied in the real world from logistics, packing optimization to VLSI circuit and automobile engineering. Several heuristic packing algorithms suggested by other authors are analyzed. Approach based on tree-search and wall building strategy is chosen to create a 3D packing optimization algorithm. A bin orientation in space restriction is added to classical 3D bin packing problem to make it more complex and more suited for real world applications. A prototype of created algorithm is created and tested with randomly generated data collections. Each data sample is processed with and without bin orientation in space restriction. Influence of restriction and maximal tree width on packing efficiency and computational time is statistically analyzed. Visualization tool based on Microsoft Direct X technology is created to view results of packing optimization.
30
Ataki, Adel. "Wetting of structured packing elements CFD and Experiment /." [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=981239463.
Full text
31
Želvytė, Lina. "3D objektų pakavimo metodai ir programinė įranga." Master's thesis, Lithuanian Academic Libraries Network (LABT), 2004. http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2004~D_20040525_175607-32032.
Full textAbstract:
The essence of 3D object packing problem is to load a set of distinct boxes with given dimensions in containers to maximize volume utilization. The goal of this research is to support with algorithmic techniques the design of package layouts that meet the functional relationships between the parts and match market needs including cost, safety, comfort, as well as economic and environmental aspects. An analysis of 3D object packing algorithms, created by foreign authors, and commercial three-dimensional pallet packing software packages was performed in this work; also methods’ advantages and disadvantages were pointed out. A model of three-dimensional rectangular object packing into containers of the same shape was formed, and the software solving 3D object packing problems was created according to this model. The tests proved that the suggested method is effective and beneficial.
32
Heydrich, Sandy [Verfasser], and Rob van [Akademischer Betreuer] Stee. "A tale of two packing problems : improved algorithms and tighter bounds for online bin packing and the geometric knapsack problem / Sandy Heydrich ; Betreuer: Rob van Stee." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2018. http://d-nb.info/1164012193/34.
Full text
33
Fischer, Carsten Oliver [Verfasser]. "New Results on the Probabilistic Analysis of Online Bin Packing and its Variants / Carsten Oliver Fischer." Bonn : Universitäts- und Landesbibliothek Bonn, 2019. http://d-nb.info/120172791X/34.
Full text
34
Casazza, Marco. "Algorithms for Optimization Problems with Fractional Resources." Thesis, Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCD048/document.
Full textAbstract:
Dans cette thèse nous considérons une classe de problèmes d’optimisation ayant une particularité : des décisions à la fois discrètes et continues doivent être prises simultanément. Ces problèmes se posent dans de nombreuses applications pratiques, comme par exemple dans les réseaux de télécommunications à large bande passante et dans les problèmes de transport écologique, où les ressources disponibles peuvent être très légèrement consommées ou réparties. Ces problèmes se sont avérés être plus difficiles à résoudre que leurs homologues purement discrets. Des méthodes efficaces pour la résolution de ces problèmes sont proposées dans cette thèse. Notre approche est de prendre en compte des variantes de problèmes classiques d’optimisation combinatoire appartenant à trois domaines : packing, routage et routage/ packing intégré. Les résultats obtenus suggèrent l’existence de méthodes efficaces, réduisant l’effort de calcul nécessaire pour résoudre ce type de problème. La plupart du temps, ces méthodes sont basées sur l’exploitation de la structure des solutions optimales pour réduire l’espace de rechercheIn this thesis we consider a class of optimization problems having adistinctive feature : both discrete and continuous decisions need to betaken simultaneously. These problems arise in many practical applications,for example broadband telecommunications and green transportation problems, where resources are available, that can be fractionally consumed or assigned. These problems are proven of being harder than their purely discrete counterpart. We propose effective methodologies to tackle them. Our approach is to consider variants of classical combinatorial optimization problems belonging to three domains : packing, routing, and integrated routing / packing. Our results suggest that indeed effective approaches exist, reducing the computational effort required for solving the problem. Mostly, they arebased on exploiting the structure of optimal solutions to reduce the search space
In questa tesi affrontiamo una classe di problemi di ottimizzazione con una caratteristica in comune : sia le decisioni discrete che quelle continue devono essere prese simultaneamente. Questi problemi emergono in molti campi, come ad esempio le nelle telecomunicazioni abanda larga e in problemi di trasporto ecologico, dove le risorse disponibili possono essere consumate o assegnate in modo frazionario.Questi problemi sono generalmente più difficili da risolvere rispetto alla loro controparte puramente combinatoria. Noi proponiamo metodologie efficaci per affrontarli. Con il nostro approccio consideriamo varianti di problemi classici nel campo dell’ottimizzazione combinatoriache appartengono a tre domini : impaccamento, instradamento einstradamento / impaccamento integrati. I nostri risultati suggeriscono l’esistenza di approcci efficienti che riducono lo sforzo computazionale necessario per risolvere questi problemi. Nella maggior parte deicasi, tali approcci sono basati sullo sfruttamento di particolari proprietà della struttura delle soluzioni ottime in modo da ridurre lo spaziodi ricerca
35
Clautiaux, François. "Bornes inférieures et méthodes exactes pour le problème de bin packing en deux dimensions avec orientation fixe." Phd thesis, Université de Technologie de Compiègne, 2005. http://tel.archives-ouvertes.fr/tel-00749411.
Full textAbstract:
Notre problème consiste à déterminer le nombre de grands rectangles identiques nécessaires pour ranger une liste de rectangles sans modifier leur orientation. Nous proposons des méthodes pour calculer des bornes inférieures pour ce problème, essentiellement basée sur le concept de fonctions dual-réalisables. Nous proposons aussi deux méthodes exactes de type énumératives. L'une permet de déterminer si un ensemble de rectangles peut être contenu dans un rectangle unique. Elle repose sur une nouvelle relaxation du problème. La deuxième méthode permet de résoudre le problème général de bin packing en deux dimensions. Elle calcule pour cela une décomposition itérative de l'ensemble des rectangles à placer.
36
El, Hayek Joseph. "Le problème de bin-packing en deux-dimensions, le cas non-orienté : résolution approchée et bornes inférieures." Phd thesis, Université de Technologie de Compiègne, 2006. http://tel.archives-ouvertes.fr/tel-00158728.
Full textAbstract:
Notre travail porte sur le problème de bin-packing qui consiste à déterminer le nombre minimum de grands rectangles (bins) nécessaires pour ranger un ensemble de petits rectangles (objets). Ce problème d'optimisation combinatoire est NP-difficile au sens fort. Nous proposons des prétraitements des objets permettant la valorisation des espaces perdus dans les bins et la diminution de la taille du problème à résoudre. Nous proposons une nouvelle méthode d'évaluation de bornes inférieures tenant compte de la possibilité de tourner les objets de 90 degrés. Nous procédons à une résolution approchée du problème grâce à deux nouvelles méthodes : une heuristique et un algorithme de recherche tabou.
37
Loh, Kok-Hua. "Weight annealing heuristics for solving bin packing and other combinatorial optimization problems concepts, algorithms and computational results /." College Park, Md. : University of Maryland, 2006. http://hdl.handle.net/1903/3980.
Full textAbstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2006.Thesis research directed by: Business and Management. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
38
ALVIM, ADRIANA CESARIO DE FARIA. "A HYBRID IMPROVEMENT HEURISTICS FOR THE BIN PACKING PROBLEM AND ITS APPLICATION TO THE PROBLEM OF TASK SCHEDULING." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2003. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=4364@1.
Full textAbstract:
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICOA principal contribuição desta tese consiste no desenvolvimento de uma heurística híbrida, robusta e eficiente, para o problema de empacotamento unidimensional. A heurística proposta utiliza os seguintes componentes: limites inferiores e superiores do número de caixas; reduções; abordagem dual para a obtenção de soluções iniciais; heurísticas para redistribuição dos pesos; e busca tabu. O outro objetivo desta tese é a aplicação desta heurística para a solução do problema de escalonamento em processadores paralelos idênticos. São apresentados resultados computacionais obtidos sobre centenas de problemas testes da literatura.
We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several components: lower and upper bounds; reductions, construction of initial solutions by reference to the dual problem;heuristics for load redistribution based on dominance, differencing, and unbalancing; and tabu search. We also investigate the application of this hybrid heuristic to the problem of task scheduling on identical parallel processors. Computational results on hundreds of benchmark test problem are presented.
39
Ražas, Artūras. "Dėžių pakavimo trimatėje erdvėje algoritmas ir jo taikymas logistikos uždaviniams spręsti." Master's thesis, Lithuanian Academic Libraries Network (LABT), 2006. http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2006~D_20060531_104235-31546.
Full textAbstract:
Whether you are in industrial manufacturing striving to optimize your supply chain, international or domestic carrier committed to lower your operational costs, retailer dedicated to run your distribution network more efficiently, or anywhere else where the words "cargo", "freight", "shipment" are in your business language, automated load planning and optimization will significantly improve your business process. While the concept of computerized simulation of 3D load building is not new, with some companies offering software solutions for "virtual" loading, no one has a single product that is capable to handle complex variety of business rules and constraints of the modern transportation industry. We are analyzing the problems related with 3D box loading and then to analyze existing 3D load building systems. After accumulating all analyzes data we are having enough experience to create our own algorithm. And we did it! We create 3D box loading algorithm witch is fast and accurate and 3D box loading system which is using this new algorithm. To ensure that we succeeded we compare this new system with existing 3D box loading software to make sure that it’s really useful for solving logistic problems. After testing we are sure that we made a big job and we have created system, which can compete with the logistic IT leaders made solutions.
40
Asgeirsson, Agni. "On-line algorithms for bin-covering problems with known item distributions." Diss., Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/53413.
Full textAbstract:
This thesis focuses on algorithms solving the on-line Bin-Covering problem, when
the items are generated from a known, stationary distribution. We introduce the
Prospect Algorithm. The main idea behind the Prospect Algorithm is to use
information on the item distribution to estimate how easy it will be to fill a bin with small overfill as a function of the empty space left in it. This estimate is then used to determine where to place the items, so that all active bins either stay easily fillable, or are finished with small overfill. We test the performance of the algorithm by simulation, and discuss how it can be modified to cope with additional constraints and extended to solve the Bin-Packing problem as well. The Prospect Algorithm is then adapted to achieve perfect packing, yielding a new version, the Prospect+ Algorithm, that is a slight but consistent improvement. Next, a Markov Decision Process formulation is used to obtain an optimal Bin-Covering algorithm to compare with the Prospect Algorithm. Even though the optimal algorithm can only be applied to limited (small) cases, it gives useful insights that lead to another modification of the Prospect Algorithm. We also discuss two relaxations of the on-line constraint, and describe how algorithms that are based on solving the Subset-Sum problem are used to
tackle these relaxed problems. Finally, several practical issues encountered when using the Prospect Algorithm in the real-world are analyzed, a computationally efficient way of doing the background calculations needed for the Prospect Algorithm is described, and the three versions of the Prospect Algorithm developed in this thesis are compared.
41
Tuenter, Hans J. H. "Worst-case bounds for bin-packing heuristics with applications to the duality gap of the one-dimensional cutting stock problem." Thesis, University of Birmingham, 1997. http://etheses.bham.ac.uk//id/eprint/266/.
Full textAbstract:
The thesis considers the one-dimensional cutting stock problem, the bin-packing problem, and their relationship. The duality gap of the former is investigated and a characterisation of a class of cutting stock problems with the next round-up property is given. It is shown that worst-case bounds for bin-packing heuristics can be and are best expressed in terms of the linear programming relaxation of the corresponding cutting stock problem. The concept of recurrency is introduced for a bin-packing heuristic, which allows a more natural derivation of a measure for the worst-case behaviour. The ideas are tested on some well known bin-packing heuristics and (slightly) tighter bounds for these are derived. These new bounds (in terms of the linear programming relaxation) are then used to make inferences about the duality gap of the cutting stock problem. In particular; these bounds allow à priori, problem-specific bounds. The thesis ends with conclusions and a number of suggestions to extend the analysis to higher dimensional problems.
42
Sannia, Giacomo. "Ottimizzazione di un sistema di pallettizzazione. Il caso IRSAP." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2020.
Find full textAbstract:
Il processo di pallettizzazione dei prodotti all'interno delle realtà industriali è stato riconosciuto negli ultimi decenni come un valore aggiunto se ottimizzato al meglio. Più i prodotti sono disposti in modo ordinato e stabile sui bancali, più la saturazione volumetrica cresce e ciò che ne consegue è una riduzione del numero di pallet totali necessari. Allo stesso tempo ottimizzare il processo di pallettizzazione coinvolge anche l'aspetto dei tempi richiesti da tutte le operazioni collegate; spesso molte realtà industriali presentano sprechi e attività non necessarie che allungano inutilmente il processo.
Lo scopo di questa tesi è quello di studiare il sistema di pallettizzazione dell’azienda IRSAP spa, individuarne le criticità e trovare delle soluzioni ottimizzanti. Nel corso della discussione verranno presentati due software di pallettizzazione e ne verranno analizzati i punti di forza e di debolezza. È inoltre presente un confronto tra la soluzione attuale proposta dall’azienda e le soluzioni ottenibili grazie all’adozione di questi software. Il confronto è stato costruito attorno allo studio di un caso aziendale costituente un ordine di spedizione di grandi dimensioni, da cui sono stati ricavati i parametri necessari alla valutazione delle performance delle varie proposte.
Dopo un giudizio complessivo finale, è emerso come le potenzialità di questi software possano innovare concretamente il modo di approcciarsi al mondo della logistica, velocizzando le operazioni e riducendo il numero di persone coinvolte.
43
Klement, Nathalie. "Planification et affectation de ressources dans les réseaux de soin : analogie avec le problème du bin packing, proposition de méthodes approchées." Thesis, Clermont-Ferrand 2, 2014. http://www.theses.fr/2014CLF22517/document.
Full textAbstract:
Les travaux de thèse présentés s’intéressent à l’optimisation des systèmes hospitaliers. Une solution existante est la mutualisation de ressources au sein d’un même territoire. Cela peut passer par différentes formes de coopération dont la Communauté Hospitalière de Territoire. Différents problèmes sont définis en fonction du niveau de décision : stratégique, tactique ou opérationnel ; et du niveau de modélisation : macroscopique, mesoscopique et microscopique. Des problèmes de dimensionnement, de planification et d’ordonnancement peuvent être considérés. Nous définissons notamment le problème de planification d’activités avec affectation de ressources. Plusieurs cas sont dissociés : soit les ressources humaines sont à capacité infinie, soit elles sont à capacité limitée et leur affectation sur site est une donnée, soit elles sont à capacité limitée et leur affectation sur site est une variable. Ces problèmes sont spécifiés et formalisés mathématiquement. Tous ces problèmes sont comparés à un problème de bin packing : le problème du bin packing de base pour le problème où les ressources humaines sont à capacité infinie, le problème du bin packing avec interdépendances dans les deux autres cas. Le problème du bin packing avec incompatibilités est ainsi défini. De nombreuses méthodes de résolution ont déjà été proposées pour le problème du bin packing. Nous faisons plusieurs propositions dont un couplage hiérarchique entre une heuristique et une métaheuristique. Des métaheuristiques basées individu et une métaheuristique basée population, l’optimisation par essaim particulaire, sont utilisées. Cette proposition nécessite un nouveau codage inspiré des problèmes de permutation d’ordonnancement. Cette méthode donne de très bons résultats sur les instances du problème du bin packing. Elle est simple à appliquer : elle couple des méthodes déjà connues. Grâce au couplage proposé, les nouvelles contraintes à considérer nécessitent d’être intégrées uniquement au niveau de l’heuristique. Le fonctionnement de la métaheuristique reste le même. Ainsi, notre méthode est facilement adaptable au problème de planification d’activités avec affectation de ressources. Pour les instances de grande taille, le solveur utilisé comme référence ne donne qu’un intervalle de solutions. Les résultats de notre méthode sont une fois encore très prometteurs : les solutions obtenues sont meilleures que la borne supérieure retournée par le solveur. Il est envisageable d’adapter notre méthode sur d’autres problèmes plus complexes par intégration dans l’heuristique des nouvelles contraintes à considérer. Il serait notamment intéressant de tester ces méthodes sur de réelles instances hospitalières afin d’évaluer leur portéeThe presented work is about optimization of the hospital system. An existing solution is the pooling of resources within the same territory. This may involve different forms of cooperation between several hospitals. Various problems are defined at the decision level : strategic, tactical or operational ; and at the modeling level : macroscopic, mesoscopic and microscopic. Problems of sizing, planning and scheduling may be considered. We define the problem of activities planning with resource allocation. Several cases are dissociated : either human resources are under infinite capacity, or they are under limited capacity and their assignment on a place is given, or they are under limited capacity and their assignment is a variable. These problems are specified and mathematically formalized. All thes problems are compared to a bin packing problem : the classical problem of bin packing is used for the problem where human resources are under infinite capacity, the bin packing problem with interdependencies is used in the two other cases. The bin packing problem with incompatibilities is defined. Many resolution methods have been proposed for the bin packing problem. We make several propositions including a hierarchical coupling between heuristic and metaheuristic. Single based metaheuristics and a population based metaheuristic, the particle swarm optimization, are used. This proposition requires a new encoding inspired by permutation problems. This method gives very good results to solve instances of the bin packing problem. It is easy to apply : it combines already known methods. With the proposed coupling, the new constraints to be considered need to be integrated only on the heuristic level. The running of the metaheuristic is the same. Thus, our method is easily adaptable to the problem of activities planning with resource allocation. For big instances, the solver used as a reference returns only an interval of solutions. The results of our method are once again very promising : the obtained solutions are better than the upper limit returned by the solver. It is possible to adapt our method on more complex issues through integration into the heuristic of the new constraints to consider. It would be particularly interesting to test these methods on real hospital authorities to assess their significance
44
Silva, Raquel Akemi Okuno Kitazume da. "Empacotamento de itens irregulares considerando balanceamento da carga." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-05102017-170921/.
Full textAbstract:
O problema de empacotamento de itens irregulares com balanceamento da carga é encontrado no carregamento de aviões, caminhões e navios. O objetivo é empacotar itens irregulares utilizando o menor número de recipientes possível de forma que os recipientes estejam balanceados, que os itens não se sobreponham e estejam inteiramente contidos no recipiente. Neste trabalho, propomos três heurísticas bases com três variações cada para o problema com recipientes retangulares e irregulares. As heurísticas utilizam abordagens diferentes para representar os itens e para fazer o balanceamento. Uma das heurísticas utiliza malha para representação dos itens e faz o balanceamento dividindo o recipiente em quadrantes e revezando a alocação dos itens entre eles de forma que o balanceamento é feito de forma indireta. Tal heurística resolve o problema tanto para recipientes retangulares quanto irregulares. A segunda heurística utiliza a representação dos itens por polígonos e impossibilita a sobreposição de itens utilizando a técnica do nofit polygon. A heurística constrói a solução item por item, sem posições fixas e a cada item alocado, os itens são deslocados em direção ao centro de gravidade desejado do recipiente. Esta heurística resolve apenas problemas com recipientes retangulares. A última heurística é uma adaptação da heurística anterior para a resolução do problema com recipientes irregulares, de forma que o problema é resolvido em duas fases. Cada heurística base possui três variações cada, totalizando nove heurísticas. As heurísticas foram comparadas com outro trabalho da literatura e conseguiram melhorar os resultados para nove das dezenove instâncias testadas.The irregular bin packing problem with load balancing is found in the loading of airplanes, trucks and ships. The aim is to use as few bins as possible to pack all the items so that all bins are balanced, items do not overlap and are fully contained in the bin. In this work, we propose three base heuristics with three variations each for the problem with rectangular and irregular bin. The three heuristics use different approaches to represent the items and to balance the bin. One of the heuristics uses a grid to represent the items and does the balancing by dividing the container into quadrants and alternating the allocation of items between them so that the balancing is done indirectly. Such heuristic solves the problem for both rectangular and irregular bins. The second heuristic uses the representation of items by polygons and uses the nofit polygon technique. The heuristic constructs the solution item by item, with no fixed positions and with each item allocated, the items are shifted towards the desired center of gravity of the bin. This heuristic only solves problems with rectangular bins. The last heuristic is an adaptation of the previous one to solve the problem with irregular bins, so that the problem is solved in two phases. Each base heuristic has three variations, totaling nine heuristics. The heuristics were compared with other work in the literature and managed to improve the results for nine of the nineteen instances tested.
45
Pereira, Robson Edvaldo da Silva. "Álgebra linear: secções cônicas e aplicações." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/55/55136/tde-25092017-161410/.
Full textAbstract:
Neste trabalho desenvolvemos o estudo da álgebra linear, secções cônicas e aplicações. Apresentamos os conceitos mais importantes da álgebra linear, estudando os espaços vetorias, subespaços vetoriais, matriz de mudança de base, transformações lineares e produto interno. O principal resultado do trabalho é o teorema espectral que fornece ferramentas para se estudar as secções cônicas não elementares, ou seja, aquelas nas quais uma parábola, elipse ou hipérbole são apresentadas com seus eixos não paralelos aos eixos coordenados do plano cartesiano. Uma vez de posse deste teorema é mostrado um processo prático no qual transformamos uma equação ax2 +bxy +cy2 +dx +ey + g = 0 na equação k1 (x\')2 + k2 (y\')2 + (dx1 + ey1) x\' + (dx2 + ey2) y\' + g = 0 sem o termo misto xy, onde após a eliminação deste, podemos deduzir a equação da cônica identificando assim esta curva. Apresentamos exemplos de cônicas com eixos paralelos e não paralelos aos coordenados do plano cartesiano e utilizamos o software geogebra para visualização. Também discutimos algumas aplicações das cônicas como trajetória de corpos celestes (planeta Terra e um cometa), princípio de reflexão da parábola mostrando o porquê das antenas e dos captadores de ondas sonoras serem parabólicos. Demonstramos um teorema que denominei de identificador de uma curva cônica pois com ele é possível classificar a cônica sem realizar o processo prático, apenas para isso identificamos através da equação ax2 +bxy + cy2 +dx + ey +g = 0, quais os valores de a;b e c e feito isto calculamos o discriminante b2 - 4ac, analisamos os sinais e a nulidade, ou seja, se é maior que zero, menor que zero ou igual a zero, assim é possível classificar a cônica.The paper develops the study of linear algebra, conic sections and applications. I present the most important concepts of linear algebra, studying vector spaces, vector subspaces, base change matrix, linear transformations, internal product. The main result of the work is the spectral theorem, which provides tools to study the non-elementary conic sections, that is, those in which a parabola, ellipse or hyperbola are presented with their axes not parallel to the cartesian planes coordinate axes. Using this theorem we show a practical process in which we transform an equation ax2 +bxy + cy2 +dx +ey +g = 0 into the equation k1 (x\')2 +k2 (y\')2 + (dx1 +ey1) x\' (dx2 + ey2) y\' +g = 0 without the mixed term xy, where after its elimination we can deduce the conic equation thus identifying the curve we are looking for. I present examples of conic with parallel and non-parallel axes to the coordinates of the Cartesian plane and use the geogebra software for visualization. I discuss some applications of the conic as a trajectory of celestial bodies (planet Earth and a comet), principle of reflection of parabola showing why the antennas and sound wave pickups are parabolics. I demonstrate a theorem that I named the identifier of a conic curve, with it it is possible to classify the conic without realizing the practical process only for this. I identify through the equation ax2 +bxy + cy2 +dx + ey + g = 0, what are the values of a;b, and c and, with this done, I compute the discriminant b2 - 4ac and analyze the signs and the nullity, that is, if it is greater than zero, less than zero or equal to zero, therefore is possible to classify the conic.
46
Antomarchi, Anne-Lise. "Conception et pilotage d'un atelier intégrant la fabrication additive." Thesis, Université Clermont Auvergne (2017-2020), 2019. http://www.theses.fr/2019CLFAC035/document.
Full textAbstract:
La fabrication additive est un domaine en plein essor. Cependant, les industriels sont aujourd’hui dans une phase d’interrogation sur l’utilisation de ce procédé dans le cadre d’une production de masse. La problématique posée dans le cadre de ces travaux de recherche est : Comment rendre viable, industriellement, le procédé de fusion sur lit de poudre ? Nos travaux abordent la conception et le pilotage d’ateliers intégrant la fabrication additive et le processus complet d’obtention de la pièce selon les trois niveaux de décision : stratégique, tactique et opérationnel. D’un point du vue stratégique, des décisions fortes d’investissement, de sélection de machines et de choix d’organisation sont à prendre avec des enjeux économiques importants. L’objectif est de définir une méthode d’optimisation multicritère pour la conception modulaire d’un système de production intégrant la fabrication additive en présence de données incertaines, optimale sur le long terme et sur le court terme. D’un point de vue tactique, toutes les pièces ne sont pas forcément des candidates pertinentes pour la fabrication additive. Dans ces travaux, nous avons développé un outil d’aide à la décision qui évalue la pertinence ou non de la fabrication additive pour l’obtention des pièces dans une approche globale des coûts. Au niveau opérationnel, nous proposons un outil basé sur la simulation de flux qui permet de passer des commandes aux ordres de fabrication et leur ordonnancement de manière à garantir l’efficience de l’atelier. Ces travaux de recherche sont développés en lien avec des acteurs du monde industriel : AddUp, MBDA et Dassault qui alimentent nos travaux et nous permettent de confronter nos outils à une réalité industrielleThe additive manufacturing is a field on the rise. However, companies wonder about the use of additive manufacturing for mass production. The problem raised in the context of this thesis is: How to make the process of sintering laser melting industrially viable? Our work focuses on the design and on the management of workshops integrating the additive manufacturing and of the complete process to obtain part according to three levels of decision: strategic, tactic and operational. About the strategic level, strong decisions of investment, machines selection and organization choice are taken with important economic issues. The aim is to define a multicriteria optimization method for the modular design of a production system integrating the additive manufacturing in the presence of uncertain data, optimal in the long term and the short term. From a tactical point of view, not all parts are necessarily relevant candidates for additive manufacturing. In this work, we developed a decision support tool that evaluates the relevance or not of additive manufacturing to obtain parts in a global cost approach. At the operational level, we offer a tool based on flow simulation that allows orders to be placed to production orders and their scheduling in order to guarantee the efficiency of the workshop. This research work is developed in collaboration with companies: AddUp, MBDA and Dassault, who contribute to our work and enable us to compare our tools with an industrial reality
47
Bouzoubaa, Yahya. "Méthodes exactes et heuristiques pour l’optimisation de l’agencement d’un logement : application aux situations de handicap." Thesis, Université de Lorraine, 2017. http://www.theses.fr/2017LORR0369/document.
Full textAbstract:
Le volet applicatif de cette thèse porte sur l'agencement d'un logement destiné à une personne en situation de handicap. L'agencement désigne le choix de la position, de la forme et des dimensions des pièces, des portes et des couloirs. L'agencement est généralement élaboré par un architecte, dans le respect d'un nombre si élevé de contraintes qu'il lui est difficile de parvenir qu'il parvienne à toutes les satisfaire : il y a d'abord des contraintes architecturales évidentes : non recouvrement des pièces, largeur suffisante des couloirs, accessibilité à tout point du lieu à partir de tout autre point, nécessité de placer certaines pièces sur des arrivées ou évacuations … Il y a ensuite les contraintes imposées par le handicap : largeur accrue des couloirs (déplacement en fauteuil), nécessité d'assurer un effort quotidien minimum (lutte contre le vieillissement), limitation des escaliers (asthme sévère), éloignement d'une pièce des murs mitoyens (surdité) .... Et il y a finalement les souhaits exprimés par le futur occupant, par exemple minimiser certains trajets, maximiser l’éloignement entre deux pièces ou imposer l’orientation d’une pièce. D’un point de vue formel, notre travail a consisté à développer d'une part des modèles mathématiques et des méthodes algorithmiques capables de gérer ces contraintes et d'autre part des prototypes logiciels opérationnels. Les méthodes élaborées relèvent de deux approches : l'optimisation d'un agencement conçu par l'architecte et la synthèse d'un agencement sans suggestion initiale de l'architecte. La synthèse d'un plan a été abordée comme un problème de type « bin-packing » (réputé NP-difficile) avec des contraintes additionnelles : les objets à placer - les pièces - ont des tailles variables et ils sont soumis à des contraintes fonctionnelles. La méthode de résolution s'appuie sur un premier modèle mathématique, qui prend la forme d’un programme quadratique (linéarisé par la suite) en variables mixtes. Elle a été appliquée avec succès pour placer les pièces d'un logement, pour les dimensionner, pour déterminer les couloirs assurant une complète accessibilité au logement et pour prendre en compte certaines contraintes imposées par le handicap du futur occupant. Un deuxième modèle mathématique a été élaboré pour le placement des portes et une heuristique a enfin été développée pour affecter l'espace occupé par les couloirs non indispensables aux pièces avoisinantes. La totalité de cette démarche a été programmée dans un prototype logiciel pleinement opérationnel. Le deuxième ensemble de contributions concerne l'optimisation d'un agencement existant. Cette optimisation a été conçue comme un processus itératif enchaînant évaluation et modification (amélioration) d'un agencement. Il est décliné de quatre manières : une métaheuristique de type « recuit simulé » et trois méthodes de type « recherche locale », qui explorent l’espace des solutions en utilisant des voisinages spécialement définis. Cette approche a d'une part permis d’appréhender le caractère multicritère de cette problématique et a d'autre part exigé la mise en œuvre de nombreux algorithmes géométriques. Ces travaux sont implantés dans un deuxième prototype logiciel. Ce projet a nécessité la participation à de nombreuses manifestations au-delà du domaine de l’informatique, nationales et régionales, scientifiques et non-scientifiques, organisées par différents organismes politiques et associatifs travaillant sur la problématique du handicap et de l’accessibilité, afin de bien appréhender les attentes du monde scientifique et socioprofessionnel. Cette phase prospective a été concrétisée par la rédaction de nombreux rapports qui ont alimentés la bibliographie du mémoire de thèseAt an application level, this thesis deals with the layout of an accommodation intended for a disabled person. Determining the layout means choosing the position, shape and dimensions of rooms, doors and corridors. It is usually an architect's job but the complexity is such that it is very unlikely that he succeeds in optimally fulfilling all the constraints: first, there are architectural constraints: no room overlapping, sufficient width for the corridors, accessibility to and from any point, mandatory positioning of some rooms on some areas (e.g. water supply and outlet) … Then, there are constraints imposed by disabilities: enlarged corridors (wheelchairs), mandatory daily amount of efforts (fight against aging), reducing the number of steps (severe asthma), moving a room away from shared walls (deafness)... Finally, there are the wishes expressed by the future occupant, such as minimizing some journeys, maximizing the distance between two rooms or fixing a room's orientation. From a formal point of view, our work has consisted, firstly, in developing mathematical models and algorithmic methods to deal with all these constraints and, secondly, in realizing software prototypes applying these concepts. The tools we propose aim either at optimizing a layout previously designed by an architect or at synthesising a layout without any initial suggestions from the architect. Synthesis has been tackled as bin-packing-type problem (known to be NP-hard) but with additional constraints: the objects to be placed (the rooms) have variable sizes and they are submitted to functional constraints. The resolution is based on a first, initially quadratic and then linearized, mixed integer mathematical model. It has been successfully applied to position and dimension the rooms of an accommodation, to determine corridors allowing a full accessibility to all the rooms and to take into account a number of constraints coming from the disabilities of the future occupant. A second mathematical model has been formulated for the positioning of the doors and, finally, a heuristic method has been designed to assign the space used by useless corridors to adjacent rooms. The whole process has been embedded in a fully operational software. The second set of contributions is about the optimization of an existing layout. This task has been tackled through an iterative process, looping on evaluation and modification (improvement) of an accommodation. It has been implemented in four different ways: a metaheuristic (simulated annealing) and three local-search-type methods, which traverse the solution space by using specific definitions of the neighbourhood. This approach has firstly underlined the multicriteria feature of our problem and, secondly, has required the development of many computational geometry algorithms. All this work is integrated in another functional prototype software. To understand the expectations of the scientific, social and professional worlds, this project has implied to take part to various manifestations which were national or regional, in the computer science domain or in others, scientific or non-scientific, organised by various political or non-political organisations working in the field of disabilities and accessibility. This phase has resulted in many reports which have directly fed into the bibliography of this thesis
48
Atchukatla, Mahammad suhail. "Algorithms for efficient VM placement in data centers : Cloud Based Design and Performance Analysis." Thesis, Blekinge Tekniska Högskola, Institutionen för datalogi och datorsystemteknik, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-17221.
Full textAbstract:
Content: Recent trends show that cloud computing adoption is continuously increasing in every organization. So, demand for the cloud datacenters tremendously increases over a period, resulting in significantly increased resource utilization of the datacenters. In this thesis work, research was carried out on optimizing the energy consumption by using packing of the virtual machines in the datacenter. The CloudSim simulator was used for evaluating bin-packing algorithms and for practical implementation OpenStack cloud computing environment was chosen as the platform for this research. Objectives: In this research, our objectives are as follows - Perform simulation of algorithms in CloudSim simulator. Estimate and compare the energy consumption of different packing algorithms. Design an OpenStack testbed to implement the Bin packing algorithm. Methods: We use CloudSim simulator to estimate the energy consumption of the First fit, the First fit decreasing, Best fit and Enhanced best-fit algorithms. Design a heuristic model for implementation in the OpenStack environment for optimizing the energy consumption for the physical machines. Server consolidation and live migration are used for the algorithms design in the OpenStack implementation. Our research also extended to the Nova scheduler functionality in an OpenStack environment. Results: Most of the case the enhanced best-fit algorithm gives the better results. The results are obtained from the default OpenStack VM placement algorithm as well as from the heuristic algorithm developed in this simulation work. The comparison of results indicates that the total energy consumption of the data center is reduced without affecting potential service level agreements. Conclusions: The research tells that energy consumption of the physical machines can be optimized without compromising the offered service quality. A Python wrapper was developed to implement this model in the OpenStack environment and minimize the energy consumption of the Physical machine by shutdown the unused physical machines. The results indicate that CPU Utilization does not vary much when live migration of the virtual machine is performed.
49
Deutgen, Caroline, and Nils Forsberg. "Planeringsprogram för kassettlastningen på SCA Sourcing & Logistics AB i Umeå : Ett planeringsprogram baserat på heuristiska Bin Packing-algoritmer och dagens manuella planeringsmetoder." Thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-136386.
Full textAbstract:
SCA Sourcing & Logistics i Umeå är ett transport- och logistikföretag som utgör en del av SCA Forest Products. Logistikföretaget transporterar bland annat kraftlinerrullar med roro-fartyg till terminaleri norra Europa. Inför varje fartygsresa utförs en planering där varje kraftlinerrulle tilldelas en godsbärare som kallas kassett. Planeringen utförs idag manuellt vilket tar lång tid, gör den svår att i efterhand anpassa efter olika önskemål och kan leda till vissa säkerhetsrisker då godset ska lastas. Vid en annan terminal i Sundsvall som också tillhör SCA Sourcing & Logistics används ett planeringsprogram för kassettlastningen men programmet är inte anpassat efter terminalen i Umeå. Syftet med detta arbete har varit att effektivisera lastplaneringen för kassetter på SCA Sourcing & Logistics i Umeågenom att ta fram ett planeringsprogram för kassettlastningen vid terminalen. Syftet har även varit att visa på hur tillgången till ett planeringsprogram kan utveckla planeringsarbetet i framtiden. Det framtagna programmet har implementerats i Visual Basic och baserats på en ingående analys av dagens planeringsmetoder och olika heuristiska Bin Packing-algoritmer. Programmet genererar planeringar som i snitt får plats med fler rullar per kassett jämfört med dagens arbetsmetoder på bekostnad av fler olika typer av rullar per kassett. Programmet minskar planeringstiden från flera timmar till under en minut och kan anpassa planeringen från att prioritera hög snittvikt per kassett till att minska antalet unika rullar per kassett. Programmet ger varje rulle en position på kassetterna vilket minskar sannolikheten för felaktig lastning och därmed ökar säkerheten vid terminalen. Vidare har vinningen med att öka den tillåtna maxvikten på godsbärarna och vilka fartygsresor som gynnas av ökad snittvikt per kassett analyserats. Slutligen har planerarens framtida roll i planeringsarbetet diskuteratsSCA Sourcing & Logistics in Umeå is a transport and logistics company that is a part of SCA Forest Products. This company transports, for example, kraftliner reels on roro-vessels to terminals in the northern part of Europe. Before each departure from the terminal in Umeå a planning process is carried out where each kraftliner reel is assigned to a goods carrier called a cassette. The planning process is carried out manually without any planning program making it time consuming, especially when the loading plan needs to be adjusted after completion. Further, there are certain operational safety risks when loading the reels due to the manual nature of the planning process. At another terminal within SCA Sourcing & Logistics in Sundsvall a planning program for cassette loading is used, but this program is not adapted for the terminal in Umeå. The purpose of the project has been to make the planning process for the cassette loading at SCA Sourcing & Logistics in Umeå more efficient by creating a planning program for the cassette loading at the terminal. The purpose has also been to show how today’s planning process can be developed with the benefit of a planning program. The program has been written in Visual Basic, and it is based on an in-depth analysis of today´s planning process and includes various modified heuristic Bin Packing algorithms. The program generates loading plans with higher-than-average weight per cassette compared to the corresponding manual loading plan. This is at the expense of more unique reel types per cassette. The planning program decreases the planning time from several hours to under one minute and it can be adjusted to prioritize high weight per cassette or few unique reel types per cassette. It gives each reel a position on the cassettes, which decreases the probability of mistakes when the cassettes are loaded. Further, the project has shown the possible gain that can be realized when the allowed maximum weight of the cassettes is increased, the profitability of shipment routes that have higher-than-average weight per cassette and proposes suggestions on how the role of the planner can be developed in the future.
50
Lemaire, Pierre. "Rangement d'objets multiboîtes : modèles et algorithmes." Phd thesis, Université Joseph Fourier (Grenoble), 2004. http://tel.archives-ouvertes.fr/tel-00006893.
Full textAbstract:
Un objet multiboîte est composé de plusieurs parties identiques qui doivent être rangées dans des boîtes différentes. La hauteur d'une boîte est alors la somme des hauteurs des objets qu'elle contient. Ce concept généralise et englobe de nombreux problèmes de la littérature de la recherche opérationnelle.Une classification de ces modèles est proposée. Les bases théoriques sont posées. En particulier, la complexité pour les principaux types d'objets et objectifs est déterminée.
Une étude détaillée est effectuée lorsque les objets ont des largeurs constantes et que l'on veut minimiser la hauteur de la boîte la plus haute. Des bornes inférieures, des heuristiques avec de très bonnes garanties de performance et un algorithme génétique sont proposés pour résoudre ce modèle. Leurs comportements théoriques et expérimentaux sont analysés.