The Bin Packing Problem consists of: given a set of items of different sizes, we have as objective distribute them in bins with limited capacity, minimizing the number of bins used. A generalization for the Bin Packing Problem is the Colored Bin Packing Problem, in which each item has a size and a color, with an extra restriction in which say that two items of the same color cannot be packed one after the other. Both problems belonging to the NP-hard class, what implies not there are algorithms that optimally solve them in polynomial time, unless than P = NP. Since, in general, algorithms not polynomial time are expensive, then is support the use of meta-heuristics for the solution of NP-hard problems, which usually provide solutions near the optimal solutions in a computationally reasonable time. In this project, will be studied meta-heuristics for the Colored Bin Packing Problem, an approach that is still unexplored in the literature. Besides, the project also aims to enroll the candidate in the field of scientific research and complementing his graduation.
News published in Agência FAPESP Newsletter about the scholarship: