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.

Evaluation of cutting patterns produced in primary teeth by an air-abrasion system

Objective: the aim of this in vitro study was to assess the effect of tip diameter, nozzle distance, and application time of an air-abrasion system for cavity preparation on the enamel of primary teeth. Method and materials: Forty exfoliated primary teeth were air abraded with a microabrasion machine used with a handpiece with an 80-degree-angle nozzle, 50-mum abrasive particle size, and 80-psi air pressure. The effects of 0.38- or 0.48-mm inner tip diameter, 2- or 5-mm distance from tip to tooth surface, and 15 or 30 seconds of application time on cutting efficiency were evaluated. Cutting width and depth were analyzed and measured from scanning electron micrographs. Results: Statistical analysis revealed that the width of the cuts was significantly greater when the tip distance was increased. Significantly deeper cavities were produced by a tip with a 0.48-mm inner diameter. The application time did not influence the cuts. Conclusion: the cutting patterns found in this study suggest that precise removal of enamel in primary teeth is best accomplished when a tip with a 0.38-mm inner diameter is used at a 2-mm distance.

Evaluation of cutting patterns produced with air-abrasion systems using different tip designs.

This study assessed cavity preparations produced with different air abrasion tip parameters. Twelve test groups of extracted teeth were prepared to evaluate the parameters of 80 degrees or 45 degrees nozzle angles and 0.38 or 0.48 mm inner tip diameters. All other factors were held constant. A device was made to hold the specimen and air abrasion handpiece that standardized the distance and position relative to the tooth and time of application. The cavities were evaluated by assessing the rounding of the cavosurface margins and cavity floor. Measurements of cavosurface angles and the angle of concavity were made at the deepest portion of the abraded surface using scanning electron micrographs. The cavosurface angles were compared using paired t-test, and the effects of the tip design parameters were analyzed by ANOVA and Duncan's Multiple Range test. From the cavity patterns found in this study, the authors suggest that 80 degrees angle tips are more appropriate than 45 degrees angle tips for making narrow, deep cuts for preventive resin restorations. Conversely, when shallow preparations are needed, as in the case of Class V cavity preparations, cutting patterns of 45 degrees angle tips are more suitable.

Generating unconstrained two-dimensional non-guillotine cutting patterns by a Recursive Partitioning Algorithm

In this study, a dynamic programming approach to deal with the unconstrained two-dimensional non-guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two-staged and non-staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of pro blem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method. Journal of the Operational Research Society (2012) 63, 183-200. doi: 10.1057/jors.2011.6 Published online 17 August 2011

Effect of handpiece tip design on the cutting efficiency of an air abrasion system

Purpose : the aim of this study was to evaluate the effect of nozzle angle and tip diameter on the cutting efficiency of an air abrasion system. Materials and Methods: Thirty-six extracted human third molars were air-abraded with the PrepStar microabrasion machine using a handpiece with either 80degrees or 45degrees nozzle angles with 0.38 or 0.48 nun tip orifice diameters. The following parameters were held constant: abrasive particle size (27 mum), air pressure (80 psi), distance (2 mm.) and duration (15 seconds). The cutting efficiency was compared using enamel, dentin and cementum substrates. Width and depth of the cutting patterns were analyzed and measured using scanning electron micrographs. Results: Statistical analysis using three-way ANOVA and Duncan's Multiple Range test revealed that the width of the cuts was significantly greater when the cavities were prepared using the 45degrees nozzle angle. Significantly deeper cavities were produced with the 80degrees nozzle angle. The tip orifice of the nozzle influenced the cutting efficiency in softer substrates, dentin and cementum. Precise removal of hard tissue is best accomplished using the 80degrees angle nozzle tips for all types of tooth surfaces, enamel, dentin and cementum.

The usable leftover one-dimensional cutting stock problem-a priority-in-use heuristic

We consider a one-dimensional cutting stock problem in which the material not used in the cutting patterns, if large enough, is kept for use in the future. Moreover, it is assumed that leftovers should not remain in stock for a long time, hence, such leftovers have priority-in-use compared to standard objects (objects bought by the industry) in stock. A heuristic procedure is proposed for this problem, and its performance is analyzed by solving randomly generated dynamic instances where successive problems are solved in a time horizon. For each period, new demands arise and a new problem is solved on the basis of the information about the stock of the previous periods (remaining standard objects in the stock) and usable leftovers generated during those previous periods. The computational experiments show that the solutions presented by the proposed heuristic are better than the solutions obtained by other heuristics from the literature. © 2012 The Authors. International Transactions in Operational Research © 2012 International Federation of Operational Research Societies.

Influence of air abrasion tips and operation modes on enamel-cutting characteristics

Objective: To assess the influence of air abrasion tips and system operation modes on enamel cutting. Methods: Forty bovine teeth were abraded with the air abrasion system Mach 4.1 for 10 and 15 seconds, employing conventional and sonic tips of 0.45-mm inner diameter and a 90° angle, and 27.5-μm aluminum oxide at 5.51 bar air pressure in continuous and pulsed modes. The width and depth of the resulting cuts were measured in SEM. Results: The multivariate analysis of variances revealed that, compared to the sonic tip, the conventional tip produced shallower cuts independent of the operation mode and the application period. Conclusions: The cutting patterns observed in this study suggest that the pulsed mode produced deeper cuts when both the conventional and sonic tips were used, and that the sonic tip cut more dental tissue than the conventional one.

