[This is a live document so please send any corrections or additions to [email protected]]

Cutting and packing is a classical problem in Operational Research and has been actively researched for over sixty years. The first cutting and packing problem formulated as a combinatorial optimization problem is arguably the knapsack problem, which has been studied extensively dating back to early 1900s. Sweeney and Paternoster (1992) published a biography of cutting and packing problems and start their chronology in 1940 with a paper by Brooks et al (1940) who studied the dissection of rectangles into squares. The biography documents the evolution of the research area and is interesting not least for showing the increasing volume of papers addressing cutting and packing problems and applications as the year’s progress.

Another point of interest that can be observed from the bibliography is the evolution of problem naming. The trim problem was prevalent in early publications. The first appearance of the cutting stock problem is attributed to Gilmore and Gomory (1961), although I have found citations that attribute the name to Kantorovich and Zalgaller (1951). Loading problems appear in 1966, pallet patterns in 1971 and the introduction of packing in 1974 along with the term bin packing. Nesting (also known as the 2-dimensional strip packing problem with irregular shapes) was introduced in 1976 and this marks the start of considering non rectangular shapes, which gained the title irregular shapes in 1980. Packing irregular shapes spawned research into geometric methodologies for handling the complexity of arbitrary shapes, where the nofit polygon became a primary tool in the late 1990s. Circles (named discs) were introduced into the literature in 1983 and more recently there are papers packing spheres and ellipses. Throughout the chronology in Sweeney and Paternoster’s paper are a range of naming conventions for the types of problem (or as an alternative authors simply named the type of application i.e cutting paper), and while common names emerge it became apparent that the papers using the same problem name were not always solving the same problem.

Dyckhoff (1990) was the first to introduce a typology which integrates the separate research areas of cutting and packing. Based on that, Dyckhoff and Finke (1992) categorized the literature existing at that time. Further experiences in applying Dyckhoff’s typology in the following years led to substantial improvements of main parts by Wäscher et al. (2007) that provided some clear definition of the commonly used names and brought greater consistency. This has gained wide acceptance, and the papers of Dyckhoff (1990) as well as of Wäscher et al. (2007) belong to the set of the most highly cited papers in the European Journal of Operational Research.

A strong characteristic of cutting and packing problems is that the research direction has largely been motivated by taking inspiration, or directly solving, problems from industry. The literature describes a large range of problems that often include specific operational constraints and objectives. As we learn more about how to solve the problems, and have more computer power at our disposal, we can include more detailed aspects of the problem. For example, cutting paper jumbos began as a one dimensional cutting stock problem, but now we consider minimising the movement of knives between patterns and model the reuse of residuals. In the last decade we have also seen the extension of problems into connected activities, for example, container loading and vehicle routing or production scheduling and bin packing.

In terms of ESICUP, the forerunner to ESICUP was the special interest group in cutting and packing (SICUP) started by Dyckhoff and Wascher. The group grew by linking a few centres of research activity in cutting and packing in Europe. This included Martin-Luther-Universitat, Halle-Wittenberg,, Germany, University of Swansea, UK (where I became a member), then University of Porto, Portugal. The group hosted a vibrant steam in Euro conferences and hosted workshops to encourage and support Ph.D. When the leadership of the group was passed over to Jose Oliveira (Porto) in 2002 the group became a European Working group and has an annual workshop and streams in Euro and IFORS. While being linked to EURO, it remains open and welcoming to all researchers interested in cutting and packing throughout the world.

[last edit Oct 2018]

Brooks R.L., Smith C.A.B., Stone A.H., and Tutte W.T. (1940) The dissection of rectangles into squares. Duke Mathematical Journal. 7, 312-340.

Dyckhoff H. (1990) A typology of cutting and packing problems. European Journal of Operational Research 44, 145–159.

Dyckhoff H. and Finke U. (1992) Cutting and Packing in Production and Distribution: A Typology and Bibliography. Physica, Heidelberg.

Gilmore P.C and Gomory R.E. (1961) A linear programming approach to the cutting stock problem, Operations Research. 9, 849-859.

Kantorovich L. V. and Zalgaller V. A. . (1951). Calculation of Rational Cutting of Stock. Lenizdat, Leningrad.

Sweeney P.E. and Paternoster E.R. (1992). Cutting and Packing Problems: A Categorized Application-Orientated Research Bibliography, Journal of the Operational Research Society, 43 (7), 691-706.

Wäscher G., Haußner H., and Schumann H (2007) An improved typology of cutting and packing problems. European Journal of Operational Research. 183, 1109-1130.