OPUS 4 | Search

Documentation and Instruction Manual of the Eddy-Covariance Software Package TK3 (2011)

Matthias Mauder Thomas Foken

no abstract

Ordering of Nanoparticles by Wrinkle-Assisted Self-Assembly : Controlling Plasmonic Coupling Effects (2011)

Alexandra Schweikart

Structures of spatial scale between 10Å and 1000Å are known as nanomaterials and have attracted immense interest over the last decades (Nobel Prize in physics in 2010 was awarded for the nanomaterial graphene). Materials within this scale show a large surface-to-volume ratio and amplify surface-related properties. Governing and manipulating material on this almost atomic level is one of the most active fields in modern natural science. Nanoscale technology, such as some of the processes involved in steel production and painting, has been empirically utilized in human society for centuries, however, a scientific investigation of phenomena on this spatial scale only began in 1857 when Michael Faraday reported on the synthesis and colors of gold colloids. In 1959 interest in the nanoscale was stimulated by an American physicist, Richard Feynman, in his famous “There’s plenty of room at the bottom” address, and the term nanotechnology first appeared in 1974 from the Japanese Norio Tanigucho. Since these pioneering works, thousands of publications have been focused on the synthesis, modification, properties and assembly of nanoparticles. Great progress has been attained in the preparation of nanoparticles of any desired size, shape and composition. Metal nanoparticles are particularly attractive due to their spectacular size and shape dependent optical and electronic properties. Color variations of nanoparticle suspension for example arise from changes in the composition, size and shape of nanoparticles, as well as from the proximity of other metal nanoparticles. The average distances of nanoparticles in thin films influence the spectral features because of inter-nanoparticle coupling. These effects are often the result of changes in the so-called surface Plasmon resonance, the frequency at which conduction electrons oscillate in response to the alternating electric field. Provided nanoparticles form ordered arrays, they can additionally have unique and fascinating optical properties because of photonic band gap effects with potential applications such as detectors, circuits, light sources, polymeric opals or meta-materials. The present work deals with the controlled placement of nanoparticles by physical con-straints. Exact placement of nanoparticles allows for the control of the inter-nanoparticle distance and thus determines the coupling effects (here: Plasmon coupling) which arise upon interaction with electromagnetic radiation. Different coupling leads to different distance-dependent signals and such substrates can serve as sensors if, for example, Raman spectroscopy is carried out for detection of the signal. Currently, most templates are created using lithographic techniques. Particularly if structures on the sub-micron scale are desired, electron beam lithography has to be used which involves environmentally harmful etching processes. Within this work we show how controlled wrinkling of a thin rigid film on a soft, elastomeric substrate, can be used as an alternative to fabricate nano-templates without using any lithography. As a substrate, a silicon elastomer poly (dimethylsiloxane) (PDMS) was used. Upon stretching such substrates uniaxially, an enlarged surface was exposed to oxygen plasma and converted to silica by oxidation. After releasing the strain, periodic wrinkles appeared perpendicular to the applied strain. Under defined conditions, such wrinkles have a regular sinusoidal topology featuring a single dominant wavelength and amplitude. The formation process could easily be tuned by tuning the plasma exposure to generate periodically structured templates between few hundreds of nanometers and several microns. In this work, wrinkled templates were tailored such that suitably sized nanoparticles could be arbitrarily assembled into a hierarchical structure by drying colloids out of suspension in a channel-like confinement offered by wrinkles in contact with a flat substrate. Using the same template geometry (same wavelength and amplitude of wrinkles) but different particle concentration of spherical polystyrene beads (r = 55nm) we found parallel particle-structures ranging from single parallel lines at low particle concentration to dense prismatic ridges at high particle concentration. The wavelength of the wrinkled template defined the spacing between the particle lines. Moreover, we performed Monte Carlo (MC) computer simulations in collaboration with the theoretical physics department (Prof. Dr. Matthias Schmidt and Dr. Andrea Fortini) at the Uni-versity of Bayreuth to assess the dominant driving forces during the assembly process. Be using MC, colloidal particle assemblies can be characterized in terms of their equilibrium configuration that minimizes the free energy. Simulations were performed on particles in a box delimited by a flat hard wall and a sinusoidal hard wall according to our experimental system. These simulations precisely predicted the exact assembled geometry in thermal equilibrium. Comparing results of simulation and experiment we found perfect agreement between the equilibrium structures. We discovered the confinement itself to be mainly responsible for the assembled morphology of nanoparticle, which makes the process independent of the detailed chemistry of particles. In addition we obtained very similar structures with the same assembly strategy but using gold nanoparticles (r = 33 nm) instead of polymeric particles. We fabricated lines of gold nanoparticles assembled in a single file and lines two particles wide using similar particle concentration but different sizes of the confinement template. The different morphologies of the lines give rise to different optical signals as collective oscillation of conduction electrons result in different interaction with electromagnetic radiation. Surface Plasmon resonance due to Plasmon coupling between adjacent particles arises. Different morphology-dependent signals of nanoparticles in contact within the lines were detected by surface enhanced Raman spectroscopy (SERS). The electromagnetic field was measured to be randomly distributed along the particle lines with strong enhancements at so-called hot spots located at gaps between neighboring nano-particles. To confirm the measured signal we compared theoretical simulations using the finite-difference time-domain (FDTD) method and experimentally measured dark-field spectroscopy signal along differently shaped lines of particles within a collaboration with Weihai Ni and Dr. Ramón Alvarez-Puebla at the University of Vigo in Spain. Good agreement between theory and experiment indicated that indeed plasmonic coupling of the individual nanoparticles is responsible for the observed SERS effects: Using wrinkle-assisted self-assembly it is possible to control the organization of the colloidal particles on the substrate, with a consequent control over the formation of hot spots and the resulting SERS intensity. Such ordered multiplicities of hot spots give rise to quantitative SERS signals with high sensitivity which has applications as diverse as biological detectors, optical filters and sensors. In addition, this work deals with chemical modification of the wrinkled structure to render it accessible to different solvents as PDMS tends to swell in organic solvents and suffers from poor mechanical stability. Additionally, wrinkles fabricated through a buckling instability of a stiff supported layer under compression are not tension free on the microscopic level and suffer from relaxation on a longer time scale. We introduce in this work two different methods to replicate wrinkles by molding. In micro thermoforming, the wrinkled surface was used as a mold (or caliber) to structure different kinds of polymers (polystyrene and poly (methylmethacrylate)) by pressing the originally wrinkled structure onto a ductile material which preserves the nanostructure after curing. The second methodology was carried out in collaboration with PD. Dr. Kerstin Koch and Michael Bennemann at the Nees institute in Bonn and employed a two-step molding process, where wrinkles were molded against wax and in a second step, the structured wax was cast against epoxy resin. Both methods revealed perfect copies of the wrinkled original with high fidelity even at dimensions as small as a few hundred nanometers and hold no residual stresses because there is only one component. Wrinkles made of tough polymers are now accessible to various solvents which make them potential substrates for microfluidics. In the last part of this work, wrinkles are used as stamps in so-called micro contact printing (µCP). In this technique, a structured elastomeric stamp is used to transfer a surface-active molecule out of solution to a flat substrate by mechanical contact. Patterns of different charge density can be created which have applications in the field of biosensors, diagnostic immunoassays and cell culturing. Traditionally, stamps for µCP are prepared by a two step process where a lithographically fabricated structured silicon master serves as mold. An elastomeric polymer is cast against the caliber and preserves the structure after curing and detaching. As already mentioned lithography is expensive and involves environmentally harmful etching processes. Within this work we introduce the one step wrinkling process to fabricate structured stamps. Even though the diversity of stamp geometries created by wrinkling is limited, the simplicity compared to lithographic techniques is evident. The process of wrinkle formation includes plasma oxidation, which renders the topmost surface hydrophilic. Therefore, charged macromolecules out of aqueous solution were adsorbed onto the surface. The coated relief structure was used as a stamp to transfer the molecules selectively from the elevated parts of the wrinkles to another flat, oppositely charged surface by means of µCP. The topography of the resulting pattern was characterized by Atomic Force Microscopy (AFM) imaging as alternating charged pattern of printed (elevated) and non-printed areas. By varying the geometry of the wrinkled stamp (amplitude and wavelength) we studied the limits in which successful µCP with wrinkles can be carried out. We found the limits for wavelength of the wrinkles below 355nm and amplitudes below 40nm at which the printed structure disappeared because material was transferred from the wrinkles’ hills as well as from the bottom parts. The height of the transferred structure increase with increasing wavelength and amplitude of the wrinkles but tended to a limit of 6-7nm, even though the topology of the stamp increases. The smallest structure found in lateral dimensions was as small as 50nm, appearing as areas where no material was transferred.

Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods (2011)

