To see the other types of publications on this topic, follow the link: Problèmes du bin packing.
Dissertations / Theses on the topic 'Problèmes du 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 'Problèmes du 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
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 objets<br>The 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
2
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
3
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 simulation<br>In 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
4
Pensi, Janvier. "Résolution conjointe des problèmes de planification des opérations chirurgicales et des opérations de maintenance : application au cas des hôpitaux camerounais." Thesis, Université Clermont Auvergne (2017-2020), 2017. http://www.theses.fr/2017CLFAC033/document.
Full textAbstract:
Les travaux de thèse présentés s’intéressent à l’optimisation des activités d’un bloc opératoire. Ces activités concernent les interventions chirurgicales à planifier et les interventions de maintenance préventive sur les équipements dans les salles d’opération. Une solution est la synchronisation de ces activités lors de la construction du planning opératoire au niveau opératoire. Nous dissocions deux stratégies de programmation opératoire : programmation ouverte et programmation avec allocation préalable des plages horaires aux chirurgiens. Pour chacune des stratégies, nous considérons deux cas : le cas où l’heure de début d’une intervention de maintenance dans la salle est fixée, ladite intervention précédant l’affection des interventions chirurgicales dans les salles. Le second cas étant celui où l’heure de début de maintenance varie dans un intervalle entre une heure de début minimum et une heure de début maximum, avec l’intervention de maintenance placée a posteriori.Nous faisons plusieurs propositions de méthodes (exactes et approchées), y compris une méthode hybride, qui repose sur le couplage entre une métaheuristique et une heuristique. Les résultats obtenus sur des instances générées en concertation avec le monde hospitalier sont intéressants<br>The presented dissertation is about the optimization of hospital systems, more precisely the optimization of the activities of an operation theatre. These activities showcase the surgical procedures to be planned and the preventive maintenance interventions on the equipment in the operating rooms. One solution is the synchronization of these activities during the construction of the operational planning at the operational level.We dissociate two operating programming strategies: Open Scheduling or Open programming and Block Scheduling or Programming with prior allocation of times to surgeons. For each strategy two cases are considered: the first case is where the time of beginning of a maintenance intervention in the room is fixed - this intervention preceding the affection of the surgical interventions in the rooms. The second case is where the maintenance start time varies in the interval between a minimum start time and a maximum start time, with the maintenance intervention placed beforehand. We make several proposition’s methods (exact and approximate), including a hybrid method, which is based on the coupling between a metaheuristic and a heuristic. The results obtained on bodies generated in consultation with the hospital’s world are interesting
5
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.
6
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.
7
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ée<br>The 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
8
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èse<br>At 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
9
Larchevêque, Hubert. "Agrégation de ressources avec contrainte de distance : applications aux plateformes de grande échelle." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2010. http://tel.archives-ouvertes.fr/tel-00580962.
Full textAbstract:
Durant cette thèse, nous avons introduit les problèmes de Bin Covering avec Contrainte de Distance (BCCD) et de Bin Packing avec Contrainte de Distance (BPCD), qui trouvent leur application dans les réseaux de grande échelle, tel Internet. L'étude de ces problèmes que nous effectuons dans des espaces métriques quelconques montre qu'il est impossible de travailler dans un tel cadre sans avoir recours à de l'augmentation de ressources, un procédé qui permet d'élaborer des algorithmes construisant des solutions moins contraintes que la solution optimale à laquelle elles sont comparées. En plus de résultats d'approximation intéressants, nous prouvons la difficulté de ces problèmes si ce procédé n'est pas utilisé. Par ailleurs, de nombreux outils ont pour objectif de plonger les grands réseaux qui nous intéressent dans des espaces métriques bien décrits. Nous avons alors étudié nos problèmes dans les espaces métriques générés par certains de ces outils, comme Vivaldi et Sequoia.
10
Shraideh, Ahmad. "Analyse et optimisation d'un processus à partir d'un modèle BPMN dans une démarche globale de conception et de développement d'un processus métier : application à la dématérialisation de flux courrier du projet GOCD (PICOM)." Phd thesis, Ecole Centrale de Lille, 2009. http://tel.archives-ouvertes.fr/tel-00579520.
Full textAbstract:
Cette thèse a été réalisée dans le cadre du projet " Gestion et Optimisation de la Chaîne Documentaire ", projet labellisé par le Pôle de compétitivité des Industries du Commerce. Le projet a pour but de concevoir et de développer un nouveau workflow et un outil d'aide à la décision. Ce système doit être capable de gérer et d'optimiser le flux complet dématérialisé de contrats reçus à COFIDIS.Nous présentons d'abord le framework retenu dans le cadre du projet pour modéliser et implémenter le workflow. En phase de conception BPMN a été choisi. Pour la partie développement, l'utilisation de BPEL a été préconisée pour implémenter et exécuter l'application finale (services web).Cependant la flexibilité offerte par BPMN peut conduire à des propriétés indésirables du processus telles que blocage et inaccessibilité. De plus, BPMN a été conçu pour fournir des modèles Orientés Process. Les données ou les ressources y sont donc peu représentées. En conséquence, l'analyse de performance sur un modèle BPMN est quasi inexistante.Afin de surmonter ces problèmes nous proposons d'insérer dans le framework deux nouvelles phases. Ces deux phases sont appliquées au modèle BPMN. La première est une phase de vérification et de validation et la deuxième une phase d'optimisation. Ces deux phases sont réalisées en transformant le modèle BPMN vers un langage formel. Notre choix dans ce travail a été d'utiliser les réseaux de Petri. Ce qui nous a permis de vérifier et de valider de bonnes propriétés du process. Quant à l'optimisation, nous avons défini une nouvelle variante du problème d'affectation (bin packing problem) et proposé une résolution à intégrer dans le processus d'aide à la décision
11
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.
12
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.
13
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.
14
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.
15
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.
16
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.<br>Bibliography: leaves 123-124.<br>by Peter Williston Shor.<br>Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1985.
17
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.
18
Pasha, Arfath. "Geometric bin packing algorithm for arbitrary shapes." [Gainesville, Fla.] : University of Florida, 2003. http://purl.fcla.edu/fcla/etd/UFE0000907.
Full text
19
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
20
Diedrich, Florian. "Algorithmes d'approximation pour des programmes linéaires et les problèmes de packing avec des contraintes géométriques." Grenoble INPG, 2009. http://www.theses.fr/2009INPG0014.
Full textAbstract:
Dans cette thèse, nous traitons plusiers problèmes à l’aide d’algorithme d’approximation. Les problemes sont aussi bien des problèmes de faisabilité que des problèmes d’optimisation<br>In this thesis we approach several problems with approximation algorithms ; these are feasibility problems as well as optimization problems
21
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
22
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.
23
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.<br>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.<br>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.
24
Perez, Anthony. "Algorithmes de noyau pour des problèmes d'édition de graphes et autres structures." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00660089.
Full textAbstract:
Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP- complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de relations. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes CLOSEST 3-LEAF POWER, COGRAPH EDITION et PROPER INTERVAL COMPLETION. Concernant les problèmes d'édition de relations, nous étendons la notion de Conflict Packing, qui a déjà été utilisée dans quelques problèmes paramétrés et permet d'élaborer des algorithmes de noyau linéaires pour différents problèmes. Nous présentons un noyau linéaire pour le problème FEEDBACK ARC SET IN TOURNAMENTS, et adaptons les techniques utilisées pour obtenir un noyau linéaire pour le problème DENSE ROOTED TRIPLET INCONSISTENCY. Dans les deux cas, nos résultats améliorent la meilleure borne connue, à savoir un noyau quadratique. Finalement, nous appliquons cette tech- nique sur les problèmes DENSE BETWEENNESS et DENSE CIRCULAR ORDERING, obtenant à nouveau des noyaux linéaires, qui constituent les premiers algorithmes de noyau polynomiaux connus pour ces problèmes.
25
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.<br>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.
26
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,
27
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.
28
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.<br>Ph. D.
29
Han, Xin. "Online and approximation algorithms for bin-packing and knapsack problems." 京都大学 (Kyoto University), 2007. http://hdl.handle.net/2433/135979.
Full text
30
Delorme, Xavier. "Modélisation et résolution de problèmes liés à l'exploitation d'infrastructures ferroviaires." Valenciennes, 2003. http://ged.univ-valenciennes.fr/nuxeo/site/esupversions/bc3fe069-ea2a-4864-9968-8cc1fe7bd9f1.
Full textAbstract:
Cette thèse s'intéresse à la planification de l'exploitation d'infrastructures ferroviaires à l'échelle d'un nœud ou d'une gare. Pour déterminer une stratégie d'offre, il est important de disposer d'outils d'évaluation de la capacité des infrastructures. Cela permet de situer les limites d'un réseau, et d'étudier l'impact de modifications. Dans ce cadre, la faisabilité d'une grille horaire, son optimisation vis-à-vis de critères comme le nombre de trains (saturation), et l'évaluation de la stabilité sont considérées. Nous proposons une modélisation linéaire multiobjectif de ce problème. Le niveau de détail considéré est suffisamment fin pour obtenir des grilles horaires réalisables dans la pratique sur les infrastructures étudiées. En outre, elle présente deux structures correspondant à des problèmes d'optimisation classiques appelés plus court chemin et set packing. Si le premier est facile à résoudre, le second est connu comme NP-difficile. Nous proposons différents algorithmes de pré-traitements, et de résolution approchée (basée sur la métaheuristique GRASP), pour ce problème. Une première extension de cette heuristique au cas biobjectif est présentée. Les expérimentations numériques, menées sur des instances correspondant au nœud de Pierrefitte-Gonesse, ou générées aléatoirement, montrent l'efficacité de ces algorithmes. L'intégration de ces travaux dans un logiciel dédié aux études de capacité d'infrastructures ferroviaires (projet RECIFE, en collaboration avec la SNCF) est décrite<br>The subject of this thesis is the planning of railroad infrastructures operation at a node or station scale. In order to determine an offer strategy, it is important to have some evaluation tools of the infrastructures capacity. This allows to evaluate the network limits, and to study the impact of some modifications. The main questions considered are, the feasibility of a timetable, its optimization according to criteria like the number of trains (saturation), and the stability evaluation. We propose a multiobjective linear model of this problem. The precision considered is accurate enough to obtain realizable timetables in practice on the studied infrastructures. Moreover, it presents two structures corresponding to classic optimization problems named shortest path and set packing. If the resolution of the first one is easy, the second one is known as NP-hard. We propose several pre-processing algorithms, and an approximation method based on the GRASP metaheuristic, for this problem. A first extension of this method in biobjective case is presented. The numerical experimentations on several instances, corresponding to Pierrefitte-Gonesse node or randomly generated, show the efficiency of these algorithms. The integration of these works in a complete software dedicated to the evaluation of railroad infrastructures capacity (RECIFE project, in collaboration with the french national railroad society) is described
31
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
32
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.<br>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.
33
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
34
Jing, Chen. "Studies on Approximation Algorithms for Bin-Packing and Train Delivery Problems." 京都大学 (Kyoto University), 2016. http://hdl.handle.net/2433/215691.
Full text
35
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.<br>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.
36
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ą.<br>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.
37
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.
38
Valicov, Petru. "Problèmes de placement, de coloration et d’identification." Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14549/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques.La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum ID est n-1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour le paramètre ID dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ID dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits<br>In this thesis we study three theoretical computer science problems, namely the orthogonal packing problem (OPP for short), strong edge-colouring and identifying codes.OPP consists in testing whether a set of rectangular items can be packed in a rectangular container without overlapping and without exceeding the borders of this container. An additional constraint is that the rotation of the items is not allowed. The problem is NP-hard even when the problem is reduced to packing squares in a square. We propose an exact algorithm for solving OPP efficiently using the characterization of the problem by interval graphs proposed by Fekete and Schepers. For this purpose we use some compact representation of interval graphs - MPQ-trees. We show experimental results of our approach by comparing them to the results of other algorithms known in the literature. we observe promising gains.The study of strong edge-colouring and identifying codes is focused on the structural and computational aspects of these combinatorial problems. In the case of strong edge-colouring we are interested in the families of planar graphs and subcubic graphs. We show optimal upper bounds for the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also show that every planar subcubic graph without induced cycles of length 4 and 5 can be strong edge-coloured with at most nine colours. Finally, we confirm the difficulty of the problem by showing that it remains NP-complete even in some restricted classes of planar subcubic graphs.For the subject of identifying codes we propose a characterization of non-trivial graphs having maximum identifying code number ID, that is n-1, where n is the number of vertices. We study the case of line graphs and prove lower and upper bounds for ID parameter in this class. At last we investigate the complexity of the corresponding decision problem and show the existence of a linear algorithm for computing ID of the line graph L(G) where G has the size of the tree-width bounded by a constant. On the other hand, we show that the identifying code problem is NP-complete in various subclasses of planar graphs
39
Ž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.
40
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
41
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
42
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 recherche<br>In 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<br>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
43
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.
44
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.<br>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.
45
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ÓGICO<br>A 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.<br>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.
46
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.
47
Joncour, Cédric. "Problèmes de placement 2D et application à l’ordonnancement : modélisation par la théorie des graphes et approches de programmation mathématique." Thesis, Bordeaux 1, 2010. http://www.theses.fr/2010BOR14173/document.
Full textAbstract:
Le problème de placement sur deux dimensions consiste à décider s’il existe un rangement d’objets rectangulaires dans une boîte donnée. C’est un problème combinatoire difficile (à la complexité du respect des capacités s’ajoute celle du positionnement des objets).Dans cette thèse, nous considérons les variantes sans rotation des objets et avec ou sansoptimisation de la valeur des objects placés.Nous menons une étude exploratoire des méthodologies qui peuvent être développéesà l’interface de la programmation mathématique, de l’optimisation combinatoire et de lathéorie des graphes. Notre objectif est aussi de développer des approches non basées surune discrétisation de la boîte, les plus performantes à l’heure actuelle.Dans ce mémoire, nous effectuons d’abord une étude théorique des qualités de bornesqui peuvent être obtenues avec les différentes formulations classiques. Au cours de cetteétude, nous renforçons certaines de ces formulations et en proposons de nouvelles formulations. Une étude qualitative des bornes issues de la relaxation linéaire des formulationstestés sur des jeux d’instances classiques de la littérature confirme l’étude théorique. Cetteétude permet de se rendre compte des facteurs déterminant la qualité des bornes et desenjeux à relever par la programmation mathématique.Par la suite, nous avons développé et testé deux approches de résolution innovantes.L’une est basée sur la décomposition de Dantzig-Wolfe associée à un branchement surles contraintes disjonctives de non recouvrement des objets. Cette approche a permis uneamélioration des résultats obtenus par la programmation mathématique.L’autre approche constitue en une approche combinatoire basée sur diverses caractérisations des graphes d’intervalles (modélisant le chevauchement des objets selon leurprojection sur chaque axe). Un premier algorithme est basé sur l’énumération de matricesde uns-consécutifs. Un autre utilise des arbres étiquetés pour éliminer plus efficacement lescas de symétries entre placements. Ces approches ont l’avantage de ne pas dépendre d’unediscrétisation du conteneur<br>The two dimensional orthogonal packing problem consists in deciding whether thereexists a packing of rectangular items in a given bin. This is a hard combinatorial problem(in addition to capacity constraints, one has to face the complexity of item positionning).In this thesis, we consider the case without item rotation and with or without packingvalue optimization.We explore methodologies at the interface of mathematical programming, combinatorial optimization and graph theory. Our aim is also to develop approaches not based on abin discretization (i.e. an alternative to such methods that are currently the most effective).In this work, we perform a theorical study of the quality of bounds of differents classicalformulations. We tighten some formulations and we propose new formulations. We perform a numerical study to test bound quality on classical instances. This study permits toidentify the determinant factor in the quality of mathematical programming formulations.We develop and test two resolution approaches. The first is based on Dantzig-Wolfedecomposition associated with a branching on no-overlapping disjunctive constraints. Thisapproach permits to improve results obtained by mathematical programming.The second approach establish a combinatorial approach based on multiple intervalgraph caracterization (modelling the item no-overlapping according to their projection oneach axis). The first algorithm is based on consecutive ones matrices enumeration. An otheruse labelled tree to eliminate more efficiently symmetry in packing. These approaches haveto advantage of being independent from bin discretization
48
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.
49
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.
50
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.<br>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.