Abstract

Abstract
In this chapter the Basic Multi-Project Scheduling Problem (BMPSP) is described, an overview of the literature on multi-project scheduling is provided, and a solution approach based on a biased random-key genetic algorithm (BRKGA) is presented. The BMPSP consists in finding a schedule for all the activities belonging to all the projects taking into account the precedence constraints and the availability of resources, while minimizing some measure of performance. The representation of the problem is based on random keys. The BRKGA generates priorities, delay times, and release dates, which are used by a heuristic decoder procedure to construct parameterized active schedules. The performance of the proposed approach is validated on a set of randomly generated problems. © Springer International Publishing Switzerland 2015.

Abstract
This paper presents a newedge-swap heuristic for generating spanning trees with a minimum number of branch vertices, i.e. vertices of degree greater than two. This problem was introduced in Gargano et al. (Lect Notes Comput Sci 2380:355-365, 2002) and has been called the minimum branch vertices problem by Cerulli et al. (Comput Optim Appl 42:353-370, 2009). The heuristic starts with a random spanning tree and iteratively reduces the number of branch vertices by swapping tree edges with edges not currently in the tree. It can be easily implemented as a multi-start heuristic. We report on extensive computational experiments comparing single-start and multi-start variants on our heuristic with other heuristics previously proposed in the literature.

Abstract
In this paper we present a novel biased random-key genetic algorithm (BRKGA) for 2D and 3D bin packing problems. The approach uses a maximal-space representation to manage the free spaces in the bins. The proposed algorithm hybridizes a novel placement procedure with a genetic algorithm based on random keys. The BRKGA is used to evolve the order in which the boxes are packed into the bins and the parameters used by the placement procedure. Two new placement heuristics are used to determine the bin and the free maximal space where each box is placed. A novel fitness function that improves significantly the solution quality is also developed. The new approach is extensively tested on 858 problem instances and compared with other approaches published in the literature. The computational experiment results demonstrate that the new approach consistently equals or outperforms the other approaches and the statistical analysis confirms that the approach is significantly better than all the other approaches.

Abstract
Random key genetic algorithms are heuristic methods for solving combinatorial optimization problems. They represent solutions as vectors of randomly generated real numbers, the so-called random keys. A deterministic algorithm, called a decoder, takes as input a vector of random keys and associates with it a feasible solution of the combinatorial optimization problem for which an objective value or fitness can be computed. We compare three types of random-key genetic algorithms: the unbiased algorithm of Bean (1994); the biased algorithm of Gonçalves and Resende (2010); and a greedy version of Bean's algorithm on 12 instances from four types of covering problems: general-cost set covering, Steiner triple covering, general-cost set k-covering, and unit-cost covering by pairs. Experiments are run to construct runtime distributions for 36 heuristic/instance pairs. For all pairs of heuristics, we compute probabilities that one heuristic is faster than the other on all 12 instances. The experiments show that, in 11 of the 12 instances, the greedy version of Bean's algorithm is faster than Bean's original method and that the biased variant is faster than both variants of Bean's algorithm. © 2014 Brazilian Operations Research Society.

Abstract
This paper deals with a very common problem in the home-textile industry. Given a set of orders of small rectangles of fabric the problem consists of determining the lengths and widths of a set of large rectangles of fabric to be produced and the corresponding cutting patterns. The objective is to minimize the total quantity of fabric necessary to satisfy all orders. The approach proposed uses a biased random-key genetic algorithm for generating sets of cutting patterns which are the input to a sequential heuristic procedure which generates a solution. Experimental tests based on a set of 100 random generated problems with known optimal solution validate quality of the approach.