A heuristic for the one-dimensional cutting stock problem with usable leftover

A heuristic algorithm for the one-dimensional cutting stock problem with usable leftover (residual length) is presented. The algorithm consists of two procedures. The first is a linear programming procedure that fulfills the major portion of the item demand. The second is a sequential heuristic procedure that fulfills the remaining portion of the item demand. The algorithm can balance the cost of the consumed bars, the profit from leftovers and the profit from shorter stocks reduction. The computational results show that the algorithm performs better than a recently published algorithm.     

Large gaps in one-dimensional cutting stock problems

Its linear relaxation is often solved instead of the one-dimensional cutting stock problem (1CSP). This causes a difference between the optimal objective function values of the original problem and its relaxation, called a gap. The size of this gap is considered in this paper with the aim to formulate principles for the construction of instances of the 1CSP with large gaps. These principles are complemented by examples for such instances.     

An integrated cutting stock and sequencing problem

In this paper an integrated problem formulated as an integer linear programming problem is presented to find an optimal solution to the cutting stock problem under particular pattern sequencing constraints. The solution uses a Lagrangian approach. The dual problem is solved using a modified subgradient method. A heuristic for the integrated problem is also presented. The computational results obtained from a set of unidimensional instances that use these procedures are reported.     

Solving binary cutting stock problems by column generation and branch-and-bound

We present an algorithm for the binary cutting stock problem that employs both column generation and branch-and-bound to obtain optimal integer solutions. We formulate a branching rule that can be incorporated into the subproblem to allow column generation at any node in the branch-and-bound tree. Implementation details and computational experience are discussed.This research was supported by NSF and AFOSR grant DDM-9115768     

Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns

Two-staged patterns are often used in manufacturing industries to divide stock plates into rectangular items. A heuristic algorithm is presented to solve the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns. It uses the column-generation method to solve the residual problems repeatedly, until the demands of all items are satisfied. Each pattern is generated using a procedure for the constrained single large object placement problem to guarantee the convergence of the algorithm. The computational results of benchmark and practical instances indicate the following: (1) the algorithm can solve most instances to optimality, with the gap to optimality being at most one plate for those solutions whose optimality is not proven and (2) for the instances tested, the algorithm is more efficient (on average) in reducing the number of plates used than a published algorithm and a commercial stock cutting software package.     

One-dimensional cutting stock optimization in consecutive time periods

The paper deals with the general one-dimensional cutting stock problem (G1D-CSP), where optimization is not limited to a single order. Stock cutting is treated as a permanent business process in a company in which consecutive order sets need to be fulfilled either for production needs or for its customers. Exact demand for future orders is not known in advance. The unutilized and partly utilized stock lengths left after fulfilling current order sets are stored and used later. The goal is the reduction of trim loss and costs over a broader time-span. A new approach is suggested where previously developed method for G1D-CSP is modified. Several practical examples of the cutting process for several consecutive order sets are presented. An extension to a currently used typology for cutting stock problems is proposed.     

The cutting stock problem for large sections in the iron and steel industries

The characteristics of a cutting stock problem for large sections in the iron and steel industries are as follows:(1) There is a variety of criterions such as maximizing yield and increasing effeciency of production lines. (2) A cutting stock problem is accompanied by an optimal stock selection problem. A two-phase algorithm is developed, using an heuristic method. This algorithm gives nearly optimal solutions in real time. It is applied to both batch-solving and on-line solving of one-dimensional cutting of large section. The new algorithm has played an important role in a large-section production system to increase the yield by approximately 2.5%.     

New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem

The two-dimensional orthogonal non-guillotine cutting stockproblem (NGCP) appears in many industries (e.g. the wood andsteel industries) and consists of cutting a rectangular mastersurface into a number of rectangular pieces, each with a givensize and value. The pieces must be cut with their edges alwaysparallel to the edges of the master surface (orthogonal cuts).The objective is to maximize the total value of the pieces cut. New upper bounds on the optimal solution to the NGCP are described.The new bounding procedures are obtained by different relaxationsof a new mathematical formulation of the NGCP. Various proceduresfor strengthening the resulting upper bounds and reducing thesize of the original problem are discussed. The proposed newupper bounds have been experimentally evaluated on test problemsderived from the literature. Comparisons with previous boundingprocedures from the literature are given. The computationalresults indicate that these bounds are significantly betterthan the bounds proposed in the literature.     

