Simplest optimal guillotine cutting patterns for strips of identical circles

The manufacturing industry often uses the cutting and stamping process to divide stock plates into circles. A guillotine machine cuts the plate into strips for stamping at the cutting stage, and then a stamping press punches out the circles from the strips at the stamping stage. The problem discussed is to cut a plate into strips of identical circles such that the number of circles is maximized. A dynamic programming algorithm is presented for generating the simplest optimal cutting patterns of the strips. The computational results indicate that the algorithm is much efficient in simplifying the cutting process.     

Heuristic for the cutting and purchasing decisions of multiple metal coils

This paper presents a heuristic algorithm for the rectangular two-dimensional cutting stock problem, where metal coils of multiple widths are divided into rectangular items with guillotine cuts. The cutting process contains two phases. Coils are cut into segments at the first phase and the segments into items at the second phase. A subset of three-staged patterns is considered in generating the cutting plan. The algorithm is used to accomplish the following tasks: (1) Generating cutting plans for the cutting process; (2) Selecting the coil widths to purchase; (3) Optimizing the segment lengths to order. Benchmark instances are used to demonstrate the effectiveness of the algorithm in improving material utilization, and examples are used to illustrate the decision methods for different tasks.     

Approximate and Exact Algorithms for Constrained (Un) Weighted Two-dimensional Two-staged Cutting Stock Problems

In this paper we propose two algorithms for solving both unweighted and weighted constrained two-dimensional two-staged cutting stock problems. The problem is called two-staged cutting problem because each produced (sub)optimal cutting pattern is realized by using two cut-phases. In the first cut-phase, the current stock rectangle is slit down its width (resp. length) into a set of vertical (resp. horizontal) strips and, in the second cut-phase, each of these strips is taken individually and chopped across its length (resp. width).First, we develop an approximate algorithm for the problem. The original problem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact algorithm tailored especially for the constrained two-staged cutting problem. The algorithm starts with an initial (feasible) lower bound computed by applying the proposed approximate algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approximate and exact approaches.     

Optimal wafer cutting in shuttle layout problems

A major cost in semiconductor manufacturing is the generation of photo masks which are used to produce the dies. When producing smaller series of chips it can be advantageous to build a shuttle mask (or multi-project wafer) to share the startup costs by placing different dies on the same mask. The shuttle layout problem is frequently solved in two phases: first, a floorplan of the shuttle is generated. Then, a cutting plan is found which minimizes the overall number of wafers needed to satisfy the demand of each die type. Since some die types require special production technologies, only compatible dies can be cut from a given wafer, and each cutting plan must respect various constraints on where the cuts may be placed. We present an exact algorithm for solving the minimum cutting plan problem, given a floorplan of the dies. The algorithm is based on delayed column generation, where the pricing problem becomes a maximum vertex-weighted clique problem in which each clique consists of cutting compatible dies. The resulting branch-and-price algorithm is able to solve realistic cutting problems to optimality in a couple of seconds.     

Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts

This paper presents an approach for solving a new real problem in cutting and packing. At its core is an innovative mixed integer programme model that places irregular pieces and defines guillotine cuts. The two-dimensional irregular shape bin packing problem with guillotine constraints arises in the glass cutting industry, for example, the cutting of glass for conservatories. Almost all cutting and packing problems that include guillotine cuts deal with rectangles only, where all cuts are orthogonal to the edges of the stock sheet and a maximum of two angles of rotation are permitted. The literature tackling packing problems with irregular shapes largely focuses on strip packing i.e. minimizing the length of a single fixed width stock sheet, and does not consider guillotine cuts. Hence, this problem combines the challenges of tackling the complexity of packing irregular pieces with free rotation, guaranteeing guillotine cuts that are not always orthogonal to the edges of the stock sheet, and allocating pieces to bins. To our knowledge only one other recent paper tackles this problem. We present a hybrid algorithm that is a constructive heuristic that determines the relative position of pieces in the bin and guillotine constraints via a mixed integer programme model. We investigate two approaches for allocating guillotine cuts at the same time as determining the placement of the piece, and a two phase approach that delays the allocation of cuts to provide flexibility in space usage. Finally we describe an improvement procedure that is applied to each bin before it is closed. This approach improves on the results of the only other publication on this problem, and gives competitive results for the classic rectangle bin packing problem with guillotine constraints.     

Approaches to real world two-dimensional cutting problems

We consider a real world generalization of the 2-Dimensional Guillotine Cutting Stock Problem arising in the wooden board cutting industry. A set of rectangular items has to be cut from rectangular stock boards, available in multiple formats. In addition to the classical objective of trim loss minimization, the problem also asks for the maximization of the cutting equipment productivity, which can be obtained by cutting identical boards in parallel. We present several heuristic algorithms for the problem, explicitly considering the optimization of both objectives. The proposed methods, including fast heuristic algorithms, Integer Linear Programming models and a truncated Branch and Price algorithm, have increasing complexity and require increasing computational effort. Extensive computational experiments on a set of realistic instances from the industry show that high productivity of the cutting equipment can be obtained with a minimal increase in the total area of used boards. The experiments also show that the proposed algorithms perform extremely well when compared with four commercial software tools available for the solution of the problem.     

