Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 × faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.

An integer programming framework for sequencing cutting patterns based on interval graph completion

We derived a framework in integer programming, based on the properties of a linear ordering of the vertices in interval graphs, that acts as an edge completion model for obtaining interval graphs. This model can be applied to problems of sequencing cutting patterns, namely the minimization of open stacks problem (MOSP). By making small modifications in the objective function and using only some of the inequalities, the MOSP model is applied to another pattern sequencing problem that aims to minimize, not only the number of stacks, but also the order spread (the minimization of the stack occupation problem), and the model is tested.

Sequencing cutting patterns with colored interval graphs

The problem addressed here originates in the industry of flat glass cutting and wood panel sawing, where smaller items are cut from larger items accordingly to predefined cutting patterns. In this type of industry the smaller pieces that are cut from the patterns are piled around the machine in stacks according to the size of the pieces, which are moved to the warehouse only when all items of the same size have been cut. If the cutting machine can process only one pattern at a time, and the workspace is limited, it is desirable to set the sequence in which the cutting patterns are processed in a way to minimize the maximum number of open stacks around the machine. This problem is known in literature as the minimization of open stacks (MOSP). To find the best sequence of the cutting patterns, we propose an integer programming model, based on interval graphs, that searches for an appropriate edge completion of the given graph of the problem, while defining a suitable coloring of its vertices.

Kitchen robot prod. line development. Proj. of Bowden cables cutting and thermal forming machine.

This document presents particular description of work done during student’s internship in PR Metal company realized as ERASMUS PROJECT at ISEP. All information including company’s description and its structure, overview of the problems and analyzed cases, all stages of projects from concept to conclusion can be found here. Description of work done during the internship is divided here into two pieces. First part concerns one activities of the company which is robotic chefs (kitchen robot) production line. Work, that was done for development of this line involved several tasks, among them: creating a single-worker montage station for screwing robots housing’s parts, improve security system for laser welding chamber, what particularly consists in designing automatically closing door system with special surface, that protects against destructive action of laser beam, test station for examination of durability of heating connectors, solving problem with rotors vibrations. Second part tells about main task, realized in second half of internship and stands a complete description of machine development and design. The machine is a part of car handle latch cable production line and its tasks are: cutting cable to required length and hot-forming plastic cover for further assembly needs.

Female Genital Mutilation/Cutting - A Literature Review

This report represents the result of two different strands of work by the Women's Health Council. At the beginning of 2006, due to the recent significant inward migration experienced in Ireland, the Council's board identified the promotion of the health of ethnic minority women as a key area of work in its strategic plan for the period 2007-2009. At the same time, it was also decided that the problem of gender-based violence would also be addressed through a number of research and policy initiatives. This report focuses on a health issuethat marries these two concerns, Female Genital Mutilation/Cutting (FGM/C – see below for definition) and serves as an accompanying document to the recently published Violence Against Women and Health (2007) and the forthcoming study on Ethnic Minority Women and Gender-Based Violence. Download document here

Flexible multivariate GARCH modeling with an application to international stock markets

The goal of this paper is to estimate time-varying covariance matrices.Since the covariance matrix of financial returns is known to changethrough time and is an essential ingredient in risk measurement, portfolioselection, and tests of asset pricing models, this is a very importantproblem in practice. Our model of choice is the Diagonal-Vech version ofthe Multivariate GARCH(1,1) model. The problem is that the estimation ofthe general Diagonal-Vech model model is numerically infeasible indimensions higher than 5. The common approach is to estimate more restrictive models which are tractable but may not conform to the data. Our contributionis to propose an alternative estimation method that is numerically feasible,produces positive semi-definite conditional covariance matrices, and doesnot impose unrealistic a priori restrictions. We provide an empiricalapplication in the context of international stock markets, comparing thenew estimator to a number of existing ones.

Cutting of Frozen Wood

The objective of this master's thesis was to develop a system for measuring the cutting forces of frozen wood. In northern parts of the world cuttingof frozen wood is one of the major problem. During winter and early spring the temperature inside the wood cells will fall below Zero degrees that strongly influences on the properties of the wood. These variations of properties will effects on the blade nomenclature while cutting the frozen wood. However the end results will cause uneven cutting forces. Cutting forces, Chip formation, wearing of the blade and the quality of the machined surface are difficult task. In this project we are attempting to find the variation of cutting forces and properties of frozen wood at four different temperatures (-20 , -10, 0 and + 10 degrees). The linear planning machine was used for measuring the cuttingforces. The cutting was done parallel to the long axis of wood due to the nature of pine wood and the structure of the plane. A considerable amount of work andtime was used for collecting and processing the numerical information from the sensors of the measuring system. There were some alterations suggested to the construction of the plane and the sensor system.

The global carbon budget:a conflicting claims problem

Despite global environmental governance has traditionally couched global warming in terms of annual CO2 emissions (a flow), global mean temperature is actually determined by cumulative CO2 emissions in the atmosphere (a stock). Thanks to advances of scientific community, nowadays it is possible to quantify the \global carbon budget", that is, the amount of available cumulative CO2 emissions before crossing the 2oC threshold (Meinshausen et al., 2009). The current approach proposes to analyze the allocation of such global carbon budget among countries as a classical conflicting claims problem (O'Neill, 1982). Based on some appealing principles, it is proposed an efficient and sustainable allocation of the available carbon budget from 2000 to 2050 taking into account different environmental risk scenarios. Keywords: Carbon budget, Conflicting claims problem, Distribution, Climate change. JEL classification: C79, D71, D74, H41, H87, Q50, Q54, Q58.

The cutting of cocaine and heroin: a critical review

The illicit drug cutting represents a complex problem that requires the sharing of knowledge from addiction studies, toxicology, criminology and criminalistics. Therefore, cutting is not well known by the forensic community. Thus, this review aims at deciphering the different aspects of cutting, by gathering information mainly from criminology and criminalistics. It tackles essentially specificities of cocaine and heroin cutting. The article presents the detected cutting agents (adulterants and diluents), their evolution in time and space and the analytical methodology implemented by forensic laboratories. Furthermore, it discusses when, in the history of the illicit drug, cutting may take place. Moreover, researches studying how much cutting occurs in the country of destination are analysed. Lastly, the reasons for cutting are addressed. According to the literature, adulterants are added during production of the illicit drug or at a relatively high level of its distribution chain (e.g. before the product arrives in the country of destination or just after its importation in the latter). Their addition seems hardly justified by the only desire to increase profits or to harm consumers' health. Instead, adulteration would be performed to enhance or to mimic the illicit drug effects or to facilitate administration of the drug. Nowadays, caffeine, diltiazem, hydroxyzine, levamisole, lidocaïne and phenacetin are frequently detected in cocaine specimens, while paracetamol and caffeine are almost exclusively identified in heroin specimens. This may reveal differences in the respective structures of production and/or distribution of cocaine and heroin. As the relevant information about cutting is spread across different scientific fields, a close collaboration should be set up to collect essential and unified data to improve knowledge and provide information for monitoring, control and harm reduction purposes. More research, on several areas of investigation, should be carried out to gather relevant information.

Advanced ceramics: evaluation of the mechanism of stock removal and ground surface quality

The aim of this work is to evaluate the mechanism of stock removal and the ground surface quality of advanced ceramics machined by a surface grinding process using diamond grinding wheels. The analysis of the grinding performance was done regarding the cutting surface wear behavior of the grinding wheel for ceramic workpieces. The ground surface was evaluated using Scanning Electron Microscopy (SEM). As a result it can be said that the mechanism of material removal in the grinding of ceramic is largely one of brittle fracture. The increase of the h max can reduce the tangential force required by the process. Although, it results in an increase in the surface damage, reducing the mechanical properties of the ground component.

Low variation in ribosomal DNA and internal transcribed spacers of the symbiotic fungi of leaf-cutting ants (Attini: Formicidae)

Leaf-cutting ants of the genera Atta and Acromyrmex (tribe Attini) are symbiotic with basidiomycete fungi of the genus Leucoagaricus (tribe Leucocoprineae), which they cultivate on vegetable matter inside their nests. We determined the variation of the 28S, 18S, and 5.8S ribosomal DNA (rDNA) gene loci and the rapidly evolving internal transcribed spacers 1 and 2 (ITS1 and ITS2) of 15 sympatric and allopatric fungi associated with colonies of 11 species of leafcutter ants living up to 2,600 km apart in Brazil. We found that the fungal rDNA and ITS sequences from different species of ants were identical (or nearly identical) to each other, whereas 10 GenBank Leucoagaricus species showed higher ITS variation. Our findings suggest that Atta and Acromyrmex leafcutters living in geographic sites that are very distant from each other cultivate a single fungal species made up of closely related lineages of Leucoagaricus gongylophorus. We discuss the strikingly high similarity in the ITS1 and ITS2 regions of the Atta and Acromyrmex symbiotic L. gongylophorus studied by us, in contrast to the lower similarity displayed by their non-symbiotic counterparts. We suggest that the similarity of our L. gongylophorus isolates is an indication of the recent association of the fungus with these ants, and propose that both the intense lateral transmission of fungal material within leafcutter nests and the selection of more adapted fungal strains are involved in the homogenization of the symbiotic fungal stock.

