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

Two-Dimensional Bin Packing Problem with Guillotine Restrictions

This thesis, after presenting recent advances obtained for the two-dimensional bin packing problem, focuses on the case where guillotine restrictions are imposed. A mathematical characterization of non-guillotine patterns is provided and the relation between the solution value of the two-dimensional problem with guillotine restrictions and the two-dimensional problem unrestricted is being studied from a worst-case perspective. Finally it presents a new heuristic algorithm, for the two-dimensional problem with guillotine restrictions, based on partial enumeration, and computationally evaluates its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases.

History of the guillotine.

Mode of access: Internet.

The literary guillotine.

"... published November, 1903."

The literary guillotine. An authorized report of the proceedings before the Literary Emergency Court holden in and for the district of North America.

Mode of access: Internet.

Memoirs of M. Danton, late Minister of Justice to the National Convention, who suffered by the guillotine, Saturday, April 5, 1794 : to which are added, genuine anecdotes of M. Roberspierre [sic], late leader of the revolutionists in France, who was guillotined July 28, 1794.

Mode of access: Internet.

Operator, organizational and direct support maintenance manual, including repair parts and special tool lists : cutter, paper, guillotine (Challenger Machinery model 305 HB), FSN 3610-689-5705.

Includes index.

Josephine: desire, ambition, Napoleon

Biography of Josephine Bonaparte. The incredible rise and unbelievable fall of Josephine, a mistress, courtesan and Revolutionary heroine whose energy and ambition has often been overshadowed by Napoleon’s military might. Historian Kate Williams, author of Becoming Queen, tells Josephine’s searing story of sexual obsession, politics and surviving as a woman in a man’s world. Abandoned in Paris by her aristocratic husband, Josephine's future did not look promising. But while her friends and contemporaries were sent to the guillotine during the Terror that followed the Revolution, she survived prison and emerged as the doyenne of a wildly debauched party scene, surprising everybody when she encouraged the advances of a short, marginalised Corsican soldier, six years her junior. Josephine, the fabulous hostess and skilled diplomat, was the perfect consort to the ambitious but obnoxious Napoleon. With her by his side, he became the greatest man in Europe, the Supreme Emperor; and she amassed a jewellery box with more diamonds than Marie Antoinette’s. But as his fame grew, Napoleon became increasingly obsessed with his need for an heir and irritated with Josephine’s extravagant spending. The woman who had enchanted France became desperate and jealous. Until, a divorcee aged forty-seven, she was forced to watch from the sidelines as Napoleon and his young bride produced a child.

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.

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50 000 instances). It is also effective for solving the instances of problem set Cover III (almost 100 000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes. Journal of the Operational Research Society (2010) 61, 306-320. doi: 10.1057/jors.2008.141 Published online 4 February 2009

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Neurectomia digital em eqüinos: comparação das técnicas guilhotina e stripping

Compararam-se as dificuldades transcirúrgicas e as complicações pós-operatórias das técnicas guilhotina (TG) e stripping (TS) para a neurectomia digital em eqüinos. Sob anestesia com halotano, quatro éguas tiveram os nervos digitais de um dos membros torácicos e um dos pélvicos submetidos à TG, enquanto os nervos digitais dos membros colaterais foram submetidos à TS. Os tempos cirúrgicos médios de TG e TS foram semelhantes. O comprimento médio do fragmento do nervo removido foi três vezes maior em TS (P<0,001). Independente da técnica utilizada, houve perda total da sensibilidade nos talões de todos os membros dentro dos quatro primeiros meses da cirurgia. Após 14 meses, houve retorno da sensibilidade em 37% dos membros em TG e 18,8% em TS (P=0,06). Ao exame de palpação para identificação de neuromas dolorosos, houve episódios de sensibilidade discreta em um maior número de cotos nervosos proximais operados com TS, 53,6% contra 6,4% dos operados com TG (P=0,003). Ambas as técnicas foram satisfatórias por não apresentarem maiores complicações durante ou após a cirurgia. Considerou-se que TG apresentou menor potencial para produzir reinervação e neuromas dolorosos.

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)