A matching approach for replenishing rectangular stock sizes

Consider a replenishment problem in which several different rectangular sizes of material are stocked. Customers order rectangles of the material, but the rectangles ordered have a range on specified width as well as on specified length. To satisfy the customer requirements, the stock material can be cut once longitudinally in order to satisfy two customer requirements or not cut at all, that is, an entire stock piece of material is used to satisfy one customer requirement. If an exact match is impossible in the current planning period, the unused material must be returned to stock— an expensive and undesirable situation. In this paper, a nonbipartite weighted matching problem formulation will be given for determining the replenishment requirements of rectangular stock sizes. Then, a hybrid solution approach, capable of solving real applications (typically up to 3000 nodes) efficiently, will be discussed. This solution was implemented in September 1998 and has operated successfully since then.     

An algorithm for the two-dimensional assortment problem

In this paper we consider the two-dimensional assortment problem. This is the problem of choosing from a set of stock rectangles a subset which can be used for cutting into a number of smaller rectangular pieces. Constraints are imposed upon the number of such pieces which result from the cutting.A heuristic algorithm for the guillotine cutting version of the problem is developed based on a greedy procedure for generating two-dimensional cutting patterns, a linear program for choosing the cutting patterns to use and an interchange procedure to decide the best subset of stock rectangles to cut.Computational results are presented for a number of test problems which indicate that the algorithm developed produces good quality results both for assortment problems and for two-dimensional cutting problems.     

Balancing stocks, flexible recipe costs and high service level requirements in a batch process industry: A study of a small scale model

Process industries often obtain their raw materials from mining or agricultural industries. These raw materials usually have variations in quality which often lead to variations in the recipes used for manufacturing a product. Another reason for varying the recipe is to minimize production costs by using the cheapest materials that still lead to a satisfactory quality in the product. A third reason for using recipe flexibility is that it may occur that not all materials for the standard recipe are available. If variations in supply and demand are large, keeping sufficient safety stock to cope with these variations may incur prohibitive high costs. This means that the costs of keeping safety stock should be balanced with the costs of sometimes using more expensive recipes. The question now is for what situations and to what extent the use of recipe flexibility is justified. In this paper we study this question by means of a small scale model. For this simple situation we derive a decision procedure to balance safety stock costs and flexibility costs. This procedure is applied to a range of different situations, that are characterized by a set of parameter values, in order to determine for which situations recipe flexibility should be used.     

Approximate Stock Formulae for Use in Conjunction with the Assortment Problem

This paper considers the calculation of the total stocks which must be held in order to maintain a given service level when the assortment problem approach of dynamic programming is used to select the standard stock sizes. Approximate formulae are derived to calculate the safety and working stocks for any number of standard sizes, assuming that the value of the demand for each stock size is approximately equal. It is shown that even very large reductions in the number of stock lines do not produce correspondingly large reductions in stock levels.     

The Cutting Stock Problem in the Flat Glass Industry

The cutting stock problem occurs where large rectangles of some material require cutting into smaller rectangles, in the most appropriate way, to satisfy an order book. A linear programming approach to the problem has been suggested by P. C. Gilmore and R. E. Gomory. An application of this approach in the glass industry is described which is shown to be inadequate since it only satisfies a wastage criterion. In practice, multiple criteria must be satisfied and two alternative approaches using linear programming and heuristic scheduling are proposed.     

An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem

This paper addresses a real-life 1.5D cutting stock problem, which arises in a make-to-order plastic company. The problem is to choose a subset from the set of stock rectangles to be used for cutting into a number of smaller rectangular pieces so as to minimize total production cost and meet orders. The total production cost includes not only material wastage, as in traditional cutting stock problems, but also production time. A variety of factors are taken into account, like cutter knife changes, machine restrictions, due dates and other work in progress limitations. These restrictions make the combinatorial structure of the problem more complex. As a result, existing algorithms and mathematical models are no longer appropriate. Thus we developed a new 1.5D cutting stock model with multiple objectives and multi-constraints and solve this problem in an incomplete enumerative way. The computational results show that the solution procedure is easy to implement and works very well.     

The Effect of Payment Rules on Ordering and Stockholding in Purchasing

