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. / 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. / 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.

Bin packing is a very important and popular research area in the computer science field. Past work showed many good and real-world packing algorithms. How- ever, due to the complexity of the problem in multiple-dimensional bin packing, also called hyperbox packing, we need more practical packing algorithms for its real-world applications. In this dissertation, we extend 1D packing algorithms to hyperbox packing prob- lems via a general framework that takes two inputs of a 1D packing algorithm and an instance of hyperbox packing problem and outputs a hyperbox packing algorithm. The extension framework significantly enriches the family of hyperbox-packing algorithms, generates many framework-based algorithms, and simultaneously calls for the analysis for those algorithms. We also analyze the performance of a couple of framework-based algorithms from two perspectives of worst-case performance and average-case performance. In worst- case analysis, we use the worst-case performance ratio as our metric and analyze the relationship of the ratio of framework-based algorithms and that of the corresponding 1D algorithms. We also compare their worst-case performance against two baselines: strip optimal algorithms and optimal algorithms. In average-case analysis, we use expected waste as a metric, analyze the waste of optimal hyperbox packing algorithms, and estimate the asymptotic forms of the waste for framework-based algorithms.

Fu ren da xue Zhongguo wen xue yan jiu suo shuo shi lun wen. / Includes bibliographical references (p. 213-214).

Thesis--London University, 1935. / "Select bibliography": p. 258-262.

Fu ren da xue Zhongguo wen xue yan jiu suo shuo shi lun wen. / Bibliography: p. 213-214.

No description available.

Zugl.: Freiburg (Breisgau), Univ., Diss., 2006

Thesis (Ph. D.)--Boston University, 2005. / Vita. Includes bibliographical references (leaves [418]-443).

An online algorithm must make decisions immediately and irrevocably based only on a part of the input without any knowledge of the future part of the input. We introduce the competitive analysis of online algorithms, a standard worst-case analysis, and present main results of this analysis on the problem of online Bin Packing and on some of its variants. In Bin Packing, a sequence of items of size up to 1 arrives to be packed into the minimal number of unit capacity bins. Mainly, we focus on Colored Bin Packing in which items have also a color and we cannot pack two items of the same color adjacently in a bin. For Colored Bin Packing, we improve some previous results on the problem with two colors and present the first results for arbitrarily many colors. Most notably, in the important case when all items have size zero, we give an optimal 1.5-competitive algorithm. For items of arbitrary size we present a lower bound of 2.5 and a 3.5-competitive algorithm. Powered by TCPDF (www.tcpdf.org)

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. / 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.