A heuristic,dynamic programming-based approach for a two-dimensional cutting problem with defects

This paper deals with a two-dimensional cutting problem in which small rectangular items of given types are to be cut from a rectangular large object which contains several defects. It is assumed that the number of pieces of each small item type which can be cut from the large object is not limited. In addition, all cuts are restricted to be of the guillotine-type and the number of stages necessary to perform all cuts is not limited. Furthermore, no small item must overlap with a defective region. The objective is to maximize the value of the cut small items. For the solution of the above-described problem, a heuristic, dynamic programming-based approach is presented which overcomes the structural and computational limitations of previously-proposed methods. In the presence of defects, the representation of the defective regions and the definition of discretization sets are revisited. This allows for an improvement of the computational efficiency as well as of the storage space requirements for solving the given problem with any number of defects in this approach. We further analyze the computational complexity of the algorithm and identify the factors which affect its running time. The proposed method is evaluated by means of a series of detailed numerical experiments which are performed on problem instances extracted from the literature, as well as on randomly generated instances. The experiments do not only illustrate how the suggested method is able to identify optimal solutions of the test problem instances, but they also explain why already existing methods fail to do so. Furthermore, the computational results indicate that the proposed method, equipped with the newly-proposed discretization sets, is capable of efficiently generating a high percentage of optimal solutions to the corresponding problem with defects.     

Dynamic programming and mixed integer programming based algorithms for the online glass cutting problem with defects and production targets

In flat glass manufacturing, glass products of various dimensions are cut from a glass ribbon that runs continuously on a conveyor belt. Placement of glass products on the glass ribbon is restricted by the defects of varying severity located on the ribbon as well as the quality grades of the products to be cut. In addition to cutting products, a common practice is to remove defective parts of the glass ribbon as scrap glass. As the glass ribbon moves continuously, cutting decisions need to be made within seconds, which makes this online problem very challenging. A simplifying assumption is to limit scrap cuts to those made immediately behind a defect (a cut-behind-fault or CBF). We propose an online algorithm for the glass cutting problem that solves a series of static cutting problems over a rolling horizon. We solve the static problem using two methods: a dynamic programming algorithm (DP) that utilises the CBF assumption and a mixed integer programming (MIP) formulation with no CBF restriction. While both methods improve the process yield substantially, the results indicate that MIP significantly outperforms DP, which suggests that the computational benefit of the CBF assumption comes at a cost of inferior solution quality.     

Sequence based heuristics for two-dimensional bin packing problems

This article addresses several variants of the two-dimensional bin packing problem. In the most basic version of the problem it is intended to pack a given number of rectangular items with given sizes in rectangular bins in such a way that the number of bins used is minimized. Different heuristic approaches (greedy, local search, and variable neighbourhood descent) are proposed for solving four guillotine two-dimensional bin packing problems. The heuristics are based on the definition of a packing sequence for items and in a set of criteria for packing one item in a current partial solution. Several extensions are introduced to deal with issues pointed out by two furniture companies. Extensive computational results on instances from the literature and from the two furniture companies are reported and compared with optimal solutions, solutions from other five (meta)heuristics and, for a small set of instances, with the ones used in the companies.     

Heuristic for two-dimensional homogeneous two-segment cutting patterns

This article deals with the guillotine-constrained two-dimensional cutting problem, where a guillotine is used to cut the stock plate into rectangular pieces, such that the pattern value (the total value of the pieces produced) is maximized, observing the constraint that the frequency of each piece type should not exceed the demand. Homogeneous two-segment (HTS) cutting patterns are considered to simplify the cutting process. Each HTS pattern includes two segments, each segment contains homogeneous strips of the same direction, and each homogeneous strip contains pieces of the same type. A heuristic is presented for generating HTS patterns. It is based on dynamic programming and branch-and-bound techniques. The computational results indicate that the heuristic is able to generate solutions close to optimal, and is adequate for solving large-scale instances.     

满足“一刀切”要求的木工板排样优化研究

 针对木工板手工排样效率低和材料利用率低问题,提出木工板“一刀切”排样优化算法．在剩余矩形填充算法中添加启发式分块原则,改进的剩余矩形填充算法满足“一刀切”工艺要求．采用遗传算法对矩形件进行排样优化,以提高木工板利用率,降低企业生产成本．为提高算法的优化精度,使用基于指数变换的非线性动态适应度函数,引入精英保护策略,应用部分填充交叉（partially matched crossover）算子．结合剩余矩形填充“一刀切”算法对遗传种群进行解码计算原料利用率,并作为适应度函数值,进行迭代搜索最优解．排样实例表明木工板“一刀切”排样优化算法能够很好地解决多品种大规模木工板排样问题．     