Feasibility of industrial implementation of laser cutting into paper making machine

Laser cutting implementation possibilities into paper making machine was studied as the main objective of the work. Laser cutting technology application was considered as a replacement tool for conventional cutting methods used in paper making machines for longitudinal cutting such as edge trimming at different paper making process and tambour roll slitting. Laser cutting of paper was tested in 70’s for the first time. Since then, laser cutting and processing has been applied for paper materials with different level of success in industry. Laser cutting can be employed for longitudinal cutting of paper web in machine direction. The most common conventional cutting methods include water jet cutting and rotating slitting blades applied in paper making machines. Cutting with CO2 laser fulfils basic requirements for cutting quality, applicability to material and cutting speeds in all locations where longitudinal cutting is needed. Literature review provided description of advantages, disadvantages and challenges of laser technology when it was applied for cutting of paper material with particular attention to cutting of moving paper web. Based on studied laser cutting capabilities and problem definition of conventional cutting technologies, preliminary selection of the most promising application area was carried out. Laser cutting (trimming) of paper web edges in wet end was estimated to be the most promising area where it can be implemented. This assumption was made on the basis of rate of web breaks occurrence. It was found that up to 64 % of total number of web breaks occurred in wet end, particularly in location of so called open draws where paper web was transferred unsupported by wire or felt. Distribution of web breaks in machine cross direction revealed that defects of paper web edge was the main reason of tearing initiation and consequent web break. The assumption was made that laser cutting was capable of improvement of laser cut edge tensile strength due to high cutting quality and sealing effect of the edge after laser cutting. Studies of laser ablation of cellulose supported this claim. Linear energy needed for cutting was calculated with regard to paper web properties in intended laser cutting location. Calculated linear cutting energy was verified with series of laser cutting. Practically obtained laser energy needed for cutting deviated from calculated values. This could be explained by difference in heat transfer via radiation in laser cutting and different absorption characteristics of dry and moist paper material. Laser cut samples (both dry and moist (dry matter content about 25-40%)) were tested for strength properties. It was shown that tensile strength and strain break of laser cut samples are similar to corresponding values of non-laser cut samples. Chosen method, however, did not address tensile strength of laser cut edge in particular. Thus, the assumption of improving strength properties with laser cutting was not fully proved. Laser cutting effect on possible pollution of mill broke (recycling of trimmed edge) was carried out. Laser cut samples (both dry and moist) were tested on the content of dirt particles. The tests revealed that accumulation of dust particles on the surface of moist samples can take place. This has to be taken into account to prevent contamination of pulp suspension when trim waste is recycled. Material loss due to evaporation during laser cutting and amount of solid residues after cutting were evaluated. Edge trimming with laser would result in 0.25 kg/h of solid residues and 2.5 kg/h of lost material due to evaporation. Schemes of laser cutting implementation and needed laser equipment were discussed. Generally, laser cutting system would require two laser sources (one laser source for each cutting zone), set of beam transfer and focusing optics and cutting heads. In order to increase reliability of system, it was suggested that each laser source would have double capacity. That would allow to perform cutting employing one laser source working at full capacity for both cutting zones. Laser technology is in required level at the moment and do not require additional development. Moreover, capacity of speed increase is high due to availability high power laser sources what can support the tendency of speed increase of paper making machines. Laser cutting system would require special roll to maintain cutting. The scheme of such roll was proposed as well as roll integration into paper making machine. Laser cutting can be done in location of central roll in press section, before so-called open draw where many web breaks occur, where it has potential to improve runability of a paper making machine. Economic performance of laser cutting was done as comparison of laser cutting system and water jet cutting working in the same conditions. It was revealed that laser cutting would still be about two times more expensive compared to water jet cutting. This is mainly due to high investment cost of laser equipment and poor energy efficiency of CO2 lasers. Another factor is that laser cutting causes material loss due to evaporation whereas water jet cutting almost does not cause material loss. Despite difficulties of laser cutting implementation in paper making machine, its implementation can be beneficial. The crucial role in that is possibility to improve cut edge strength properties and consequently reduce number of web breaks. Capacity of laser cutting to maintain cutting speeds which exceed current speeds of paper making machines what is another argument to consider laser cutting technology in design of new high speed paper making machines.