The two-dimensional cutting stock problem revisited

In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k=2 stages cannot guarantee any bounded asymptotic performance ratio. k=3 stages lead to asymptotic performance ratios arbitrarily close to 1.69103; this bound is tight. Finally, k=4 stages yield asymptotic performance ratios arbitrarily close to 1.Steve Seiden died in a tragic accident on June 11, 2002. This paper resulted from a number of email discussions between the authors in spring 2002.     

Random search in the one-dimensional cutting stock problem

The paper reports on a randomized approach to the one-dimensional cutting stock problem. In a sequential heuristic the next pattern to be processed is chosen according to the best outcome of 200 trials of random bin packing. The quality of the solutions is discussed and the problem of multiple occurrence of equivalent solutions with different patterns is explained by the cross over technique known from genetic algorithms. For one data instance with 27 demand lengths, reported by Haessler (1975), four different optimal solutions are given.     

A two-objective mathematical model without cutting patterns for one-dimensional assortment problems

This paper considers a one-dimensional cutting stock and assortment problem. One of the main difficulties in formulating and solving these kinds of problems is the use of the set of cutting patterns as a parameter set in the mathematical model. Since the total number of cutting patterns to be generated may be very huge, both the generation and the use of such a set lead to computational difficulties in solution process. The purpose of this paper is therefore to develop a mathematical model without the use of cutting patterns as model parameters. We propose a new, two-objective linear integer programming model in the form of simultaneous minimization of two contradicting objectives related to the total trim loss amount and the total number of different lengths of stock rolls to be maintained as inventory, in order to fulfill a given set of cutting orders. The model does not require pre-specification of cutting patterns. We suggest a special heuristic algorithm for solving the presented model. The superiority of both the mathematical model and the solution approach is demonstrated on test problems.     

Dynamic job assignment: A column generation approach with an application to surgery allocation

We consider the assignment of jobs to heterogeneous agents in a dynamic system with a rolling time horizon. An example is a hospital operating theatre where the jobs are surgeries and the agents are the surgeons. The paper is presented in the context of surgery allocation and the system is characterized as follows: Patients are grouped into categories and they arrive continually following a stochastic process. Patients in each group have specific time limits within which they need treatment and if it cannot be accommodated then the patients are outsourced. The service level is the percentage of patients in each group treated within the time limit. Surgery durations are stochastic and depend on the surgeon conducting the surgeries. Each surgeon has limited time available and expected overtime is penalized by a non-decreasing convex function. We develop a column generation approach for the assignment of already arrived patients and tentative future patients to surgeons on specific days. It balances the conflicting objectives of including as many arrived patients as possible within their time limits, maximizing the service level of future patients, and minimizing the expected overtime of surgeons. A computational study is conducted with the model embedded in a rolling time horizon frame. The study indicates that the assignment of patients based on our model increases system performance in terms of service level and reduced overtime compared to a First-Come-First-Served (FCFS) policy when the arrival rates of patients are medium to high compared to the capacity of the system.     

Alternative configurations for cutting machines in a tube cutting mill

In a steel tube mill where an endless stream of steel tube is supplied from a manufacturing facility, trim waste is never made regardless of cutting patterns used and the standard cutting stock problem seems meaningless. Therefore, the continuous stock cutting problem with setup is introduced to minimize the sum of cutting time and pattern changing time to meet the given demand. We propose a new configuration of cutting machines to achieve higher production efficiency, namely the open-ended configuration as opposed to the traditional closed-ended configuration, thereby two variants of the problem are defined. We propose linear formulations for both problems using binary expansion of the number of pieces of different types in a pattern. Furthermore, we define the time for pattern change as a linear function of the number of knives used in the pattern to be more realistic. Computational studies suggest that the open-ended cutting machine may improve the production time by up to 44% and that our linear formulations are more efficient than the existing ones.     

A column generation approach for solving the patient admission scheduling problem

