Cutting and Packing in Production and Distribution

Cutting and packing problems such as the cutting of sheet metal and the loading of contain­ ers or, in a more abstract sense, capital budgeting or assembly line balancing have been treated in scientific literature of various disciplines for about fifty years. Since the pioneer work of Kantorovich in 1939, which frrst appeared in the West in 1960, there has been a steadily growing number of contributions of increasing importance in this research area, particularly in the past decade. As of today more than 700 contributions exist even when applying a strict categorisation. Since comprehensive monographies and compiled studies are still lacking, it is very time consuming and thus expensive to search for a suitable solution procedure for concrete problems in the available literature. Thus, an apparently simpler way is often chosen, which is to develop ones own approach. For this reason there is not only the danger of unnecessary effort and scientific repetition, but it is reality. With the goal of improved research coordination an interdisciplinary Special Interest Group on Cutting and Packing (SICUP) was founded in 1988, which meets every two years (1988 Paris, 1990 Athens, 1992 San Francisco) and issues a semi-annual newsletter (SICUP­ Bulletin) with up-to-date information. This book is intended to assist in the coordination of research work in this area.

Inhalt

1 Introduction.- 1.1. Purpose of the Investigation.- 1.2. Methodology Used.- 1.3. Structure of the Book.- 2 Cutting and Packing Problems as Geometric-Combinatoric Problems.- 2.1. Basic Logical Structure.- 2.2. Phenomena of Cutting and Packing.- 2.2.1. Cutting and Packing in Spatial Dimensions.- 2.2.2. Cutting and Packing in Abstract Dimensions.- 2.2.3. Related Problems.- 2.3. Delimitation in Investigation.- 3 The Treatment of Cutting and Packing Problems in the Literature.- 3.1. Models as Idealized Images of Actual Phenomena.- 3.2. Sources on Cutting and Packing Problems.- 3.2.1. Differentiation According to Thematic Criteria.- 3.2.2. Differentiation According to Bibliographical Criteria.- 3.3. Delimitation of Investigated Literature.- 4 Systematic Catalogue of Properties for the Characterization of Cutting and Packing Problems.- 4.1. Basis for Characteristic Properties.- 4.2. Design of the Catalogue.- 4.3. Characteristics Based on the Logical Structure.- 4.3.1. Dimensionality.- 4.3.2. Type of Assignment.- 4.3.3. Characteristics of Large Objects and Small Items.- 4.3.4. Pattern Restrictions.- 4.3.5. Objectives.- 4.3.6. Status of Information and Variability of Data.- 4.3.7. Solution Methods.- 4.4. Reality-Based Characteristics.- 4.4.1. Kind of Objects and Items, and Branch of Industry.- 4.4.2. Planning Context.- 4.4.3. Software.- 4.5. Overview.- 5 Types of Cutting and Packing Problems in the Literature.- 5.1. Principles of Type Definition.- 5.2. Hierarchical Catalogue of Types.- 5.2.1. General Types.- 5.2.2. Special Types.- 5.2.3. Summarized Description of the Hierarchy of Types.- 5.3. Properties of the Derived Problem Types.- 6 Bin Packing Types (BP).- 6.1. One-dimensional Bin Packing Type (BP1).- 6.2. Two-dimensional Bin Packing Types (BP2).- 6.2.1. BP2-Type with a Heterogeneous Assortment of Large Objects.- 6.2.2. BP2-Type with a Homogeneous Assortment of Large Objects.- 6.3. Actual Bin Packing Problems.- 7 Cutting Stock Types (CS).- 7.1. One-dimensional Cutting Stock Types (CS1).- 7.1.1. CS1-Type with Continuous Quantity Measurement of Large Objects.- 7.1.2. CS1-Types with Discrete Quantity Measurement of Large Objects.- 7.1.2.1. Discrete CSl-Type with a Homogeneous Assortment of Large Objects.- 7.1.2.2. Discrete CSl-Type with a Heterogeneous Assortment of Large Objects.- 7.2. Two-dimensional Cutting Stock Types (CS2).- 7.2.1. CS2-Type with Non-rectangular Small Items.- 7.2.2. CS2-Types with Rectangular Small Items.- 7.2.2.1. Rectangular CS2-Types with Only One Large Object per Figure.- 7.2.2.2. Rectangular CS2-Types with Guillotine Patterns.- 7.2.2.3. Rectangular CS2-Type with Nested Patterns.- 7.3. Three-dimensional Cutting Stock Type (CS3).- 7.4. Actual Cutting Stock Problems.- 8 Knapsack Types (KS).- 8.1. One-dimensional Knapsack Type (KS1).- 8.2. Two-dimensional Knapsack Type (KS2).- 8.3. Three-dimensional Knapsack Type (KS3).- 8.4. Actual Knapsack Problems.- 9 Pallet Loading Types (PL).- 9.1. Two-dimensional Pallet Loading Type (PL2).- 9.2. Three-dimensional Pallet Loading Type (PL3).- 9.3. Actual Pallet Loading Problems.- 10 Conclusions.- I. A Bibliography of Further C&P-Problems.- A. Published Surveys.- B. Literary References not Closely Analysed.- C. Most Recent Sources.- II. Brief Description of the Characteristics.- III. LARS Data Base System.- List of Abbreviations for the Journals.- I. General Literature.- II. C&P-Literature.