Problemas de corte : métodos exactos y aproximados para formulaciones mono y multi-objetivo

Los problemas de corte y empaquetado son una familia de problemas de optimización combinatoria que han sido ampliamente estudiados en numerosas áreas de la industria y la investigación, debido a su relevancia en una enorme variedad de aplicaciones reales. Son problemas que surgen en muchas industrias de producción donde se debe realizar la subdivisión de un material o espacio disponible en partes más pequeñas. Existe una gran variedad de métodos para resolver este tipo de problemas de optimización. A la hora de proponer un método de resolución para un problema de optimización, es recomendable tener en cuenta el enfoque y las necesidades que se tienen en relación al problema y su solución. Las aproximaciones exactas encuentran la solución óptima, pero sólo es viable aplicarlas a instancias del problema muy pequeñas. Las heurísticas manejan conocimiento específico del problema para obtener soluciones de alta calidad sin necesitar un excesivo esfuerzo computacional. Por otra parte, las metaheurísticas van un paso más allá, ya que son capaces de resolver una clase muy general de problemas computacionales. Finalmente, las hiperheurísticas tratan de automatizar, normalmente incorporando técnicas de aprendizaje, el proceso de selección, combinación, generación o adaptación de heurísticas más simples para resolver eficientemente problemas de optimización. Para obtener lo mejor de estos métodos se requiere conocer, además del tipo de optimización (mono o multi-objetivo) y el tamaño del problema, los medios computacionales de los que se dispone, puesto que el uso de máquinas e implementaciones paralelas puede reducir considerablemente los tiempos para obtener una solución. En las aplicaciones reales de los problemas de corte y empaquetado en la industria, la diferencia entre usar una solución obtenida rápidamente y usar propuestas más sofisticadas para encontrar la solución óptima puede determinar la supervivencia de la empresa. Sin embargo, el desarrollo de propuestas más sofisticadas y efectivas normalmente involucra un gran esfuerzo computacional, que en las aplicaciones reales puede provocar una reducción de la velocidad del proceso de producción. Por lo tanto, el diseño de propuestas efectivas y, al mismo tiempo, eficientes es fundamental. Por esta razón, el principal objetivo de este trabajo consiste en el diseño e implementación de métodos efectivos y eficientes para resolver distintos problemas de corte y empaquetado. Además, si estos métodos se definen como esquemas lo más generales posible, se podrán aplicar a diferentes problemas de corte y empaquetado sin realizar demasiados cambios para adaptarlos a cada uno. Así, teniendo en cuenta el amplio rango de metodologías de resolución de problemas de optimización y las técnicas disponibles para incrementar su eficiencia, se han diseñado e implementado diversos métodos para resolver varios problemas de corte y empaquetado, tratando de mejorar las propuestas existentes en la literatura. Los problemas que se han abordado han sido: el Two-Dimensional Cutting Stock Problem, el Two-Dimensional Strip Packing Problem, y el Container Loading Problem. Para cada uno de estos problemas se ha realizado una amplia y minuciosa revisión bibliográfica, y se ha obtenido la solución de las distintas variantes escogidas aplicando diferentes métodos de resolución: métodos exactos mono-objetivo y paralelizaciones de los mismos, y métodos aproximados multi-objetivo y paralelizaciones de los mismos. Los métodos exactos mono-objetivo aplicados se han basado en técnicas de búsqueda en árbol. Por otra parte, como métodos aproximados multi-objetivo se han seleccionado unas metaheurísticas multi-objetivo, los MOEAs. Además, para la representación de los individuos utilizados por estos métodos se han empleado codificaciones directas mediante una notación postfija, y codificaciones que usan heurísticas de colocación e hiperheurísticas. Algunas de estas metodologías se han mejorado utilizando esquemas paralelos haciendo uso de las herramientas de programación OpenMP y MPI.

IN-SITU ELECTRICAL, MECHANICAL AND ELECTROCHEMICAL CHARACTERIZATIONS OF ONE-DIMENSIONAL NANOSTRUCTURES