The payment conditions for the purchase of raw materials and components have received little attention in the literature on inventory control. A common practice is to require payment by some specific day of the month following the month of delivery rather than a fixed time period after delivery. Alternatively, for convenience, invoices for a particular supplier may always be dealt with on the same day of the month, regardless of the payment conditions. In such circumstances the classical square root E.O.Q. is not the ‘optimal’ size for purchase orders. Under the assumption of a roughly constant demand rate for the final products, as is assumed for lot sizing techniques in most statistical inventory control models, it is shown that orders should be specified as a number of integral months' demands. For those items whose annual purchase bill is over about £500 per year, the minimum cost purchase order should be one month's demand, to be delivered as early in the month as possible or in convenient sub-lots.This new model will not lead to large savings on the use of the E.O.Q. lot size. It is however claimed that this fits the practical situation better and avoids many of the nonsenses of the E.O.Q. of, for example, giving absurdly low order sizes for high priced items, and the need to place lower bounds on order sizes.     

Cutting circles and polygons from area-minimizing rectangles

A set of circles, rectangles, and convex polygons are to be cut from rectangular design plates to be produced, or from a set of stocked rectangles of known geometric dimensions. The objective is to minimize the area of the design rectangles. The design plates are subject to lower and upper bounds of their widths and lengths. The objects are free of any orientation restrictions. If all nested objects fit into one design or stocked plate the problem is formulated and solved as a nonconvex nonlinear programming problem. If the number of objects cannot be cut from a single plate, additional integer variables are needed to represent the allocation problem leading to a nonconvex mixed integer nonlinear optimization problem. This is the first time that circles and arbitrary convex polygons are treated simultaneously in this context. We present exact mathematical programming solutions to both the design and allocation problem. For small number of objects to be cut we compute globally optimal solutions. One key idea in the developed NLP and MINLP models is to use separating hyperplanes to ensure that rectangles and polygons do not overlap with each other or with the circles. Another important idea used when dealing with several resource rectangles is to develop a model formulation which connects the binary variables only to the variables representing the center of the circles or the vertices of the polytopes but not to the non-overlap or shape constraints. We support the solution process by symmetry breaking constraints. In addition we compute lower bounds, which are constructed by a relaxed model in which each polygon is replaced by the largest circle fitting into that polygon. We have successfully applied several solution techniques to solve this problem among them the Branch&Reduce Optimization Navigator (BARON) and the LindoGlobal solver called from GAMS, and, as described in Rebennack et al. [21], a column enumeration approach in which the columns represent the assignments. Good feasible solutions are computed within seconds or minutes usually during preprocessing. In most cases they turn out to be globally optimal. For up to 10 circles, we prove global optimality up to a gap of the order of 10^?8 in short time. Cases with a modest number of objects, for instance, 6 circles and 3 rectangles, are also solved in short time to global optimality. For test instances involving non-rectangular polygons it is difficult to obtain small gaps. In such cases we are content to obtain gaps of the order of 10%.     

Nonisomorphic complete sets of F-rectangles with prime power dimensions

A technique for constructing nonisomorphic complete sets of frequency rectangles with prime power dimensions is described. This procedure is used to establish a conservative general lower bound for the number of possible nonisomorphic complete sets of frequency rectangles of prime power order. Several cases are considered in detail which improve the lower bound for those orders. The technique can also be applied to the construction of inequivalent orthogonal arrays of strength 2.     

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem

The research addressing two-dimensional (2D) irregular shape packing has largely focused on the strip packing variant of the problem. However, it can be argued that this is a simplification. The materials from which pieces are required to be cut will ultimately have a fixed length either due to the physical dimensions of the material or through constraints on the cutting machinery. Hence, in order to cut all the pieces, multiple sheets may be required. From this scenario arises the 2D irregular shape cutting stock problem. In this paper, we will present implementations of cutting stock approaches adapted to handle irregular shapes, including two approaches based on column generation (CG) and a sequential heuristic procedure. In many applications, setup costs can be reduced if the same pattern layout is cut from multiple sheets; hence there is a trade-off between material waste and number of patterns. Therefore, we describe the formulation and implementation of an adaptation of the CG method to control the number of different patterns. CG is a common method for the cutting stock problem; however, when the pieces are irregular the sub-problem cannot be solved optimally. Hence we implement CG and solve the sub-problem using the beam search heuristic. Further, we introduce a version of CG for instances where the number of rows is less than the number of columns.     

A hybrid approach based on genetic algorithms to solve the problem of cutting structural beams in a metalwork company

This work presents a hybrid approach based on the use of genetic algorithms to solve efficiently the problem of cutting structural beams arising in a local metalwork company. The problem belongs to the class of one-dimensional multiple stock sizes cutting stock problem, namely 1-dimensional multiple stock sizes cutting stock problem. The proposed approach handles overproduction and underproduction of beams and embodies the reusability of remnants in the optimization process. Along with genetic algorithms, the approach incorporates other novel refinement algorithms that are based on different search and clustering strategies. Moreover, a new encoding with a variable number of genes is developed for cutting patterns in order to make possible the application of genetic operators. The approach is experimentally tested on a set of instances similar to those of the local metalwork company. In particular, comparative results show that the proposed approach substantially improves the performance of previous heuristics.     