Stefan Heinz Jörg Rambau Andreas Tuchscherer

We develop a method to approximate the value vector of discounted Markov decision problems (MDP) with guaranteed error bounds. It is based on the linear programming characterization of the optimal expected cost. The new idea is to use column generation to dynamically generate only such states that are most relevant for the bounds by incorporating the reduced cost information. The number of states that is sufficient in general and necessary in the worst case to prove such bounds is independent of the cardinality of the state space. Still, in many instances, the column generation algorithm can prove bounds using much fewer states. In this paper, we explain the foundations of the method. Moreover, the method is used to improve the well-known nearest-neighbor policy for the elevator control problem.

Jahresbericht Universitätsbibliothek Bayreuth (2011)

Jahresbericht der Universitätsbibliothek Bayreuth - Berichtsjahr 2009

Klassifikation gewisser Darstellungen halbeinfacher Liealgebren (2011)

Ridvan Güner

Zusammenfassung Die Arbeit behandelt folgende Fragen aus der Darstellungs- und Invariantentheorie halbeinfacher Liealgebren: Gegeben eine halbeinfache (meist: eine einfache) komplexe endlich dimensionale Liealgebra L . Betrachtet wird das Monoid M = M(L) der Äquivalenzklassen der endlich dimensionalen irreduziblen komplexen Darstellungen von L . M wird identifiziert mit dem Gitter der entsprechenden höchsten Gewichte (bezüglich einer ausgewählten Cartanalgebra von L und einer ausgewählten Basis der zugehörigen Wurzeln). Diese Identifizierung liefert die Monoidstruktur von M . Zu einer Darstellung pi von L kann man die symmetrische Algebra von pi betrachten (als unendlich dimensionale Darstellung, welche die symmetrischen Potenzen von pi als endlich dimensionale direkte Summanden enthält.) Ein höchstes Gewicht von L , das als höchstes Gewicht einer irreduziblen Komponente in einer n-ten symmetrischen Potenz von pi auftritt, sei gutes dominantes Gewicht genannt. Die Menge aller guten dominanten Gewichte bildet ein Untermonoid M(pi) des Monoids M . Solch ein M(pi) besitzt einen natürlich definierten Rang r(pi) , der größer-gleich 1 und kleiner-gleich r ist. (S. Seite 8 der Arbeit in der Einleitung.) Hier ist r der Rang von L , d.h. die Dimension einer Cartanunteralgebra von L . Nun: Eine Darstellung pi von L sei gut genannt, wenn r(pi) kleiner als r ist, und schlecht, wenn r(pi) gleich r ist. In den Paragraphen 4 und 5 der Arbeit werden dann - explizit als L-Darstellungen - die n-ten symmetrischen Potenzen der guten Darstellungen pi beschrieben. Im ersten Paragraphen der Arbeit wird nachgewiesen, dass Darstellungen bis auf wenige Ausnahmen schlecht sind, und es werden Listen von schlechten Darstellungen verifiziert. Letztlich werden die Typen der einfachen Liealgebren - die vier klassischen Reihen und die fünf Ausnahmealgebren - einzeln und individuell abgehandelt. In diesem ersten Paragraphen der Arbeit werden, wie auch später, entscheidend explizite Ausreduzierungen von symmetrischen Potenzen von Darstellungen benutzt, die in ausführlichen Listen zusammengestellt sind, s. Liste 1 und Liste 2 am Ende der Arbeit. (Die Berechnungen wurden mit dem Lie-Berechnungspaket aus [van Leeuwen] gemacht. In Einzelfällen werden auch explizite Ausreduzierungssätze benutzt, weil versucht wird, bei den Beweisen Argumente aus der Darstellungstheorie zu bevorzugen. Gemäß dem ersten Paragraphen sind für die einzelnen Typen einfacher Liealgebren fast alle irreduziblen Darstellungen schlecht. Bei jedem Typ bleibt nur eine kurze Liste von möglicherweise guten Darstellungen übrig. In Paragraph 2 werden nun die Darstellungen in diesen Restlisten als tatsächlich gut nachgewiesen. Paragraph 3 gibt eine Zusammenfassung der guten Darstellung unter einem anderen Gesichtspunkt: Die guten Darstellungen sind geordnet nach ihrem Rang (und nicht nach dem Isomorphietyp der Liealgebra ). In den Paragraphen 4 und 5 wird - für alle guten irreduziblen Darstellungen pi - die genaue Struktur (als vollständig reduzible Darstellung) der symmetrischen Potenzen von pi bestimmt. Benutzt wird dabei auch detailliertere Invariantentheorie und die Kenntnis von Hauptisotropiegruppen bei Darstellungsräumen.

Tagungsband zum Doctoral Consortium der WI 2011 (2011)

Torsten Eymann

Since the early 1990es, young researchers participate in the doctoral consortium series, co-located with the "Wirtschaftsinformatik" conference. This volume contains the selected papers of 20 PhD candidates of the 2011 doctoral consortium in Zurich.

Women's Life Worlds 'In-Between' (2011)

Antje Daniel Katharina Fink Lena Kroeker Jaana Schütze

This volume of Bayreuth African Studies Working Papers authored and edited by doctoral students of the Bayreuth International Graduate School of African Studies (BIGSAS) represents challenges and (im-)possibilities of reviewing women’s life worlds in Africa. Therewith we revive an old debate: African thinkers opposed Western concepts, searching for a kind of feminism beyond traditional roles and beyond Western feminism, which basically antagonizes women’s subordination due to patriarchy. Thus, if African women have different positions to Western feminism, how do they perceive themselves? To what extent are women expanding their social, political or economic realm? Does this change result in a re-definition of gender roles? How do women in Africa deal with gendered hierarchies and authority? Are there conflicts or ‘in-betweens’ among ‘traditional roles’ and the behavior of women? All these questions surround one core content: women’s life worlds ‘in-between’. ‘In-betweenness’ refers here to a situation when the life worlds of women transform, resulting from social, political, economic or environmental changes or uncertainties. In such a situation women negotiate between conflicting or contradictory assumed norms, roles, social practices or orders. Opportunities for women may change, expand or become limited. For example, women can rethink their roles and behavior, be it temporary or in long term perspectives. Following this view the authors focus on situations of ‘in-betweenness’ of women in different African countries and in diverse realms of life. Literary scholar Samuel Ndogo analyzes the autobiography of an exceptional Kenyan author and activist: Wangari Maathai. The title of her autobiography, Unbowed (2006), already suggests friction between her life trajectory and cultural notions of womanhood. However, the title also shows pride at having withstood opposition, which at the same time contests a society’s readiness to tolerate an exception. Katharina Nambula’s paper shares Ndogo’s perspective of Literature Studies and shows how the female protagonists in Waiting, written by Goretti Kyomuhendo (2007), survive in a politically instable and male dominated society during the reign of Idi Amin in Uganda. Facing the men's inability to sort out the chaos, Kyomuhendo’s female characters temporarily deploy their hidden strengths to resume some order. As soon as men re-enter their former positions though, gender relations are back to normal. Other aspects of uncertainty and how women deal with it are discussed by Serah Kiragu. With regard to global climate change, Kiragu assesses changes in women’s livelihoods in semi arid Kenya. She describes the women’s recent difficulties and how they are coping with a changing environmental situation. This approach vividly illustrates that a notion of women as passive victims does not hold. Young rural women in Northern Ghana change their social sphere altogether – at least temporarily. In his anthropological article, Christian Ungruhe describes how a whole generation of young girls move out from their rural homes to urban centers. They become actively involved in labor migration and therewith experience economic independence in an attempt to generate their dowry, acquire modern assets, and consummate relationships. Although the journey marks a temporary phase in the women’s lives, it is an important experience which they can bring to their future rural lives and a permanent phenomenon in women’s biographies in West Africa. In contrast, women in Lesotho participate in wage labor on a permanent basis. Lena Kroeker illustrates in a historic and ethnographic overview why Lesotho ranks 8th in the Global Gender Gap Index 2010 and how women’s high level of participation did not change but merely separated gender and generations. Various civil society representatives met at the World Social Forum with the aim of creating a more equal and just world. Antje Daniel portraits the strategies and main features of Brazilian and Kenyan women’s organizations and explains how characteristics of women’s organizations in the national context determine transnational activism within the space of the World Social Forum. All contributions not only illustrate contemporary life worlds of women but depict processes of change within them from the perspectives of African Literature, Geography, Anthropology and Sociology. The articles in this first issue of BIGSASworks! from a broad spectrum of disciplines provide fresh and original perspectives on an evergreen debate as well as unique empirical material.

Dynamics and statistics of hydrodynamically interacting particles in laminar flows (2011)

Jochen Bammert

The subject of this thesis is the investigation of the dynamics and statistics of hydrodynamically interacting particles in low Reynolds number flows, which is discussed in three interrelated themes. The first theme focuses on polymer fractionation. With our basic model we explore the possibility to sort dumbbells with respect to their size using a two dimensional periodic potential. It turns out that the purely diffusive behavior of a dumbbell in this structured landscape is dominated by the ratio of two characteristic length scales, namely the wavelength of the potential l and the size of the dumbbell b. We explain why the diffusion constant in the potential plane shows a pronounced local maximum around l/b equal 3/2. Furthermore, the influence of the spring rigidity and the hydrodynamic interaction on the diffusive motion are examined as well as the dumbbell statistics. If the dumbbell is driven by an external flow through the periodic landscape two different kinds of motion occur: transport along a potential valley and a stair-like motion oblique to the trenches. In the latter case, the dumbbell jumps regularly to a neighboring valley which results in an effective deflection. The onset of the oblique movement as well as the deflection angle beta depend on the hydrodynamic interaction, on the ratio l/b, and on the Brownian motion of the beads. Especially the significant dependence of beta on l/b enables particle sorting. The results are published. The second theme deals with the Brownian dynamics in shear flows. Here, we investigate the correlations of particle fluctuations in order to characterize the direct interplay between thermal motion, hydrodynamic interactions, and non-uniform flows.With respect to the experimental implementation the particles are caught by harmonic potentials. First, we consider one trapped Brownian bead in linear shear and Poiseuille flows. The correlation functions of the particle’s position and velocity fluctuations are calculated analytically. The main result is the occurrence of shear-induced cross-correlations between orthogonal fluctuations in the shear plane which are asymmetric in time. Moreover, the positional probability distribution, P(r), of a single bead in both types of flow is determined. In Poiseuille flow, where no analytical solutions can be obtained, we use perturbation expansions to derive formulas for P(r) that are valuable for the analysis of experimental data. In the case of a linear shear flow, a connection between the static correlations and the distribution functions is derived which allows a consistency check between independent measurements. Considering a system with several Brownian particles it is obvious that hydrodynamic interactions influence the correlations. In order to investigate this effect, we calculate the positional correlation functions for a setup of two trapped Brownian beads which are exposed to a linear shear flow. As expected, the one-particle correlations change compared to the single particle case described above. They depend on the distance between the two beads. In addition, we find inter-particle correlations between orthogonal positional fluctuations of different particles. The structure of these new cross-correlations depends significantly on the relative orientation of the two beads in the shear flow. They can have zero, one, or two local extrema as a function of time. In collaboration with Prof. Wagner from Saarbrücken some of our predictions are already confirmed by experiments, where polystyrene beads are caught by optical traps and simultaneously exposed to linear shear flows in a special microfluidic device. The results are published and further investigations are in progress.The third theme concentrates on the rheology of colloidal suspensions. Our deterministic model system consists of Hookean dumbbells suspended in a confined Newtonian fluid under constant shear. We perform a numerical study using fluid particle dynamics simulations, where the effective viscosity of the suspension, eta, and the dumbbell statistics are determined. The investigations on the tumbling motion of a single dumbbell reveals that eta is influenced by three different contributions: the volume fraction occupied by the dumbbell, the hydrodynamic interaction between the beads, and elastic correlation effects. For a suspension of independent spheres we observe in our simulations that the viscosity, as a function of the volume fraction Phi, differs from the prediction of Einstein, Batchelor and Green if Phi becomes larger than 8%. Replacing the beads by dumbbells leads to an increase of eta , which depends significantly on the length of the springs connecting the two beads. The distribution function for the orientation angle of the dumbbells indicates the complex motion of the individual objects in the suspension, which may lead to the so-called elastic turbulence, as experimentally discovered by Groisman and Steinberg.

Development of Bacillus subtilis spores and cells for surface display of proteins (2011)

Quynh Anh Nguyen

Surface display has attracted the attention of researchers in developing efficient display systems expressing heterologous polypeptides on the surface of bioparticles such as phages, bacterial and eukaryotic cells and bacterial spores. Among these bioparticles, the endospore from B. subtilis has advantages, including feasibility of production, safety feature, the robustness of the bacterial spore allowing storage in the desiccated form, a technological platform supported by extensive tools for genetic manipulation and less size restrictions of the displayed proteins compared to cell- and phage-based systems. A strategy to engineer B. subtilis spores to display heterologous protein on their surface is to use outer spore coat proteins (CotB, CotC, CotG) or an inner-coat protein (OxdD) with the coat genes’ transcriptional and translational signals as carriers (Isticato et al., 2001; Mauriello et al., 2004; Hinc et al., 2010; Zhou et al., 2008a; Potot et al., 2010; Kim et al., 2005a; Kwon et al., 2007). This strategy guarantees the timing for fusion protein synthesis during coat formation, but the amount of produced fusion proteins cannot be controlled. Therefore, the first aim of this doctoral thesis focused on construction of more effective expression systems for spore surface protein anchoring. A novel approach of substitution of native promoter by two different IPTG-inducible promoters to the increase the production of fusion protein is presented here. CotB was used and the expression of the cotB gene was regulated by either its own promoter, the Pgrac and the PSgrac promoter in a series of plasmids which can be integrated into or replicated independently of the B. subtilis chromosomal DNA. Two reporter proteins, α-amylase Q from B. amyloliquefaciens (AmyQ) (Palva, 1982) and GFPuv – an enhanced version from the GFP protein of the jellyfish Aequorea victoria (Crameri et al., 1996), were fused downstream of the CotB protein. To assess the enhancement of GFPuv displayed on the spore surface, CotC and CotG were similarly examined. The results indicated that the Pgrac promoter is a suitable, hence recommended as a promoter of choice. Substitution of the native promoter by Pgrac promoter, the amount of proteins displayed per spore can be increased two-fold. Furthermore, the display of heterologous proteins on the spore surface when using different carriers is gene dosage dependent. And for the first time, the tendency of the three Cot proteins’ localization on the spore coat compartment is reported using the GFPuv tag. Second, a new B. subtilis spore-based system for protein expression and purification was developed. Using this system, proteins prone to form inclusion bodies can be anchored on the spore surface, separated by a mini-intein derived from the SSp DnaB, which was then used as self-cleaving tag for purification by shifting the pH and/or temperature conditions, with no addition of any proteases or thiol reagent (Mathys et al., 1999). To construct the system, the mini-intein was fused downstream of the CotB protein, followed by the reporter protein AmyQ. By changing the pH of the buffer, the mini-intein self-cleaving process was induced followed by the release of α-amylase into the supernatants. This observation suggests the use of the B. subtilis spores as an effective and low cost tool for protein purification. However, concerns related to premature of the pH-inducible mini-intein and auto-release of coat protein raise the question about the stability of the fusion coat-heterologous protein on the spore surface using the system. Hence, further investigation is needed to achieve a usable spore-based purification system. The last aim of the thesis was to apply the newly constructed B. subtilis spore display and the cell surface display systems (Nguyen and Schumann, 2006) to generate cellulose chips, in which enzymes were immobilized on the surface of microorganism cells or spores. The cellulase A (CelA) from C. thermocellum (Beguin et al., 1985) was utilized as a model enzyme. Unfortunately, the results showed an ineffective anchoring of CelA on the cell wall. This indicates the unsuccessful creation of cell-based cellulase chip when using the SrtA transpeptidase. In contrast, CelA was verified to be successfully displayed on the spore surface using CotB and CotG, but not CotC, as carriers. In general, a large volume of culture (up to one liter) must be prepared containing both cells and spores displaying CelA on the surface to assure sufficient CMC degradation. This might indicate a low activity of CelA. Further works should be done in selection of cellulase and improvement of the systems to generate the more effective cellulase chips.

A generalized job-shop problem with more than one resource demand per task (2011)

Joachim Schauer Cornelius Schwarz

We study a generalized job-shop problem called the Laser Sharing Problem with fixed tours (LSP-T) where the tasks may need more than one resource simultaneously. This fact will be used to model possible collisions between industrial robots. For three robots we will show that the special case where only one resource is used by more than one robot is already NP-hard. This also implies that one machine scheduling with chained min delay precedence constraints is NP-hard for at least three chains. On the positive side, we present a polynomial algorithm for the two robot case and a pseudo-polynomial algorithm together with an FPTAS for an arbitrary but constant number of robots. This gives a sharp boundary of the complexity status for a constant number of robots.

Refine

Author

Year of publication

Document Type

Language

Keywords

Institute

88 search hits