This paper addresses the Patient Admission Scheduling (PAS) problem. The PAS problem entails assigning elective patients to beds, while satisfying a number of hard constraints and as many soft constraints as is possible, and arises at all planning levels for hospital management. There exist a few, different variants of this problem. In this paper we consider one such variant and propose an optimization-based heuristic building on branch-and-bound, column generation, and dynamic constraint aggregation to solve it. We achieve tighter lower bounds than previously reported in the literature and, in addition, we are able to produce new best known solutions for five out of twelve instances from a publicly available repository.     

T-shape homogenous block patterns for the two-dimensional cutting problem

This paper presents an algorithm for unconstrained T-shape homogenous block cutting patterns of rectangular pieces. A vertical cut divides the stock sheet into two segments. Each segment consists of sections that have the same length and direction. A section contains a row of homogenous blocks. A homogenous block consists of homogenous strips of the same piece type. Each cut on the block produces just one strip. The directions of two strips cut successively from a block are either parallel or orthogonal. The algorithm uses a dynamic programming recursion to generate optimal blocks, solves knapsack problems to obtain the block layouts on the sections and the section layout on segments of various lengths, and optimally selects two segments to compose the cutting pattern. The computational results indicate that the algorithm is efficient in improving material usage, and the computation time is reasonable.     

A branch-and-price approach to the feeder network design problem

In this paper we consider the problem of designing a container liner shipping feeder network. The designer has to choose which port to serve during many rotations that start and end at a central hub. Many operational characteristics are considered, such as variable leg-by-leg speeds and cargo transit times. Realistic instances are generated from the LinerLib benchmark suite. The problem is solved with a branch-and-price algorithm, which can solve most instances to optimality within one hour. The results also provide insights on the cost structure and desirable features of optimal routes. These insights were obtained by means of an analysis where scenarios are generated varying internal and external conditions, such as fuel costs and port demands.     

A comparative numerical analysis for the guillotine two-dimensional cutting problem

In this work, the behavior of four algorithms in the resolution of the two-dimensional constrained guillotine cutting problem is analyzed. This problem is concerned about the way a set of pieces should be cut from a plate of greater dimensions, considering guillotine cutting and a constrained number of times a piece can be cut from the plate. In this study three combinatorial and two heuristic methods are considered. In the combinatorial methods from the set of pieces, a minimum loss layout is constructively generated based on Wang's algorithm. In addition, an evolutionary and an annealing type approach are considered. All of these models have been implemented on a high performance Silicon Graphics machine. Performance of each algorithm is analyzed both in terms of percentage waste and running time. In order to do that, a set of 1000 instances are classified according to their combinatorial degree and subsequently evaluated. This revised version was published online in June 2006 with corrections to the Cover Date.     

An application of simulated annealing to the cutting stock problem

We solve a two-dimensional cutting stock problem by applying a general global optimization algorithm, the simulated annealing. Our algorithms applied to the cutting problems involving both the guillotine and non-guillotine constraints, underlying that the latter is to be preferred for a big number of items. Several tests prove the validity of the algorithms.     

A branch-and-price approach for integrating nurse and surgery scheduling

A common problem at hospitals is the extreme variation in daily (even hourly) workload pressure for nurses. The operating room is considered to be the main engine and hence the main generator of variance in the hospital. The purpose of this paper is threefold. First of all, we present a concrete model that integrates both the nurse and the operating room scheduling process. Second, we show how the column generation technique approach, one of the most employed exact methods for solving nurse scheduling problems, can easily cope with this model extension. Third, by means of a large number of computational experiments we provide an idea of the cost saving opportunities and required solution times.     

A simulated annealing approach to the nesting problem in the textile manufacturing industry

The nesting problem in the textile industry is the problem of placing a set of irregularly shaped pieces (calledstencils) on a rectangularsurface, such that no stencils overlap and that thetrim loss produced when cutting out the stencils is minimized. Certain constraints may put restrictions on the positions and orientation of some stencils in the layout but, in general, the problem is unconstrained. In this paper, an algorithmic approach using simulated annealing is presented covering a wide variety of constraints which may occur in the industrial manufacturing process. The algorithm has high performance, is quite simple to use, is extensible with respect to the set of constraints to be met, and is easy to implement.The work of this author was supported in part by grant Le 491/3-1 from the German Research Association (DFG).