Optimising the cutting of wood fibre plates in the hardboard industry

Hardboard companies transform eucalyptus trunks into rectangular wood fibre plates basically by means of processes of disintegration and reconstitution of wood fibres. Such plates called hardboards are then cut into ordered items (smaller rectangles) to satisfy customer demands. In this paper, we present approaches to generate cutting patterns that minimize the cost or waste of material, considering different particular constraints associated with longitudinal and transversal saws, head cuts, book rotation and item unloading stations of the cutting machine. The methods are based on dynamic programming recursive formulas combined with greedy constructive heuristics and the primal simplex algorithm. To illustrate the application of these approaches, a case study was carried out in a Brazilian hardboard company. The results show that the approaches are able to produce better solutions than the ones currently used by the company.     

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.     

Secondary log breakdown optimization with dynamic programming

Log breakdown can be viewed as a two-stage process with logs sawn into slabs of wood known as flitches during the primary stage and flitches further processed during the secondary stage to produce edged (cut lengthwise) and trimmed (cut widthwise) pieces. This paper addresses the secondary problem and describes some procedures for determining the optimal cutting of flitches into graded dimensional boards. The problem is formulated as a set packing problem with the objective being to maximise total value. Extensions to the basic formulation include constraints which restrict the number of saws and which disallow waste between adjacent edged pieces. The problem is solved using dynamic programming techniques and the algorithms incorporated into a sawing simulation system. Comparisons with existing edging and trimming procedures show that substantial reductions in solution time (to as little as 1/25th of the time required for an enumerative search) can be achieved.     

Modeling multistage cutting stock problems

In multistage cutting stock problems (CSP) the cutting process is distributed over several successive stages. Every stage except the last one produces intermediate products. The list of intermediate products may be given or arbitrary. The goal is to minimize the total amount of material taken out of stock to cut finished products sufficient to meet customer demands. If the intermediate sizes are given, the column generation technique can be applied to multistage cutting problems. If the intermediate sizes are not given then another dimension is added to the problem complexity. We propose a special procedure for this case that dynamically generates both rows (intermediate sizes) and columns (patterns). We refer to this method as row-and-column generation. The method uses an auxiliary problem embedded into the frame of the revised simplex algorithm. It is a non-linear knapsack problem that can be solved efficiently. In contrast to the column generation method the developed technique cannot guarantee the optimal solution. However, the results of computational experiments are very promising and prove that the method is a valuable addition to the set of tools for modeling and solving multistage CSPs.     

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.     

An algorithm for a cutting stock problem on a strip

A cutting stock problem is formulated as follows: a set of rectangular pieces must be cut from a set of sheets, so as to minimize total waste. In our problem the pieces are requested in large quantities and the set of sheets are long rolls of material. For this class of problems we have developed a fast heuristic based on partial enumeration of all feasible patterns. We then tested the effectiveness on a set of test problems ranging from practical to random instances. Finally, the algorithm has been applied to check the asymptotic behaviour of the solution when a continuous stream of pieces is requested and cutting decisions are to be made while orders are still arriving.     

Supply chain scheduling with receiving deadlines and non-linear penalty

We study the operations scheduling problem with delivery deadlines in a three-stage supply chain process consisting of (1) heterogeneous suppliers, (2) capacitated processing centres (PCs), and (3) a network of business customers. The suppliers make and ship semi-finished products to the PCs where products are finalized and packaged before they are shipped to customers. Each business customer has an order quantity to fulfil and a specified delivery date, and the customer network has a required service level so that if the total quantity delivered to the network falls below a given targeted fill rate, a non-linear penalty will apply. Since the PCs are capacitated and both shipping and production operations are non-instantaneous, not all the customer orders may be fulfilled on time. The optimization problem is therefore to select a subset of customers whose orders can be fulfilled on time and a subset of suppliers to ensure the supplies to minimize the total cost, which includes processing cost, shipping cost, cost of unfilled orders (if any), and a non-linear penalty if the target service level is not met. The general version of this problem is difficult because of its combinatorial nature. In this paper, we solve a special case of this problem when the number of PCs equals one, and develop a dynamic programming-based algorithm that identifies the optimal subset of customer orders to be fulfilled under each given utilization level of the PC capacity. We then construct a cost function of a recursive form, and prove that the resulting search algorithm always converges to the optimal solution within pseudo-polynomial time. Two numerical examples are presented to test the computational performance of the proposed algorithm.     

A tabu search algorithm for a two-dimensional non-guillotine cutting problem

In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.     

A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem

The two-dimensional orthogonal non-guillotine cutting problem (NGCP) appears in many industries (like wood and steel industries) and consists in cutting a rectangular master surface into a number of rectangular pieces, each with a given size and value. The pieces must be cut with their edges always parallel or orthogonal to the edges of the master surface (orthogonal cuts). The objective is to maximize the total value of the pieces cut.In this paper, we propose a two-level approach for solving the NGCP, where, at the first level, we select the subset of pieces to be packed into the master surface without specifying the layout, while at a second level we check only if a feasible packing layout exists. This approach has been already proposed by Fekete and Schepers [S.P. Fekete, J. Schepers, A new exact algorithm for general orthogonal d-dimensional knapsack problems, ESA 97, Springer Lecture Notes in Computer Science 1284 (1997) 144–156; S.P. Fekete, J. Schepers, On more-dimensional packing III: Exact algorithms, Tech. Rep. 97.290, Universität zu Köln, Germany, 2000; S.P. Fekete, J. Schepers, J.C. van der Veen, An exact algorithm for higher-dimensional orthogonal packing, Tech. Rep. Under revision on Operations Research, Braunschweig University of Technology, Germany, 2004] and Caprara and Monaci [A. Caprara, M. Monaci, On the two-dimensional knapsack problem, Operations Research Letters 32 (2004) 2–14]. We propose improved reduction tests for the NGCP and a cutting-plane approach to be used in the first level of the tree search to compute effective upper bounds.Computational tests on problems derived from the literature show the effectiveness of the proposed approach, that is able to reduce the number of nodes generated at the first level of the tree search and the number of times the existence of a feasible packing layout is tested.     

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.     

Simple block patterns for the two-dimensional cutting problem

This paper presents an algorithm for the unconstrained two-dimensional cutting problem of rectangular pieces. It proposes the simple block (SB) pattern consisting of simple blocks. The SB pattern is defined recursively. Each cut on the stock plate produces just one simple block. A horizontal cut produces a horizontal block with width equal to that of the leftmost piece in the block. A vertical cut produces a vertical block with length equal to that of the bottommost piece in the block. The algorithm generates the optimal SB pattern recursively, and selects optimally the first piece in each block. It uses upper bound to prune some unpromising branches during the searching process. The computational results indicate that the algorithm is highly efficient in improving material utilization, and the computation time is reasonable.     

A comparison of strategies to develop a customer default scoring model

Behavioural scoring models are generally used to estimate the probability that a customer of a financial institution who owns a credit product will default on this product in a fixed time horizon. However, one single customer usually purchases many credit products from an institution while behavioural scoring models generally treat each of these products independently. In order to make credit risk management easier and more efficient, it is interesting to develop customer default scoring models. These models estimate the probability that a customer of a certain financial institution will have credit issues with at least one product in a fixed time horizon. In this study, three strategies to develop customer default scoring models are described. One of the strategies is regularly utilized by financial institutions and the other two will be proposed herein. The performance of these strategies is compared by means of an actual data bank supplied by a financial institution and a Monte Carlo simulation study.     

A Practical Approach for Determining Rectangular Stock Sizes

In this paper we address the problem of determining what rectangular sizes should be stocked in order to satisfy a bill of materials composed of smaller rectangles. As is common in many manufacturing operations, the stock material will be cut using two-staged guillotine cutting patterns. We first generate a large number of stock sizes ideally suited to the bill of materials. Then we use a facility location algorithm to consolidate the stock sizes down to an acceptable number. Given the solution of what rectangular sizes to stock, a second program is used to map bills of materials into the stock rectangles. The effectiveness of our approach is demonstrated by generating stock sizes for a real-world bill of materials with 392 distinct order sizes and over 7700 order pieces.     

社会演进中钢未来使用规律预测及政策分析

运用国际上新兴的动态物质流分析方法,对2014~2100年中国钢使用规律进行预测。研究发现,2014年至21世纪30年代,中国人均钢存量迅速增长,并于2035年以后达到饱和。在联合国中等方差人口增长情景下,2014年以后中国钢总存量出现了先迅速上升、后逐步下降的态势。中国未来钢消费量将于2015年左右达到峰值。2035年以后,钢退役量将超过钢消费量,并于消费峰值出现的30年后达到最大值。根据上述钢未来使用规律,中国应根据消费峰值出现的时间和数量合理安排钢的生产量,并于消费峰值出现之前做好减产准备;提高退役钢的处理能力,加强循环技术研究,实现资源解耦;开拓国际钢铁市场,与初级工业化国家进行产业联合,释放过剩产能。     

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.     

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.     