A recursive algorithm for the rectangular guillotine strip packing problem

This article presents a recursive heuristic algorithm to generate cutting patterns for the rectangular guillotine strip packing problem in which a set of rectangular items must be cut from the strip such that the consumed strip length is minimized. The strip is placed with its length along the horizontal direction, and is divided into several segments with vertical cuts. The length of a segment is determined by the item placed at the bottom. Orthogonal cuts divide the segments into blocks and finished items. For the current block considered, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with an orthogonal cut. Rotation of the items by 90 is allowed. Both lower and upper bounds are used to prune unpromising branches. The computational results indicate that the algorithm performs better than several recently published algorithms.     

An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts

Puzzle-based storage systems consist of densely stored unit loads on a square grid. The problem addressed in this paper is to retrieve a stored unit load from a puzzle-based storage using the minimum number of item moves. While previous research contributed optimal algorithms for only up to two empty locations (escorts), our approach solves configurations where multiple empty locations are arbitrarily positioned in the grid. The problem is formulated as a state space problem and solved to optimality using an exact search algorithm. To reduce the search space, we derive bounds on the number of eligible empty locations and develop several search-guiding estimate functions. Furthermore, we present a heuristic variant of the search algorithm to solve larger problem instances. We evaluate both solution algorithms on a large set of problem instances. Our computational results show that the algorithms clearly outperform existing approaches where they are applicate and solve more general configurations, which could not be solved to optimality before. The heuristic variant efficiently yields high-quality solutions for significantly larger instances of practically relevant size.     

Exact and approximate algorithms for part-machine clustering based on a relationship between interval graphs and Robinson matrices

An important manufacturing cell formation problem requires permutations of the rows (parts) and columns (machines) of a part-machine incidence matrix such that the reordered matrix exhibits a block-diagonal form. Numerous objective criteria and algorithms have been proposed for this problem. In this paper, a new perspective is offered that is based on the relationship between the consecutive ones property associated with interval graphs and Robinson structure within symmetric matrices. This perspective enables the cell formation problem to be decomposed into two permutation subproblems (one for rows and one for columns) that can be solved optimally using dynamic programming or a branch-and-bound algorithm for matrices of nontrivial size. A simulated annealing heuristic is offered for larger problem instances. Results pertaining to the application of the proposed methods for a number of problems from the literature are presented.     

Single machine multi-product capacitated lot sizing with sequence-dependent setups

In production planning in the glass container industry, machine-dependent setup times and costs are incurred for switch overs from one product to another. The resulting multi-item capacitated lot-sizing problem has sequence-dependent setup times and costs. We present two novel linear mixed-integer programming formulations for this problem, incorporating all the necessary features of setup carryovers. The compact formulation has polynomially many constraints, whereas the stronger formulation uses an exponential number of constraints that can be separated in polynomial time. We also present a five-step heuristic that is effective both in finding a feasible solution (even for tightly capacitated instances) and in producing good solutions to these problems. We report computational experiments.     

A note on linear models for two-group and three-group two-dimensional guillotine cutting problems

Due to the particular characteristics of certain cutting machines, special classes of cutting patterns, such as 1-group, 2-group and 3-group, requiring shorter processing times appear in the furniture, hardboard and stone industries. In this study we present integer linear models to generate 2-group and 3-group constrained and unconstrained two-dimensional guillotine cutting patterns. The models are derived from the linear models for 1-group guillotine cutting patterns proposed in Yanasse, H.H. and Morabito, R., Linear models for one-group two-dimensional guillotine cutting problems. International Journal of Production Research, in press. The performances of the models were evaluated by solving a number of examples randomly generated and an actual example derived from a furniture company. These results were produced using GAMS modelling language and the CPLEX solver, and they show that the models are effective to solve problems of small and moderate size.     

Linear models for 1-group two-dimensional guillotine cutting problems