The Impact of Recycling on the Long-Run Stock of Trees

Interest in recycling of forest products has grown in recent years, one of the goals being to conserve the stock of trees or possibly increase it to compensate for positive externalities generated by the forest and neglected by the market. This paper explores the issue as to whether recycling is an appropriate measure to attain such a goal. We do this by considering the problem of the private owner of an area of land, who, acting as a price taker, decides how to allocate his land over time between forestry and some other use, and at what age to harvest the forest area chosen. Once the forest is cut, he makes a new land allocation decision and replants. He does so indefinitely, in a Faustmann-like framework. The wood from the harvest is transformed into a final product which is partly recycled into a substitute for the virgin wood, so that past output affects the current price. We show that in such a context, increasing the rate of recycling will result in less area being devoted to forestry. It will also have the effect of increasing the harvest age of the forest, as long as the planting cost is positive. The net effect on the flow of virgin wood being harvested to supply the market will as a result be ambiguous. The main point however is that recycling will result in a smaller, not a larger, stock of trees in the long run. It would therefore be best to resort to other means if the goal is to increase the stock of trees.

Essais sur la gestion des ressources forestières

Cette thèse est composée de trois essais en économie forestière. Les deux premiers s'intéressent à la fixation de la redevance optimale à laquelle fait face le propriétaire d'une ressource forestière dans un contexte d'information asymétrique. Le troisième analyse l'impact à long terme du recyclage sur la surface de terre affectée à la forêt. La gestion des ressources forestières implique souvent la délégation des droits de coupe par le propriétaire forestier à une entreprise exploitante. Cette délégation prend la forme d'un contrat de concession par lequel le propriétaire forestier octroie les droits d'exploitation aux compagnies forestières, en contrepartie d'une redevance (transfert monétaire). L'octroie des droits d'exploitation s'effectue généralement sous plusieurs modes, dont les plus répandus sont les appels d'offres publics et les contrats de gré à gré, où le propriétaire forestier et la firme exploitante spécifient entre autres la redevance dans les clauses d'exploitation de la forêt. Pour déterminer le mécanisme optimal (choix de la firme, âge de coupe et redevance), le propriétaire forestier a idéalement besoin de connaître les coûts de coupe et de reboisement. Or en réalité, les firmes sont mieux informées sur leurs coûts que le propriétaire forestier. Dans ce contexte d'information asymétrique, le mécanisme optimal doit donc prendre en considération des contraintes informationnelles. Les deux premiers essais caractérisent, sous ces conditions, l'âge de coupe optimal (la rotation optimale) et la redevance optimale. Le premier essai examine le contrat optimal quand le propriétaire forestier cède les droits de coupes à une firme par un accord de gré à gré ou par une procédure d'appel d'offre public au second prix. L'analyse du problème est menée premièrement dans un contexte statique, dans le sens que les coûts de coupe sont parfaitement corrélés dans le temps, puis dans un contexte dynamique, où les coûts sont indépendants dans le temps. L'examen en statique et en dynamique montre que la rotation optimale va satisfaire une version modifiée de la règle de Faustmann qui prévaudrait en information symétrique. Cette modification est nécessaire afin d'inciter la firme à révéler ses vrais coûts. Dans le cas statique, il en résulte que la rotation optimale est plus élevée en information asymétrique qu'en situation de pleine information. Nous montrons également comment le seuil maximal de coût de coupe peut être endogénéisé, afin de permettre au propriétaire d'accroître son profit espéré en s'assurant que les forêts non profitables ne seront pas exploitées. Nous comparons ensuite la redevance optimale en information asymétrique et symétrique. Les redevances forestières dans un arrangement de gré à gré étant généralement, en pratique, une fonction linéaire du volume de bois, nous dérivons le contrat optimal en imposant une telle forme de redevance et nous caractérisons la perte en terme de profit espéré qui résulte de l'utilisation de ce type de contrat plutôt que du contrat non linéaire plus général. Finalement, toujours dans le contexte statique, nous montrons à travers un mécanisme optimal d'enchère au second prix qu'en introduisant ainsi la compétition entre les firmes le propriétaire forestier augmente son profit espéré. Les résultats obtenus dans le contexte dynamique diffèrent pour la plupart de ceux obtenus dans le cas statique. Nous montrons que le contrat optimal prévoit alors que chaque type de firme, incluant celle ayant le coût le plus élevé, obtient une rente strictement positive, laquelle augmente dans le temps. Ceci est nécessaire pour obtenir la révélation à moindre coût à la période courante du véritable type de la firme. Comme implication, la rotation optimale s'accroît aussi dans le temps. Finalement, nous montrons qu'il y a distorsion en asymétrique d'information par rapport à l'optimum de pleine information même pour le coût le plus bas (la réalisation la plus favorable). La concurrence introduite dans le premier essai sous forme d'enchère au second prix suppose que chaque firme connaît exactement son propre coût de coupe. Dans le deuxième essai nous relâchons cette hypothèse. En réalité, ni le propriétaire forestier ni les firmes ne connaissent avec précision les coûts de coupe. Chaque firme observe de manière privée un signal sur son coût. Par exemple chaque firme est autorisée à visiter un lot pour avoir une estimation (signal) de son coût de coupe. Cependant cette évaluation est approximative. Ainsi, le coût de chaque firme va dépendre des estimations (signaux) d'autres firmes participantes. Nous sommes en présence d'un mécanisme à valeurs interdépendantes. Dans ce contexte, la valeur d'une allocation dépend des signaux de toutes les firmes. Le mécanisme optimal (attribution des droits d'exploitation, redevance et âge de coupe) est exploré. Nous déterminons les conditions sous lesquelles le mécanisme optimal peut être implémenté par une enchère au second prix et dérivons la rotation optimale et le prix de réserve dans le contexte de ce type d'enchère. Le troisième essai de la thèse analyse l'impact à long terme du recyclage sur la surface de terre affectée à la forêt. L'un des principaux arguments qui milite en faveur du recours au recyclage est que cela entraînerait une réduction de la coupe de bois, épargnant ainsi des arbres. L'objectif est donc d'aboutir à un nombre d'arbres plus important qu'en l'absence de recyclage. L'idée d'accroître le stock d'arbre tient au fait que les forêts génèrent des externalités: elles créent un flux de services récréatifs, freinent l'érosion des sols et des rives des cours d'eau et absorbent du dioxyde de carbone présent dans l'atmosphère. Étant donné la présence d'externalités, l'équilibre des marchés résulterait en un nombre d'arbre insuffisant, justifiant donc la mise en oeuvre de politiques visant à l'accroître. Le but de ce troisième essai est de voir dans quelle mesure la promotion du recyclage est un instrument approprié pour atteindre un tel objectif. En d'autres mots, comment le recyclage affecte-t-il à long terme la surface de terre en forêt et l'âge de coupe? Nous étudions cette question en spécifiant un modèle dynamique d'allocation d'un terrain donné, par un propriétaire forestier privé, entre la forêt et une utilisation alternative du terrain, comme l'agriculture. Une fois les arbres coupés, il décide d'une nouvelle allocation du terrain. Il le fait indéfiniment comme dans le cadre du modèle de Faustmann. Le bois coupé est transformé en produit final qui est en partie recyclé comme substitut du bois original. Ainsi, les outputs passés affectent le prix courant. Nous montrons que, paradoxalement, un accroissement du taux de recyclage réduira à long terme la surface forestière et donc diminuera le nombre d'arbres plantés. Par contre l'âge de coupe optimal va s'accroître. L'effet net sur le volume de bois offert sur le marché est ambigu. Le principal message cependant est qu'à long terme le recyclage va résulter en une surface en forêt plus petite et non plus grande. Donc, si le but est d'accroître la surface en forêt, il pourrait être préférable de faire appel à d'autres types d'instruments de politique que celui d'encourager le recyclage.

The Complexity of Safety Stock Placement in General-Network Supply Chains

We consider the optimization problem of safety stock placement in a supply chain, as formulated in [1]. We prove that this problem is NP-Hard for supply chains modeled as general acyclic networks. Thus, we do not expect to find a polynomial-time algorithm for safety stock placement for a general-network supply chain.