No description available.

No description available.

Ph. D.

Thesis (PhD (Logistics))--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: Packing problems are common in industry and there is a large body of literature on the subject. Two packing problems are considered in this dissertation: the strip packing problem and the bin packing problem. The aim in both problems is to pack a speci ed set of small items, the dimensions of which are all known prior to packing (hence giving rise to an o ine problem), into larger objects, called bins. The strip packing problem requires packing these items into a single bin, one dimension of which is unbounded (the bin is therefore referred to as a strip). In two dimensions the width of the strip is typically speci ed and the aim is to pack all the items into the strip, without overlapping, so that the resulting packing height is a minimum. The bin packing problem, on the other hand, is the problem of packing the items into a speci ed set of bins (all of whose dimensions are bounded) so that the wasted space remaining in the bins (which contain items) is a minimum. The bins may all have the same dimensions (in which case the problem is known as the single bin size bin packing problem), or may have di erent dimensions, in which case the problem is called the multiple bin size bin packing problem (MBSBPP). In two dimensions the wasted space is the sum total of areas of the bins (containing items) not covered by items. Many solution methodologies have been developed for above-mentioned problems, but the scope of the solution methodologies considered in this dissertation is restricted to heuristics. Packing heuristics follow a xed set of rules to pack items in such a manner as to nd good, feasible (but not necessarily optimal) solutions to the strip and bin packing problems within as short a time span as possible. Three types of heuristics are considered in this dissertation: (i) those that pack items into levels (the heights of which are determined by the heights of the tallest items in these levels) in such a manner that all items are packed along the bottom of the level, (ii) those that pack items into levels in such a manner that items may be packed anywhere between the horizontal boundaries that de ne the levels, and (iii) those heuristics that do not restrict the packing of items to levels. These three classes of heuristics are known as level algorithms, pseudolevel algorithms and plane algorithms, respectively. A computational approach is adopted in this dissertation in order to evaluate the performances of 218 new heuristics for the strip packing problem in relation to 34 known heuristics from the literature with respect to a set of 1 170 benchmark problem instances. It is found that the new level-packing heuristics do not yield signi cantly better solutions than the known heuristics, but several of the newly proposed pseudolevel heuristics do yield signi cantly better results than the best of the known pseudolevel heuristics in terms of both packing densities achieved and computation times expended. During the evaluation of the plane algorithms two classes of heuristics were identi ed for packing problems, namely sorting-dependent and sortingindependent algorithms. Two new sorting techniques are proposed for the sorting-independent algorithms and one of them yields the best-performing heuristic overall. A new heuristic approach for the MBSBPP is also proposed, which may be combined with level and pseudolevel algorithms for the strip packing problem in order to nd solutions to the problem very rapidly. The best-performing plane-packing heuristic is modi ed to pack items into the largest bins rst, followed by an attempted repacking of the items in those bins into smaller bins with the aim of further minimising wasted space. It is found that the resulting plane-packing algorithm yields the best results in terms of time and packing density, but that the solution di erences between pseudolevel algorithms are not as marked for the MBSBPP as for the strip packing problem. / AFRIKAANSE OPSOMMING: Inpakkingsprobleme kom algemeen in die industrie voor en daar is 'n aansienlike volume literatuur oor hierdie onderwerp. Twee inpakkingsprobleme word in hierdie proefskrif oorweeg, naamlik die strook-inpakkingsprobleem en die houer-inpakkingsprobleem. In beide probleme is die doel om 'n gespesi seerde versameling klein voorwerpe, waarvan die dimensies almal voordat inpakking plaasvind, bekend is (en die probleem dus 'n sogenaamde a yn-probleem is), in een of meer groter houers te pak. In die strook-inpakkingsprobleem word hierdie voorwerpe in een houer, waarvan een dimensie onbegrens is, ingepak (hierdie houer word dus 'n strook genoem). In twee dimensies word die wydte van die strook gewoonlik gespesi seer en is die doel om al die voorwerpe sonder oorvleueling op s o 'n manier in die strook te pak dat die totale inpakkingshoogte geminineer word. In die houer-inpakkingsprobleem, daarenteen, is die doel om die voorwerpe op s o 'n manier in 'n gespesi seerde aantal houers (waarvan al die dimensies begrens is) te pak dat die vermorste of oorblywende ruimte in die houers (wat wel voorwerpe bevat) 'n minimum is. Die houers mag almal dieselfde dimensies h^e (in welke geval die probleem as die enkelgrootte houer-inpakkingsprobleem bekend staan), of mag verskillende dimensies h^e (in welke geval die probleem as die veelvuldige-grootte houer-inpakkingsprobleem bekend staan, afgekort as VGHIP). In twee dimensies word die vermorste ruimte geneem as die somtotaal van daardie deelareas van die houers (wat wel voorwerpe bevat) waar daar geen voorwerpe geplaas word nie. Verskeie oplossingsmetodologie e is al vir die bogenoemde twee inpakkingsprobleme ontwikkel, maar die bestek van die metodologie e wat in hierdie proefskrif oorweeg word, word beperk tot heuristieke. 'n Inpakkingsheuristiek volg 'n vaste stel re els waarvolgens voorwerpe in houers gepak word om so spoedig moontlik goeie, toelaatbare (maar nie noodwendig optimale) oplossings tot die strook-inpakkingsprobleem en die houer-inpakkingsprobleem te vind. Drie tipes inpakkingsheuristieke word in hierdie proefskrif oorweeg, naamlik (i) heuristieke wat voorwerpe langs die onderste randte van horisontale vlakke in die houers pak (die hoogtes van hierdie vlakke word bepaal deur die hoogtes van die hoogste item in elke vlak), (ii) heuristieke wat voorwerpe op enige plek binne horisontale stroke in die houers pak, en (iii) heuristieke waar inpakking nie volgens horisontale vlakke of stroke beperk word nie. Hierdie drie klasse heuristieke staan onderskeidelik as vlakalgoritmes, pseudo-vlakalgoritmes en platvlakalgoritmes bekend. 'n Berekeningsbenadering word in hierdie proefskrif gevolg deur die werkverrigting van die 218 nuwe heuristieke vir die strook-inpakkingsprobleem met die werkverrigting van 34 bekende heuristieke uit die literatuur te vergelyk, deur al die heuristieke op 1 170 toetsprobleme toe te pas. Daar word bevind dat die nuwe vlakalgoritmes nie 'n noemenswaardige verbetering in oplossingskwaliteit in vergeleke met soortgelyke bestaande algoritmes in die literatuur lewer nie, maar dat verskeie nuwe pseudo-vlakalgoritmes wel noemenswaardige verbeteringe in terme van beide inpakkingsdigthede en oplossingstye in vergeleke met die beste bestaande algoritmes in die literatuur lewer. Assessering van die platvlakalgoritmes het gelei tot die identi kasie van twee deelklasse van algoritmes, naamlik sorteringsafhanklike- en sorteringsonafhanklike algoritmes. Twee nuwe sorteringstegnieke word ook vir die deelklas van sorteringsonafhanklike algoritmes voorgestel, en een van hulle lewer die algeheel beste inpakkingsheursitiek. 'n Nuwe heuristiese benadering word ook vir die VGHIP ontwikkel. Hierdie benadering kan met vlak- of pseudo-vlakalgoritmes vir die strook-inpakkingsprobleem gekombineer word om baie vinnig oplossings vir die VGHIP te vind. Die beste platvlakheuristiek vir die strookinpakkingsprobleem word ook aangepas om voorwerpe eers in die grootste houers te pak, en daarna in kleiner houers te herpak met die doel om vermorste ruimte verder te minimeer. Daar word bevind dat die resulterende platvlakalgoritme die beste resultate in terme van beide inpakkingsdigtheid en oplossingstyd lewer, maar dat oplossingsverskille tussen die pseudovlakalgoritmes nie so opmerklik vir die VGHIP is as wat die geval met die strookinpakkingsprobleem was nie.