A multi-objective programming approach to 1.5-dimensional assortment problem

In this paper we study a 1.5-dimensional cutting stock and assortment problem which includes determination of the number of different widths of roll stocks to be maintained as inventory and determination of how these roll stocks should be cut by choosing the optimal cutting pattern combinations. We propose a new multi-objective mixed integer linear programming (MILP) model in the form of simultaneously minimization two contradicting objectives related to the trim loss cost and the combined inventory cost in order to fulfill a given set of cutting orders. An equivalent nonlinear version and a particular case related to the situation when a producer is interested in choosing only a few number of types among all possible roll sizes, have also been considered. A new method called the conic scalarization is proposed for scalarizing non-convex multi-objective problems and several experimental tests are reported in order to demonstrate the validity of the developed modeling and solving approaches.     

Multi-job Cutting Stock Problem with Due Dates and Release Dates

The common feature of cutting stock problems is to cut some form of stock materials to produce smaller pieces of materials in quantities matching orders received. Most research on cutting stock problems focuses on either generating cutting patterns to minimize wastage or determining the required number of stock materials to meet orders. In this paper, we examine a variation of cutting stock problems that arises in some industries where meeting orders' due dates is more important than minimizing wastage of materials. We develop two two-dimensional cutting stock models with due date and release date constraints. Since adding due dates and release dates makes the traditional cutting stock problem even more difficult to solve, we develop both LP-based and non-LP-based heuristics to obtain good solutions. The computational results show that the solution procedures are easy to implement and work very well.     

Existence of magic 3‐dimensional rectangles

Since the complete solution for the existence of magic 2‐dimensional rectangles in 1881, much attention has been paid on the existence of magic l‐dimensional rectangles for . The existence problem for magic l‐dimensional rectangles with even sizes has been solved completely for all integers . However, very little is known for the existence of magic l‐dimensional rectangles () with odd sizes except for some families and a few sporadic examples. In this paper, we focus our attention on the existence of magic 3‐dimensional rectangles and prove that the necessary conditions for the existence of magic 3‐dimensional rectangles are also sufficient. Our construction method is mainly based on a new concept, symmetric zero‐sum subset partition, which plays a crucial role in the recursive constructions of magic 3‐rectangles similar to that of PBD in the PBD‐closure construction in combinatorial design theory.     

On the number of rectangulations of a planar point set

We investigate the number of different ways in which a rectangle containing a set of n noncorectilinear points can be partitioned into smaller rectangles by n (nonintersecting) segments, such that every point lies on a segment. We show that when the relative order of the points forms a separable permutation, the number of rectangulations is exactly the (n+1)st Baxter number. We also show that no matter what the order of the points is, the number of guillotine rectangulations is always the nth Schröder number, and the total number of rectangulations is O(n²⁰/n⁴).     

A goal-driven approach to the 2D bin packing and variable-sized bin packing problems

In this paper, we examine the two-dimensional variable-sized bin packing problem (2DVSBPP), where the task is to pack all given rectangles into bins of various sizes such that the total area of the used bins is minimized. We partition the search space of the 2DVSBPP into sets and impose an order on the sets, and then use a goal-driven approach to take advantage of the special structure of this partitioned solution space. Since the 2DVSBPP is a generalization of the two-dimensional bin packing problem (2DBPP), our approach can be adapted to the 2DBPP with minimal changes. Computational experiments on the standard benchmark data for both the 2DVSBPP and 2DBPP shows that our approach is more effective than existing approaches in literature.     

Fixed charge problems with identical fixed charges

The general problem considered by this paper is a special case of the fixed-charge problem. The further condition imposed is that all variables have the same associated fixed-charge. The problem is discussed in the context of a known commercial application, that being the cutting stock problem. The situation considered is that of cutting given numbers of small rectangles from large rectangular stock-plates. In many such situations major aims are to have low stock-plate usage and a low number of setups of the cutting equipment. These represent conflicting objectives capable of being combined by the use of fixed charges upon the setups but this paper presents an alternative approach incorporating direct manipulation of the number of setups involved in the solution. This approach is compared to a solution technique for the general fixed-charge problem.     

Resource augmentation in two-dimensional packing with orthogonal rotations

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90^° rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1+ε), for any positive ε. Additionally, we show near-optimal packing results for a number of related packing problems.