One-dimensional nanostructures initiated new aspects to the materials applications due to their superior properties compared to the bulk materials. Properties of nanostructures have been characterized by many techniques and used for various device applications. However, simultaneous correlation between the physical and structural properties of these nanomaterials has not been widely investigated. Therefore, it is necessary to perform in-situ study on the physical and structural properties of nanomaterials to understand their relation. In this work, we will use a unique instrument to perform real time atomic force microscopy (AFM) and scanning tunneling microscopy (STM) of nanomaterials inside a transmission electron microscopy (TEM) system. This AFM/STM-TEM system is used to investigate the mechanical, electrical, and electrochemical properties of boron nitride nanotubes (BNNTs) and Silicon nanorods (SiNRs). BNNTs are one of the subjects of this PhD research due to their comparable, and in some cases superior, properties compared to carbon nanotubes. Therefore, to further develop their applications, it is required to investigate these characteristics in atomic level. In this research, the mechanical properties of multi-walled BNNTs were first studied. Several tests were designed to study and characterize their real-time deformation behavior to the applied force. Observations revealed that BNNTs possess highly flexible structures under applied force. Detailed studies were then conducted to understand the bending mechanism of the BNNTs. Formations of reversible ripples were observed and described in terms of thermodynamic energy of the system. Fracture failure of BNNTs were initiated at the outermost walls and characterized to be brittle. Second, the electrical properties of individual BNNTs were studied. Results showed that the bandgap and electronic properties of BNNTs can be engineered by means of applied strain. It was found that the conductivity, electron concentration and carrier mobility of BNNTs can be tuned as a function of applied stress. Although, BNNTs are considered to be candidate for field emission applications, observations revealed that their properties degrade upon cycles of emissions. Results showed that due to the high emission current density, the temperature of the sample was increased and reached to the decomposition temperature at which the B-N bonds start to break. In addition to BNNTs, we have also performed in-situ study on the electrochemical properties of silicon nanorods (SiNRs). Specifically, lithiation and delithiation of SiNRs were studied by our STM-TEM system. Our observations showed the direct formation of Li22Si5 phases as a result of lithium intercalation. Radial expansion of the anode materials were observed and characterized in terms of size-scale. Later, the formation and growth of the lithium fibers on the surface of the anode materials were observed and studied. Results revealed the formation of lithium islands inside the ionic liquid electrolyte which then grew as Li dendrite toward the cathode material.

The SHIVir Survey: A Dynamical Catalogue of Virgo Cluster Galaxies and their Scaling Relations

By virtue of its proximity and richness, the Virgo galaxy cluster is a perfect testing ground to expand our understanding of structure formation in the Universe. Here, we present a comprehensive dynamical catalogue based on 190 Virgo cluster galaxies (VCGs) in the "Spectroscopy and H-band Imaging of the Virgo cluster" (SHIVir) survey, including kinematics and dynamical masses. Spectroscopy collected over a multi-year campaign on 4-8m telescopes was joined with optical and near-infrared imaging to create a cosmologically-representative overview of parameter distributions and scaling relations describing galaxy evolution in a rich cluster environment. The use of long-slit spectroscopy has allowed the extraction and systematic analysis of resolved kinematic profiles: Halpha rotation curves for late-type galaxies (LTGs), and velocity dispersion profiles for early-type galaxies (ETGs). The latter are shown to span a wide range of profile shapes which correlate with structural, morphological, and photometric parameters. A study of the distributions of surface brightnesses and circular velocities for ETGs and LTGs considered separately show them all to be strongly bimodal, hinting at the existence of dynamically unstable modes where the baryon and dark matter fractions may be comparable within the inner regions of galaxies. Both our Tully-Fisher relation for LTGs and Fundamental Plane analysis for ETGs exhibit the smallest scatter when a velocity metric probing the galaxy at larger radii (where the baryonic fraction becomes sub-dominant) is used: rotational velocity measured in the outer disc at the 23.5 i-mag arcsec^{-2} level, and velocity dispersion measured within an aperture of 2 effective radii, respectively. Dynamical estimates for gas-poor and gas-rich VCGs are merged into a joint analysis of the stellar-to-total mass relation (STMR), stellar TFR, and Mass-Size relation. These relations are all found to contain strong bimodalities or dichotomies between the ETG and LTG samples, alluding to a "mixed scenario'' evolutionary sequence between morphological/dynamical classes that involves both quenching and dry mergers. The unmistakable differentiation between these two galaxy classes appears robust against different classification schemes, and supports the notion that they are driven by different evolutionary histories. Future observations using integral field spectroscopy and including lower-mass galaxies should solidify this hypothesis.

Experiences with an Object-Oriented, Multi-Stage Language

Metaphor is a multi-stage programming language extension to an imperative, object-oriented language in the style of C# or Java. This paper discusses some issues we faced when applying multi-stage language design concepts to an imperative base language and run-time environment. The issues range from dealing with pervasive references and open code to garbage collection and implementing cross-stage persistence.