论文快速发表网

社科类论文文艺类论文建筑类论文新闻类论文农林类论文教育类论文管理类论文医学类论文科技类论文法学类论文

EI Compendex Source List（2020年1月） EI Compendex Source List（2019年5月） EI Compendex Source List（2018年9月） EI Compendex Source List（2018年5月） EI Compendex Source List（2018年1月）中国科学引文数据库来源期刊列 CSSCI(2017-2018)及扩展期刊目录 2017年4月7日EI检索目录（最新） 2017年3月EI检索目录最新公布北大中文核心期刊目录 SCI期刊（含影响因子） EI Compendex Source List

本站服务项目浅谈青年教师如何开展教科研大学青年教师如何处理教学和科

论文范文

Novel Methods Generated by Genetic Programming for the Guillotine-Cutting Problem 时间:2018-09-24 00:06 来源:未知作者:admin 点击: 次 Abstract:New constructive algorithms for the two-dimensional guillotine-cutting problem are presented. The algorithms were produced from elemental algorithmic components using evolutionary computation. A subset of the components was selected from a previously existing constructive algorithm. The algorithms’ evolution and testing process used a set of 46 instances from the literature. The structure of three new algorithms is described, and the results are compared with those of an existing constructive algorithm for the problem. Several of the new algorithms are competitive with respect to a state-of-the-art constructive algorithm. A subset of novel instructions, which are responsible for the majority of the new algorithms’ good performances, has also been found.
1. Introduction
Various industrial processes exist in which the raw material must be cut into smaller sections that must be assembled to produce the final product, as in the case of cutting plastics, glass, paper, and metals [1–3]. A typical case occurs in the wooden board cutting industry that requires efficient techniques to minimize the loss of material in furniture manufacturing. A piece of furniture is manufactured from rectangular pieces of wood cut from rectangular wooden plates by a saw which allows an end-to-end cutting of the plate [4, 5]. In turn, Park et al. [6] describe the situation that occurs during the manufacturing and cutting of glass. In such a case, a continuously produced sheet of glass is cut into large sheets, which in turn are cut into smaller rectangular pieces according to the customer requirements. The cut is made according to an optimal cutting pattern that minimizes wasted glass. These kinds of processes generated a family of stock cutting problems, which aim at determining the best method of using raw materials [7].
Often approached from a combinatorial optimization perspective, cutting problems represent an intellectual challenge because of the computational difficulty that arises when attempting to solve them [8]. A particular case is the constrained two-dimensional guillotine-cutting problem studied in this paper, which focuses on cutting rectangular plates [9, 10].
The statement of the problem considers a rectangular plate of length L and width W that must be cut into a set of m small rectangular pieces p1, p2,…, pm of sizes and li and area such that ≤ W and for every i ∈ P = {1,2,…,m}. A limit bi > 0 ∀ i ∈ P that corresponds to the number of times that piece i, with profit , can be cut from the rectangular plate is considered. A cutting pattern is a feasible configuration of pieces to be cut from the plate. The geometric feasibility of the cutting pattern considers that (i) all cuts must be of the guillotine type, (ii) there should be no overlap among the pieces that constitute the pattern, and (iii) the pieces must be positioned in a fixed orientation. Defining xi ∈ as the number of times that a piece of type i is found in a pattern, the problem lies in determining a cutting pattern with a maximum value such that 0 ≤ xi ≤ bi, ∀ i ∈ P. Following the commonly used notation [11, 12], the problem corresponds to the constrained weighted version (CW_TDC). Conversely, following the classification of Wäscher et al. [7], this case corresponds to a two-dimensional, rectangular, single large object placement problem.