RESUMO
We use the Positions and Covering methodology to obtain exact solutions for the two-dimensional, non-guillotine restricted, strip packing problem. In this classical NP-hard problem, a given set of rectangular items has to be packed into a strip of fixed weight and infinite height. The objective consists in determining the minimum height of the strip. The Positions and Covering methodology is based on a two-stage procedure. First, it is generated, in a pseudo-polynomial way, a set of valid positions in which an item can be packed into the strip. Then, by using a set-covering formulation, the best configuration of items into the strip is selected. Based on the literature benchmark, experimental results validate the quality of the solutions and method's effectiveness for small and medium-size instances. To the best of our knowledge, this is the first approach that generates optimal solutions for some literature instances for which the optimal solution was unknown before this study.
Assuntos
Algoritmos , Simulação por ComputadorRESUMO
We present a two-stage methodology called Positions and Covering (P&C) to solve the two-dimensional bin packing problem (2D-BPP). The objective of this classical combinatorial NP-hard problem is to pack a set of items (small rectangles) in the minimum number of bins (larger rectangles). The first stage is the key-point of the Positions and Covering, where for each item, it is generated in a pseudo-polynomial way a set of valid positions that indicate the possible ways of packing the item into the bin. In the second stage, a new set-covering formulation, strengthen with three sets of valid inequalities, is used to select the optimal non-overlapping configuration of items for each bin. Experimental results for the P&C method are presented and compared with some of the best algorithms in the literature for small and medium size instances. Furthermore, we are considering both cases of the 2D-BPP, with and without rotations of the items by 90°. To the best of our knowledge, this is one of the first exact approaches to obtain optimal solutions for the rotation case.
Assuntos
Biologia Computacional , Modelos Teóricos , Software , Algoritmos , Simulação por Computador , Alinhamento de SequênciaRESUMO
Vegetation health assessment by using airborne multispectral images throughout crop production cycles, among other precision agriculture technologies, is an important tool for modern agriculture practices. However, to really take advantage of crop fields imagery, specialized analysis techniques are needed. In this paper we present a geographic object-based image analysis (GEOBIA) approach to examine a set of very high resolution (VHR) multispectral images obtained by the use of small unmanned aerial vehicles (UAVs), to evaluate plant health states and to generate cropland maps for Capsicum annuum L. The scheme described here integrates machine learning methods with semi-automated training and validation, which allowed us to develop an algorithmic sequence for the evaluation of plant health conditions at individual sowing point clusters over an entire parcel. The features selected at the classification stages are based on phenotypic traits of plants with different health levels. Determination of areas without data dependencies for the algorithms employed allowed us to execute some of the calculations as parallel processes. Comparison with the standard normalized difference vegetation index (NDVI) and biological analyses were also performed. The classification obtained showed a precision level of about 95 % in discerning between vegetation and non-vegetation objects, and clustering efficiency ranging from 79 % to 89 % for the evaluation of different vegetation health categories, which makes our approach suitable for being incorporated at C. annuum crop's production systems, as well as to other similar crops. This methodology can be reproduced and adjusted as an on-the-go solution to get a georeferenced plant health estimation.