Fuzzy chance-constrained programming model for a multi-echelon reverse logistics network for household appliances

Efficient planning and design of an appropriate reverse logistics network is crucial to the economical collection and disposal of scrapped household appliances and electrical products. Such systems are commonly modelled as mixed-integer programs, whose solutions will determine the location of individual facilities that optimize material flow. One of the major drawbacks of current models is that they do not adequately address the important issue of uncertainty in demand and supply. Another deficiency in current models is that they are restricted to a two-echelon system. This study addresses these deficiencies by embodying such uncertainties in the model using the technique of fuzzy-chance constrained programming, and by extending the model to a three-echelon system. A heuristic in the form of a hybrid genetic algorithm is then employed to generate low-cost solutions. The overall objective is to find economical solutions to the general problem of determining the volume of appliances to be moved between the three echelons of customer base to collection sites, collection sites to disposal centres and disposal centre to landfill centre/remanufacturing centre; and to the problems of positioning the disposal centres and the landfill centre/remanufacturing centres within the problem domain. A case example in China is presented and the quality and robustness of the solutions are explored through sensitivity analysis.     

Flexible job shop scheduling with overlapping in operations

In this paper, flexible job shop scheduling problem with a new approach, overlapping in operations, is discussed. In many flexible job shops, a customer demand can be released more than one for each job, where demand determines the quantity of each finished job ordered by a customer. In these models each job has a demand more than one. This assumption is an important and practical issue for many flexible job shops such as petrochemical industries. To consider this assumption, we use a new approach, named overlapping in operations. In this approach, embedded operations of each job can be performed due to overlap considerations in which each operation may be overlapped with the others because of its nature. The overlapping is limited by structural constraints, such as the dimensions of the box to be packed or the capacity of the container used to move the pieces from one machine to the next. Since this problem is well known as NP-Hard class, a hierarchical approach used simulated annealing algorithm is developed to solve large problem instances. Moreover, a mixed integer linear programming (MILP) method is presented. To evaluate the validity of the proposed SA algorithm, the results are compared with the optimal solution obtained with the traditional optimization technique (The Branch and Bound method). The computational results validate the efficiency and effectiveness of the proposed algorithm. Also the computational results show that the overlapping considering can improve the makespan and machines utilization measures. So the proposed algorithm can be applied easily in real factory conditions and for the large size problems and it should thus be useful to both practitioners and researchers.     

Inventory control by different service levels

This paper examines the multiple period inventory control problem of a single product with multiple (two) prices, depending on service level, in which optimal pricing and ordering decisions are made in each period. Traditional inventory and pricing models consider only single products, single prices, and single service levels. However, this research paper finds that a seller can improve inventory control and revenue by offering multiple prices depending on service level. This research considers a single product with multiple (two) pricing policies corresponding to service level as follows: if the customer is willing to delay the shipment, he/she will be offered a lower regular price. Otherwise, the customer will pay the regular price plus extra charges for express service. In this paper, I show the following: (1) there is an optimal pricing and replenishment policy that can control inventory and (2) there exists a finite threshold for inventory levels such that if the inventory level at the beginning of each period is higher than the threshold, the customer will be offered the express service at the regular price, without any extra charge.     

A queueing model for crowdsourcing

Crowdsourcing is getting popular after a number of industries such as food, consumer products, hotels, electronics, and other large retailers bought into this idea of serving customers. In this paper, we introduce a multi-server queueing model in the context of crowdsourcing. We assume that two types, say, Type 1 and Type 2, of customers arrive to a c-server queueing system. A Type 1 customer has to receive service by one of c servers while a Type 2 customer may be served by a Type 1 customer who is available to act as a server soon after getting a service or by one of c servers. We assume that a Type 1 customer will be available for serving a Type 2 customer (provided there is at least one Type 2 customer waiting in the queue at the time of the service completion of that Type 1 customer) with probability \(p, 0 \le p \le 1\). With probability \(q = 1 - p\), a Type 1 customer will opt out of serving a Type 2 customer provided there is at least one Type 2 customer waiting in the system. Upon completion of a service a free server will offer service to a Type 1 customer on an FCFS basis; however, if there are no Type 1 customers waiting in the system, the server will serve a Type 2 customer if there is one present in the queue. If a Type 1 customer decides to serve a Type 2 customer, for our analysis purposes that Type 2 customer will be removed from the system as Type 1 customer will leave the system with that Type 2 customer. Under the assumption of exponential services for both types of customers we study the model in steady state using matrix analytic methods and establish some results including explicit ones for the waiting time distributions. Some illustrative numerical examples are presented.