We consider random fractals generated by random recursive constructions, prove zero-one laws concerning their dimensions and find their packing and Minkowski dimensions. Also we investigate the packing measure in corresponding dimension. For a class of random distribution functions we prove that their packing and Hausdorff dimensions coincide.

Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving optimal times in theory. However, over a wide range of random data this version of the algorithm is giving very good solutions very fast and runs on problems of up to 100,000,000 nodes in a grid and different ranges for the variables. It is also shown that this version of algorithm is clearly superior to the first algorithm and has shown to be very efficient in practice.

O Brasil é o maior produtor de lima ácida \'Tahiti\' (Citrus latifolia Tanaka), uma fruta de origem tropical pertencente à família Rutaceae. O beneficiamento pós-colheita desta fruta visa conservar a qualidade obtida no campo por mais tempo, entretanto, injúrias mecânicas podem ocorrer neste processo, elevando a perda de qualidade e, reduzindo a vida útil e o valor comercial dos frutos. Este trabalho foi dividido em duas etapas, as quais deram origem a dois artigos que objetivaram: (1) Avaliar a influência da colheita e do beneficiamento pós-colheita na qualidade e conservação de lima ácida \'Tahiti\', (2) Identificar os pontos críticos de impacto na linha de beneficiamento de lima ácida \'Tahiti\', e avaliar a influência desses pontos na qualidade e na conservação pós-colheita. Na etapa 1, os frutos foram coletados na planta e na linha de beneficiamento, sendo os tratamentos denominados: colheita, secagem, fungicida e giberelina, cera e embalagem. Na etapa 2, os frutos foram coletados diretamente das plantas e submetidos a impactos visando simular aqueles da linha de beneficiamento. Foram realizadas análises físico-químicas de rendimento do suco, acidez titulável, sólidos solúveis, ácido ascórbico, clorofila total, perda de massa, coloração da casca (colorímetro e escala de cor), incidência e severidade de oleocelose, e avaliação visual (podridões, murchamento, danos físicos, coloração e perda do cálice). Também foram realizados experimentos sensoriais considerando frutos coletados na linha e com os impactos simulados em laboratório, cada qual em duas condições de armazenamento (refrigerado e ambiente). O beneficiamento contribui para a manutenção de características físico-químicas importantes para a lima ácida \'Tahiti\', todavia, os resultados obtidos nestes trabalhos apontam que as condições da linha e os impactos a que os frutos são submetidos durante o beneficiamento influem negativamente na qualidade. Na etapa 1, constatou-se com o beneficiamento redução no conteúdo de sólidos solúveis no último dia de armazenamento, queda dos cálices e, maior incidência e severidade de oleocelose. Além disto, o beneficiamento completo acarretou numa maior porcentagem de murchamento e perda da coloração verde da casca dos frutos, sobrepujando os efeitos positivos da giberelina e da cera. Na etapa 2, ao realizar a caracterização da linha, constatou-se magnitude total de 1788,6 G, variando de 23,9 G à 147,4 G dependendo do ponto de transferência. Nos frutos com impactos simulados houve perda da cor verde da casca, de sólidos solúveis, e de acidez titulável e, maior teor de ácido ascórbico, perda de massa, murchamento, queda do cálice e, incidência e severidade de oleocelose. Além disto, a análise sensorial apontou que a preferência dos provadores está alinhada aos níveis de impactos, com os frutos injuriados obtendo menor aceitabilidade para a aparência e, maiores intensidades de amargor e gosto de sobremaduro do suco. Os principais motivos que influenciam na tomada de decisão para o atributo aparência do fruto são incidência de distúrbios, turgidez e coloração da casca. A redução dos impactos na linha de beneficiamento pelo controle das alturas de quedas e do uso de tecnologias, como materiais amortecedores, contribui para a conservação de atributos importantes para a comercialização de lima ácida \'Tahiti\', reduzindo suas perdas pós-colheita e, gerando maiores lucros aos envolvidos na cadeia de produção. / Brazil is the largest producer of \'Tahiti\' acid lime (Citrus latifolia Tanaka), a fruit of tropical origin belonging to the Rutaceae family. The postharvest handling of this fruit aims to preserve the quality obtained in the field, however, mechanical injuries increases quality loss, reducing the fruit useful life and commercial value. This work was divided into two stages, which gave rise to two articles that objectified:: (1) To evaluate the influence of harvest and postharvest handling on the quality and conservation of \'Tahiti\' acid lime; (2) Identify the critical impact points of the \'Tahiti\' acid lime handling line, and to evaluate the influence of these points on quality and postharvest conservation. In step 1, the fruits were collected in the plant and in the handling line, being the treatments denominated: harvest, drying, fungicide and gibberellin, wax and packaging. In step 2, fruit were collected from the plants, being the same submitted to impacts aiming to simulate those of the handling line. Physicochemical analysis of the juice yield, titratable acidity, soluble solids, ascorbic acid, chlorophyll, weight loss, peel color (colorimeter and color scale), the incidence and severity oleocellose and visual evaluation (rotting, wilting, physical damage, coloring and loss of the calyx) were performed. Sensory experiments were also performed considering fruits collected in the line and with simulated impacts in the laboratory, each one under two storage conditions (refrigerated and ambient). The handling contributes to the maintenance of important physical and chemical characteristics for the \'Tahiti\' acid lime, however, the results obtained in these studies indicate that the conditions of the line and the impacts to which the fruits are submitted during the handling affect negatively the quality. In step 1, it was verified with the handling the reduction was observed in the content of soluble solids on the last day of storage, drop in the calyces and, greater incidence and severity of oleocellose. In addition, the complete handling resulted in a higher percentage of wilting and loss of the green color of the fruit peel, overcoming the positive effects of gibberellin and wax. In step 2, when performing the line characterization, a magnitude of 1788.6 G was found, varying from 23.9 G to 147.4 G depending on the transfer point. In fruits with simulated impacts there was loss of the green color of the peel, soluble solids, and titratable acidity and higher ascorbic acid content, weight loss, wilting, and drop the calyx, oleocelose incidence and severity. In addition, the sensorial analysis showed that the preference of the tasters agrees with the impact magnitude levels, with the injured fruits obtaining less acceptability for the appearance, higher intensities of bitterness and taste overriper of juice. The main reasons that influence in the decision making for the attribute appearance are incidence of disorders, turgidity and coloration of peel. Reducing impacts on the handling line for control of falls and the use of technologies such as bumpers materials, contributes to the conservation of important attributes for the marketing of \'Tahiti\' acid lime, reducing its postharvest losses and generating higher profits to those involved in the production chain.