Solving the two-stage cutting stock problem

This paper describes an important class of cutting stock problems not previously discussed in the literature. The problem is one of determining the patterns to be used in a two-stage cutting process with restrictions imposed on the locations of cuts in the first stage. A particularly difficult version of this problem from the plastic film industry is presented and solved.     

OPTIMAL DIMENSIONS OF VIRGIN STOCK IN CUTTING GLASS TO ORDER

Glass cutting is a two-dimensional version of the cutting-stock problem. It involves two questions. One concerns the best way to cut a pane from a given plate. A less obvious question concerns selection of the plate from which the pane is cut. This leads to the question of what stock to order, before we even think of cutting it. We show that this latter question is more critical to economic cutting than the refinement of cutting procedures. We also present a method for selecting optimal stock sizes.     

下料问题与运输问题联合优化建模

本文研究了考虑子材运输的标准一维下料问题。建立了由生产商负责运输时,标准一维下料与运输协调优化整数规划模型,最小化母材使用成本,子材库存成本及子材运输成本。采用拉格朗日松弛技术对有关约束进行松弛和模型分解,设计基于序列规则和FFD规则的混合启发式算法求解模型。该算法由两部分组成,分别用于求解标准一维下料子问题和卖方运输子问题。通过随机产生的1800个算例,验证模型合理性与算法的有效性。与基于列生成法的两阶段算法解进行比较,平均总成本降低了17.57%,表明集成算法优于两阶段算法。     

Constructing the Maximum Consensus Tree from Rooted Triples

We investigated the problem of constructing the maximum consensus tree from rooted triples. We showed the NP-hardness of the problem and developed exact and heuristic algorithms. The exact algorithm is based on the dynamic programming strategy and runs in O((m + n ²)3 ⁿ ) time and O(2 ⁿ ) space. The heuristic algorithms run in polynomial time and their performances are tested and shown by comparing with the optimal solutions. In the tests, the worst and average relative error ratios are 1.200 and 1.072 respectively. We also implemented the two heuristic algorithms proposed by Gasieniec et al. The experimental result shows that our heuristic algorithm is better than theirs in most of the tests.     

投资项目集合选择问题的非线性规划模型与解法研究

基于项目集合选择问题的定义,给出了项目集合选择问题求解的一般步骤。依据投资方案组合选择问题的非线性特性,构建了投资项目集合选择问题的非线性规划模型,在此模型的基础上提出了基于外点法求解此类问题的改进贪婪搜索算法。研究了采用surrogate松弛模型确定初始点和运用改进的贪婪算法搜索最优解的具体实现方法,给出了实现算法的具体步骤。     

A hybrid algorithm based on variable neighbourhood for the strip packing problem

This paper addresses the strip packing problem, which has a wide range of real-world applications. Our proposed algorithm is a hybrid metaheuristic that combines an improved heuristic algorithm with a variable neighbourhood search. Different neighbourhoods are constructed based on the concept of block patterns. The proposed algorithm has three interesting features. First, a least-waste strategy is used to improve the constructive heuristics. Second, a better sorting sequence is selected to generate an initial solution. Finally, different neighbourhoods are constructed based on block patterns. The computational results from a diverse set of problem instances show that the proposed algorithm performs better than algorithms reported in the literature for most of the problem sets compared.     

Energy-oriented bi-objective optimization for the tempered glass scheduling

This paper investigates a real life bi-objective hybrid flow shop scheduling problem in an energy-intensive manufacturing system, in which glass is produced successively in cutting, printing and tempering stages. The problem aims to simultaneously optimize makespan and the total electricity cost under a time-of-use electricity pricing policy. The glass production has to respect the following environments: (i) the cutting and printing operations are processed in parallel machine environments; (ii) the tempering operation is processed on a batch machine; (iii) machine eligibility and setup time have to be considered in the cutting and printing stages; (iv) the whole manufacturing system is under a time-of-use electricity pricing policy. For the problem, an integer programming model is firstly proposed and shown to be strongly NP-hard. Then a model-based heuristic is adopted and a bi-objective differential evolution algorithm (BODE) is devised based on problem features. Computational experiments on randomly generated instances demonstrated that the BODE outperforms the model-based heuristic in terms of computation time and solution quality. Moreover, with mild increase on computation burden, the BODE significantly outperforms the classic NSGA II in terms of solution quality.     

Dynamic Programming and Hill-Climbing Techniques for Constrained Two-Dimensional Cutting Stock Problems

In this paper we propose an algorithm for the constrained two-dimensional cutting stock problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. The TDC problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. The proposed algorithm is a hybrid approach in which a depth-first search using hill-climbing strategies and dynamic programming techniques are combined. The algorithm starts with an initial (feasible) lower bound computed by solving a series of single bounded knapsack problems. In order to enhance the first-level lower bound, we introduce an incremental procedure which is used within a top-down branch-and-bound procedure. We also propose some hill-climbing strategies in order to produce a good trade-off between the computational time and the solution quality. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approach. The obtained results are compared to the results published by Alvarez-Valdés et al. (2002).     