In this study we present integer linear and non-linear models to generate 1-group constrained and unconstrained two-dimensional guillotine cutting patterns, including exact and non-exact cases. These patterns appear in different cutting processes as, for example, in the furniture industry. The models are useful for research and development of more effective solution methods, exploring particular structures, model decomposition, model relaxations, etc. They are also helpful for the performance evaluation of heuristic methods, since they allow (at least for problems of moderate size) an estimation of the optimality gap of heuristic solutions. To demonstrate the effectiveness of the proposed models, we compare them with models of the literature by solving a number of examples randomly generated and an actual example derived from a furniture company. Such results were produced using a well-known commercial software (the modelling language GAMS and the solver CPLEX) and they show that the computational efforts required to solve the models can be very different.     

Optimizing the cutting of stock plates in a furniture company

In this study we analysed practical aspects of the application of a cutting stock model to a Brazilian company that manufactures furniture on a large scale with a high degree of standardization. The model is based on the classical approach of Gilmore and Gomory (1965, Operations Research, 14, 94-120), which combines a linear program and a column generation procedure. Besides the two-stage and three-stage guillotine cutting patterns, we also considered one-group guillotine patterns that improve the productivity of the cutting equipment. Examples derived from the furniture company are used to illustrate some of the trade-offs involved, in particular the trade-off between cutting simpler patterns and patterns that yield less waste material, but reduce the productivity of the cutting machine.     

A dynamic programming-based heuristic for the variable sized two-dimensional bin packing problem

This paper addresses a variable sized two-dimensional bin packing problem. We propose two heuristics, H1 and H2, stemming from the dynamic programming idea by aggregating states to avoid the explosion in the number of states. These algorithms are elaborated for different purposes: H1 builds a general packing plan for items, while H2 can provide solutions by considering a variety of customer demands, such as guillotine cutting style and rotation of items. The performance of both algorithms is evaluated based on randomly generated instances reported in the literature by comparing them with the lower bounds and optimal solutions for identical bins. Computational results show that the average gaps are 8.97% and 13.41%, respectively, for H1 and H2 compared with lower bounds, and 5.26% and 6.26% compared with optimal solutions for identical bins. We also found that we can save 6.67% of space, on average, by considering variable sized bins instead of a bin packing problem with identical bins.     

A hybrid heuristic for the multiple choice multidimensional knapsack problem

In this article, a new solution approach for the multiple choice multidimensional knapsack problem is described. The problem is a variant of the multidimensional knapsack problem where items are divided into classes, and exactly one item per class has to be chosen. Both problems are NP-hard. However, the multiple choice multidimensional knapsack problem appears to be more difficult to solve in part because of its choice constraints. Many real applications lead to very large scale multiple choice multidimensional knapsack problems that can hardly be addressed using exact algorithms. A new hybrid heuristic is proposed that embeds several new procedures for this problem. The approach is based on the resolution of linear programming relaxations of the problem and reduced problems that are obtained by fixing some variables of the problem. The solutions of these problems are used to update the global lower and upper bounds for the optimal solution value. A new strategy for defining the reduced problems is explored, together with a new family of cuts and a reformulation procedure that is used at each iteration to improve the performance of the heuristic. An extensive set of computational experiments is reported for benchmark instances from the literature and for a large set of hard instances generated randomly. The results show that the approach outperforms other state-of-the-art methods described so far, providing the best known solution for a significant number of benchmark instances.     

Pattern-set generation algorithm for the one-dimensional multiple stock sizes cutting stock problem

A pattern-set generation algorithm (PSG) for the one-dimensional multiple stock sizes cutting stock problem (1DMSSCSP) is presented. The solution process contains two stages. In the first stage, the PSG solves the residual problems repeatedly to generate the patterns in the pattern set, where each residual problem is solved by the column-generation approach, and each pattern is generated by solving a single large object placement problem. In the second stage, the integer linear programming model of the 1DMSSCSP is solved using a commercial solver, where only the patterns in the pattern set are considered. The computational results of benchmark instances indicate that the PSG outperforms existing heuristic algorithms and rivals the exact algorithm in solution quality.     

Production scheduling in a market-driven foundry: a mathematical programming approach versus a project scheduling metaheuristic algorithm