Neste trabalho desenvolvemos o estudo da álgebra linear, secções cônicas e aplicações. Apresentamos os conceitos mais importantes da álgebra linear, estudando os espaços vetorias, subespaços vetoriais, matriz de mudança de base, transformações lineares e produto interno. O principal resultado do trabalho é o teorema espectral que fornece ferramentas para se estudar as secções cônicas não elementares, ou seja, aquelas nas quais uma parábola, elipse ou hipérbole são apresentadas com seus eixos não paralelos aos eixos coordenados do plano cartesiano. Uma vez de posse deste teorema é mostrado um processo prático no qual transformamos uma equação ax2 +bxy +cy2 +dx +ey + g = 0 na equação k1 (x\')2 + k2 (y\')2 + (dx1 + ey1) x\' + (dx2 + ey2) y\' + g = 0 sem o termo misto xy, onde após a eliminação deste, podemos deduzir a equação da cônica identificando assim esta curva. Apresentamos exemplos de cônicas com eixos paralelos e não paralelos aos coordenados do plano cartesiano e utilizamos o software geogebra para visualização. Também discutimos algumas aplicações das cônicas como trajetória de corpos celestes (planeta Terra e um cometa), princípio de reflexão da parábola mostrando o porquê das antenas e dos captadores de ondas sonoras serem parabólicos. Demonstramos um teorema que denominei de identificador de uma curva cônica pois com ele é possível classificar a cônica sem realizar o processo prático, apenas para isso identificamos através da equação ax2 +bxy + cy2 +dx + ey +g = 0, quais os valores de a;b e c e feito isto calculamos o discriminante b2 - 4ac, analisamos os sinais e a nulidade, ou seja, se é maior que zero, menor que zero ou igual a zero, assim é possível classificar a cônica. / The paper develops the study of linear algebra, conic sections and applications. I present the most important concepts of linear algebra, studying vector spaces, vector subspaces, base change matrix, linear transformations, internal product. The main result of the work is the spectral theorem, which provides tools to study the non-elementary conic sections, that is, those in which a parabola, ellipse or hyperbola are presented with their axes not parallel to the cartesian planes coordinate axes. Using this theorem we show a practical process in which we transform an equation ax2 +bxy + cy2 +dx +ey +g = 0 into the equation k1 (x\')2 +k2 (y\')2 + (dx1 +ey1) x\' (dx2 + ey2) y\' +g = 0 without the mixed term xy, where after its elimination we can deduce the conic equation thus identifying the curve we are looking for. I present examples of conic with parallel and non-parallel axes to the coordinates of the Cartesian plane and use the geogebra software for visualization. I discuss some applications of the conic as a trajectory of celestial bodies (planet Earth and a comet), principle of reflection of parabola showing why the antennas and sound wave pickups are parabolics. I demonstrate a theorem that I named the identifier of a conic curve, with it it is possible to classify the conic without realizing the practical process only for this. I identify through the equation ax2 +bxy + cy2 +dx + ey + g = 0, what are the values of a;b, and c and, with this done, I compute the discriminant b2 - 4ac and analyze the signs and the nullity, that is, if it is greater than zero, less than zero or equal to zero, therefore is possible to classify the conic.

O problema de empacotamento de itens irregulares com balanceamento da carga é encontrado no carregamento de aviões, caminhões e navios. O objetivo é empacotar itens irregulares utilizando o menor número de recipientes possível de forma que os recipientes estejam balanceados, que os itens não se sobreponham e estejam inteiramente contidos no recipiente. Neste trabalho, propomos três heurísticas bases com três variações cada para o problema com recipientes retangulares e irregulares. As heurísticas utilizam abordagens diferentes para representar os itens e para fazer o balanceamento. Uma das heurísticas utiliza malha para representação dos itens e faz o balanceamento dividindo o recipiente em quadrantes e revezando a alocação dos itens entre eles de forma que o balanceamento é feito de forma indireta. Tal heurística resolve o problema tanto para recipientes retangulares quanto irregulares. A segunda heurística utiliza a representação dos itens por polígonos e impossibilita a sobreposição de itens utilizando a técnica do nofit polygon. A heurística constrói a solução item por item, sem posições fixas e a cada item alocado, os itens são deslocados em direção ao centro de gravidade desejado do recipiente. Esta heurística resolve apenas problemas com recipientes retangulares. A última heurística é uma adaptação da heurística anterior para a resolução do problema com recipientes irregulares, de forma que o problema é resolvido em duas fases. Cada heurística base possui três variações cada, totalizando nove heurísticas. As heurísticas foram comparadas com outro trabalho da literatura e conseguiram melhorar os resultados para nove das dezenove instâncias testadas. / The irregular bin packing problem with load balancing is found in the loading of airplanes, trucks and ships. The aim is to use as few bins as possible to pack all the items so that all bins are balanced, items do not overlap and are fully contained in the bin. In this work, we propose three base heuristics with three variations each for the problem with rectangular and irregular bin. The three heuristics use different approaches to represent the items and to balance the bin. One of the heuristics uses a grid to represent the items and does the balancing by dividing the container into quadrants and alternating the allocation of items between them so that the balancing is done indirectly. Such heuristic solves the problem for both rectangular and irregular bins. The second heuristic uses the representation of items by polygons and uses the nofit polygon technique. The heuristic constructs the solution item by item, with no fixed positions and with each item allocated, the items are shifted towards the desired center of gravity of the bin. This heuristic only solves problems with rectangular bins. The last heuristic is an adaptation of the previous one to solve the problem with irregular bins, so that the problem is solved in two phases. Each base heuristic has three variations, totaling nine heuristics. The heuristics were compared with other work in the literature and managed to improve the results for nine of the nineteen instances tested.

Traditionally, the experimental model of choice for studying the structure and dynamics of glasses or crystals are hard-sphere colloids. An analogy with molecular or atomic materials is often drawn, in which each colloidal particle represents an atom or a molecule. Making the individual particles deformable allows an even wider range of phenomena to be observed. In this thesis, I report the three-dimensional confocal microscopic study of the structure and dynamics of aqueous suspensions of fluorescently labeled poly(N-Isopropylacrylamide)-co-(Acrylic Acid), or p(NIPAm-co-AAc), microgel particles of hydrodynamic diameter 1.0 - 1.5 μm. Image analysis techniques and particle tracking algorithms are used to quantify the particle dynamics and the suspension structure. The phase behavior of the suspensions is dependent on a number of factors including pH, temperature, and concentration. By adjusting the pH, the interactions between the microgel particles can be tuned from purely repulsive near neutral pH, to weakly attractive at low pH. At low pH and low concentration, dynamic arrest results mainly from crystallization driven by the attraction between particles; crystal nucleation occurs homogeneously throughout the sample. The dynamics is nucleation limited where fast crystallization follows a delay time. At low pH and high concentration, relaxation of the suspension is constrained and it evolves only slightly to form disordered solid. At neutral pH, the dynamics are a function of the particle number concentration only; a high concentration leads to the formation of a disordered soft glassy solid. Additionally, the three-dimensional image stacks are studied to determine crystal structure by calculating pair correlation functions, g(r), bond order parameters, and structure factors, s(q). The results show that crystal structure is independent of concentration, charge, size, and stiffness of particles remaining FCC under all conditions. At low concentrations and low pH, the structures formed are polycrystalline solids. Moreover, the ability of the particles to compress enables the suspensions to maintain their crystal structure when subjected to external stress. The results help us better understand the relationship between dynamics and structure in soft colloidal suspensions, enhance our ability to use the colloids to model materials, and improve applications of the colloids in industrial products. / Physics