2014
Authors
Brandao, F; Pedroso, JP;
Publication
COMPUTERS & OPERATIONS RESEARCH
Abstract
The conventional assignment-based first/best fit decreasing algorithms (FFD/BFD) are not polynomial in the one-dimensional cutting stock input size in its most common format. Therefore, even for small instances with large demands, it is difficult to compute FFD/BFD solutions. We present pattern-based methods that overcome the main problems of conventional heuristics in cutting stock problems by representing the solution in a much more compact format Using our pattern-based heuristics, FFD/BFD solutions for extremely large cutting stock instances, with billions of items, can be found in a very short amount of time.
2016
Authors
Brandao, F; Pedroso, JP;
Publication
COMPUTERS & OPERATIONS RESEARCH
Abstract
We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems-including multi-constraint variants-by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model. Our formulation is equivalent to Gilmore and Gomory's, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern. The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and other problems. We report computational results obtained with many benchmark test datasets, some of them showing a large advantage of this formulation with respect to the traditional ones.
2014
Authors
Brandão, F; Pedroso, JP;
Publication
EURO J. Computational Optimization
Abstract
The traveling tournament problem is a sports scheduling problem that includes two major issues in creating timetables: home/away pattern feasibility and travel distance. In this problem, the schedule must be compact: every team plays in every time slot. However, there are some sports leagues that have both home/away pattern restrictions and distance limits, but do not require a compact schedule. In such schedules, one or more teams can have a bye in any time slot. This leads us to a variant of the problem: the relaxed traveling tournament problem. We present a complete search method to solve this problem based on branch-and-bound, metaheuristics and dynamic programming. © 2013, Springer-Verlag Berlin Heidelberg and EURO - The Association of European Operational Research Societies.
The access to the final selection minute is only available to applicants.
Please check the confirmation e-mail of your application to obtain the access code.