This paper presents the application of the one new approach using Genetic Algorithm in solving One-Dimensional Cutting Stock Problems in order to minimize two objectives, usually conflicting, i.e., the number of processed objects and setup while simultaneously treating them as a single goal. The model problem, the objective function, the method denominated SingleGA10 and the steps used to solve the problem are also presented. The obtained results of the SingleGA10 are compared to the following methods: SHP, Kombi234, ANLCP300 and Symbio10, found in literature, verifying its capacity to find feasible and competitive solutions. The computational results show that the proposed method, which only uses a genetic algorithm to solve these two objectives inversely related, provides good results.
TopIntroduction
With recent advances in computing, it has become important and valuable to study the problems of cutting and packing, as well as optimization models for the control and planning of production systems, which have been stimulated by various industries such as glass, paper, textile, chemical, among others, aimed at making their processes more efficient due to competition between companies in search of lower costs, reducing waste and efficiency in delivery.
The cutting stock problem consists in finding the best way to get parts of different sizes (items) from the cutting of larger pieces (objects) in order to minimize any kind of cost or maximize profit. The items are arranged on the object to perform cuts along the production. On the disposition of items is given the default name of cutting. It is important to highlight the importance of geometry on cutting stock problems, since the shapes and dimensions of items and objects determine their possible standards.
Kantorovick (1960) was a pioneer in the field of cutting stock problems. However, the breakthrough of the area was the work of Gilmore and Gomory (1961, 1963) studying the cutting stock problem through the process of column generation.
To solve a cutting stock problem you need the cutting patterns and the frequency of the patterns, ie the number of times that the standards will be implemented.
Although the overall objective is to minimize losses, there are several modelings of the problem, as the maximization of profits, the reduction of objects used, the production time and/or a combination of these.
The cost of preparing the machine is a relevant factor in some cutting processes. Thus, it is interesting to evaluate the effect of minimizing the number of processed objects (input minimization) and the minimizing of the number of cutting patterns (setup), goals which are partially conflicting, for a more general assessment of the cost. Haessler (1975) was the first to address the non-linear one-dimensional cutting stock problem this way. The objectives are considered inversely related or partially conflicting, because, as the setup, is reduced, the number of processed objects is increased.
For most formulations of the cutting problem there is no knowledge, until now, of a method that produces a solution in polynomial time. According to Salles Neto (2005), the large number of applications and the difficulty of solving the cutting problems, mostly NP-Complete, have led many researchers around the world to focus efforts on developing new and efficient methods of resolution, most of them heuristic.The problem discussed here belongs to the class NP-Complete. In this case the use of heuristics or metaheuristics is justified, generating, for these, good solutions in a short period of time.
According to Ribeiro et al. (2007), Metaheuristics are high-level procedures that coordinate simple heuristics and rules to find good (often optimal) approximate solutions to computationally dificult combinatorial optimization problems.
This work was conducted via the implementation of object-oriented programming for a new approach using a single genetic algorithm in order to solve the same problem initially treated by Haessler (1975), inspired by a recent approach presented by Golfeto et al. (2007, 2009b), in which two genetic algorithms, which interact themselves in a mutualistic relationship, aim to minimize the number of processed objects and setup. The approach here presented, aimed at achieving the same goals as Golfeto et al. (2007, 2009b) described, uses only a simple single genetic algorithm. Not known in the literature so far, the implementation of a single genetic algorithm to minimize these two goals simultaneously treated in a single objective version. In this paper, we will analyze the behavior of the proposed method, SingleGA10, to meet these goals and compare it with other methods.