A genetic algorithm for the one-dimensional cutting stock problem with setups

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Integrated cutting machine programming and lot sizing in furniture industry

In this paper a mathematical model that combines lot-sizing and cutting-stock problems applied to the furniture industry is presented. The model considers the usual decisions of the lot sizing problems, as well as operational decisions related to the cutting machine programming. Two sets of a priori generated cutting patterns are used, industry cutting patterns and a class of n-group cutting patterns. A strategy to improve the utilization of the cutting machine is also tested. An optimization package was used to solve the model and the computational results, using real data from a furniture factory, show that a small subset of n-group cutting patterns provides good results and that the cutting machine utilization can be improved by the proposed strategy.

Análise estrutural e dimensionamento de estruturas de membrana

Dissertação de mestrado integrado em Engenharia Civil

Calceology : an introduction to North Western European archaeological leather footwear (Neolithic period to c. AD 1600)

Calceology is the study of recovered archaeological leather footwear and is comprised of conservation, documentation and identification of leather shoe components and shoe styles. Recovered leather shoes are complex artefacts that present technical, stylistic and personal information about the culture and people that used them. The current method in calceological research for typology and chronology is by comparison with parallel examples, though its use poses problems by an absence of basic definitions and the lack of a taxonomic hierarchy. The research findings of the primary cutting patterns, used for making all leather footwear, are integrated with the named style method and the Goubitz notation, resulting in a combined methodology as a basis for typological organisation for recovered footwear and a chronology for named shoe styles. The history of calceological research is examined in chapter two and is accompanied by a review of methodological problems as seen in the literature. Through the examination of various documentation and research techniques used during the history of calceological studies, the reasons why a standard typology and methodology failed to develop are investigated. The variety and continual invention of a new research method for each publication of a recovered leather assemblage hindered the development of a single standard methodology. Chapter three covers the initial research with the database through which the primary cutting patterns were identified and the named styles were defined. The chronological span of each named style was established through iterative cross-site sedation and named style comparisons. The technical interpretation of the primary cutting patterns' consistent use is due to constraints imposed by the leather and the forms needed to cover the foot. Basic parts of the shoe patterns and the foot are defined, plus terms provided for identifying the key points for pattern making. Chapter four presents the seventeen primary cutting patterns and their sub-types, these are divided into three main groups: six integral soled patterns, four hybrid soled patterns and seven separately soled patterns. Descriptions of the letter codes, pattern layout, construction principle, closing seam placement and list of sub-types are included in the descriptions of each primary cutting pattern. The named shoe styles and their relative chronology are presented in chapter five. Nomenclature for the named styles is based on the find location of the first published example plus the primary cutting pattern code letter. The named styles are presented in chronological order from Prehistory through to the late 16th century. Short descriptions of the named styles are given and illustrated with examples of recovered archaeological leather footwear, reconstructions of archaeological shoes and iconographical sources. Chapter six presents documentation of recovered archaeological leather using the Goubitz notation, an inventory and description of style elements and fastening methods used for defining named shoe styles, technical information about sole/upper constructions and the consequences created by the use of lasts and sewing forms for style identification and fastening placement in relation to the instep point. The chapter concludes with further technical information about the implications for researchers about shoemaking, pattern making and reconstructive archaeology. The conclusion restates the original research question of why a group of primary cutting patterns appear to have been used consistently throughout the European archaeological record. The quantitative and qualitative results from the database show the use of these patterns but it is the properties of the leather that imposes the use of the primary cutting patterns. The combined methodology of primary pattern identification, named style and artefact registration provides a framework for calceological research.

A linear optimization approach to the combined production planning model

Two fundamental processes usually arise in the production planning of many industries. The first one consists of deciding how many final products of each type have to be produced in each period of a planning horizon, the well-known lot sizing problem. The other process consists of cutting raw materials in stock in order to produce smaller parts used in the assembly of final products, the well-studied cutting stock problem. In this paper the decision variables of these two problems are dependent of each other in order to obtain a global optimum solution. Setups that are typically present in lot sizing problems are relaxed together with integer frequencies of cutting patterns in the cutting problem. Therefore, a large scale linear optimizations problem arises, which is exactly solved by a column generated technique. It is worth noting that this new combined problem still takes the trade-off between storage costs (for final products and the parts) and trim losses (in the cutting process). We present some sets of computational tests, analyzed over three different scenarios. These results show that, by combining the problems and using an exact method, it is possible to obtain significant gains when compared to the usual industrial practice, which solve them in sequence. (C) 2010 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.

O problema de corte de estoque em indústrias de móveis de pequeno e médio portes

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

A linear optimization approach to the combined production planning model

Two fundamental processes usually arise in the production planning of many industries. The first one consists of deciding how many final products of each type have to be produced in each period of a planning horizon, the well-known lot sizing problem. The other process consists of cutting raw materials in stock in order to produce smaller parts used in the assembly of final products, the well-studied cutting stock problem. In this paper the decision variables of these two problems are dependent of each other in order to obtain a global optimum solution. Setups that are typically present in lot sizing problems are relaxed together with integer frequencies of cutting patterns in the cutting problem. Therefore, a large scale linear optimizations problem arises, which is exactly solved by a column generated technique. It is worth noting that this new combined problem still takes the trade-off between storage costs (for final products and the parts) and trim losses (in the cutting process). We present some sets of computational tests, analyzed over three different scenarios. These results show that, by combining the problems and using an exact method, it is possible to obtain significant gains when compared to the usual industrial practice, which solve them in sequence. (C) 2010 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.