This paper describes a real problem in a market-driven medium sized foundry delivering a wide range of castings to different markets. The problem consists of finding an efficient production plan to schedule the different processes (moulding, furnacing, cutting, tooling, etc.) needed to the manufacture of the pieces. Different objectives and resources and technical constraints must be taken into account. To solve this problem we have first developed a more classical integer linear programming approach based on a rolling horizon strategy. The most innovative contribution of the paper is that it models the problem as a project scheduling problem. Based on this model we present a metaheuristic algorithm that adapts techniques from the area. Computational experiments comparing both approaches are provided on instances created by a generator simulating real instances.     

Mathematical models and a hunting search algorithm for the no-wait flowshop scheduling with parallel machines

Majority of researches in no-wait flowshop scheduling assume that there is only one machine at each stage. But, factories commonly duplicate machines in parallel for each operation. In this case, they balance the speed of the stages, increase the throughput of the shop floor and reduce the impact of bottleneck stages. Despite their importance, there is no paper to study the general no-wait flowshop with parallel machines. This paper studies this problem where the objective is to minimise makespan. Since there is no mathematical model for the problem, we first mathematically formulate it in form of two mixed integer linear programming models. By the models, the small instances are optimally solved. We then propose a novel hunting search metaheuristic algorithm (HSA) to solve large instances of the problem. HSA is derived based on a model of group hunting of animals when searching for food. A set of experimental instances are carried out to evaluate the algorithm. The algorithm is carefully evaluated for its performance against an available algorithm by means of statistical tools. The related results show that the proposed HSA provides sound performance comparing with other algorithms.     

Multi-objective resource assignment problem in a product-driven supply chain using a Taguchi-based DNA algorithm

This paper conceptualises the integration of tangible and intangible factors into the design consideration of a resource assignment problem for a product-driven supply chain. The problem is formulated mathematically as a multi-objective optimisation model to maximise the broad objectives of profit, ahead of time of delivery, quality, and volume flexibility. Product characteristics are associated with the design requirements of a supply chain. Different types of resources are considered, each differing in its characteristics, thereby providing various alternatives during the design process. The aim is to design integrated supply chains that maximise the weighted sum of the objectives, the weights being decided by the desired product characteristics. The problem is solved through the proposed Taguchi-based DNA algorithm that draws its traits from random search optimisation and the statistical design of experiments. In order to minimise the effect of the causes of variations, the fundamental Taguchi method is integrated with the DNA-metaheuristic. The suggested methodology exhibits the global exploration capability to exploit the optimal or near-optimal DNA strands with a faster convergence rate. In order to authenticate the performance of the proposed solution methodology, a set of ten problem instances are considered and the results obtained are compared with that of the basic DNA, particle swarm optimisation (PSO) and its variant (PSO — time varying acceleration coefficients). The results demonstrate the benefits of the proposed algorithm for solving this type of problem.     

A VNS-LP algorithm for the robust dynamic maximal covering location problem

This study introduces a robust variant of the well-known dynamic maximal covering location problem (DMCLP) and proposes an integer linear programming formulation of the robust DMCLP. A hybrid approach for solving both deterministic and robust variant of the DMCLP is developed, which is based on hybridization of a Variable neighborhood search and a linear programming technique. The main idea is to split the problem into subproblems and to combine optimal solutions of the obtained subproblems in order to construct solution of the initial problem. The results of the proposed hybrid approach on instances of the deterministic DMCLP are presented and compared with the results of the state-of-the-art approach from the literature and with the results of commercial CPLEX solver. The presented computational analysis shows that the proposed hybrid algorithm outperforms other approaches for the DMCLP. In addition, the algorithm was tested on the instances of the robust variant of DMCLP, and obtained results are discussed in detail.

     

不均衡数据下基于SVM的故障检测新算法

针对传统支持向量机(SVM)算法在数据不均衡情况下无法有效实现故障检测的不足,提出一种基于过抽样和代价敏感支持向量机相结合的故障检测新算法。该算法首先利用边界人工少数类过抽样技术(BSMOTE)实现训练样本的均衡。为减少人工增加样本带来的噪声影响,利用K近邻构造一个代价敏感的支持向量机(CSSVM)算法,利用每个样本的代价函数消除噪声样本对SVM算法分类精度的影响。将该算法应用在轴承故障检测中,并同传统的SVM算法,不同类代价敏感SVM-C算法,SVM和SMOTE相结合的算法进行比较,试验结果表明当样本不均衡时,建议算法的故障检测性能较其它算法有显著提高。