Simulated annealing procedure for scheduling competing tasks in flexible manufacturing

This paper presents a simulated annealing SA procedure heuristic for the problem of scheduling N tasks on a machine equipped with an automatic tool changer to minimize the makespan time. The problem is first formulated as a symmetric travelling salesman problem TSP . A local search heuristic procedure is developed, then embedded into SA algorithm to enhance its performance. The implemented SA heuristic has the following features: an exponential acceptance function with non-monotonic cooling schedule, heuristic pre-processing, and a neighbourhood of changing the sequence of a small number of tasks and named the k-interchange procedure. The algorithm is compared with an exact solution method on a set of practical-sized problems. The proposed algorithm performed very well in terms of solution quality and computation time.     

A Semidefinite Programming Approach to the Quadratic Knapsack Problem

In order to gain insight into the quality of semidefinite relaxations of constrained quadratic 0/1 programming problems we study the quadratic knapsack problem. We investigate several basic semidefinite relaxations of this problem and compare their strength in theory and in practice. Various possibilities to improve these basic relaxations by cutting planes are discussed. The cutting planes either arise from quadratic representations of linear inequalities or from linear inequalities in the quadratic model. In particular, a large family of combinatorial cuts is introduced for the linear formulation of the knapsack problem in quadratic space. Computational results on a small class of practical problems illustrate the quality of these relaxations and cutting planes.     

An upper bound on the minimal total cost of the transportation problem with varying demands and supplies

In general cases, to find the exact upper bound on the minimal total cost of the transportation problem with varying demands and supplies is an NP-hard problem. In literature, there are only two approaches with several shortcomings to solve the problem. In this paper, the problem is formulated as a bi-level programming model, and proven to be solvable in a polynomial time if the sum of the lower bounds for all the supplies is no less than the sum of the upper bounds for all the demands; and a heuristic algorithm named TPVDS-A based on genetic algorithm is developed as an efficient and robust solution method of the model. Computational experiments on benchmark and new randomly generated instances show that the TPVDS-A algorithm outperforms the two existing approaches.     

The Ordered Cutting Stock Problem

The one‐dimensional cutting stock problem (CSP) is a classic combinatorial optimization problem in which a number of parts of various lengths must be cut from an inventory of standard‐size material. The classic CSP ensures that the total demand for a given part size is met but ignores the fact that parts produced by a given cutting pattern may be destined for different jobs. As a result, applying the classic CSP in a dynamic production environment may result in many jobs being open (or partially complete) at any point in time—requiring significant material handling or sorting operations. This paper identifies and discusses a new type of one‐dimensional CSP, called the ordered CSP, which explicitly restricts to one the number of jobs in a production process that can be open, or in process, at any given point in time. Given the growing emphasis on mass customization in the manufacturing industry, this restriction can help lead to a reduction in both in‐process inventory levels and material handling activities. A formal mathematical formulation is provided for the new CSP model, and its applicability is discussed with respect to a production problem in the custom door and window manufacturing industry. A genetic algorithm (GA) solution approach is then presented, which incorporates a customized heuristic for reducing scrap levels. Several different production scenarios are considered, and computational results are provided that illustrate the ability of the GA‐based approach to significantly decrease the amount of scrap generated in the production process.     

Logic-based Benders decomposition for an inventory-location problem with service constraints

We study an integrated inventory-location problem with service requirements faced by an aerospace company in designing its service parts logistics network. Customer demand is Poisson distributed and the service levels are time-based leading to highly non-linear, stochastic service constraints and a nonlinear, mixed-integer optimization problem. Unlike previous work in the literature, which propose approximations for the nonlinear constraints, we present an exact solution methodology using logic-based Benders decomposition. We decompose the problem to separate the location decisions in the master problem from the inventory decisions in the subproblem. We propose a new family of valid cuts and prove that the algorithm is guaranteed to converge to optimality. This is the first attempt to solve this type of problem exactly. Then, we present a new restrict-and-decompose scheme to further decompose the Benders master problem by part. We test on industry instances as well as random instances. Using the exact algorithm and restrict-and-decompose scheme we are able to solve industry instances with up to 60 parts within reasonable time, while the maximum number of parts attempted in the literature is 5.     

An exact semidefinite programming approach for the max-mean dispersion problem

This paper proposes an exact algorithm for the Max-Mean dispersion problem (\(Max-Mean DP\)), an NP-Hard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural non-convex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. This relaxation can be tightened by means of a cutting plane algorithm which iteratively adds the most violated triangular inequalities. The proposed approach embeds the SDP relaxation and the cutting plane algorithm into a branch and bound framework to solve \(Max-Mean DP\) instances to optimality. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up to 100 elements, outperforming other alternative approaches.