The study of theoretical and practical combinatorial optimization problems applied...
Cutting and Packing Problems: Practical and Theoretical Approaches
Cutting, packing, lot-sizing and scheduling problems and their integration in indu...
Grant number: | 16/14132-4 |
Support type: | Scholarships in Brazil - Post-Doctorate |
Effective date (Start): | January 01, 2017 |
Effective date (End): | January 28, 2018 |
Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |
Principal Investigator: | Flávio Keidi Miyazawa |
Grantee: | Carla Negri Lintzmayer |
Home Institution: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil |
Abstract This project aims to study and develop algorithms for packing problems. A classic example is the bin packing problem, for which the input is a list of items (each one with a size) and we want to pack them in the smallest number of bins (where the bins have a maximum size). Several of the simplest variations of packing problems belong to the class of NP-hard problems. In this project, we are interested in investigating variations of packing problems in one or two dimensions, which present restrictions of unloading or conflicts over the items of the input. For example, we can consider conflict restrictions when some items cannot be packed in the same bin or unloading restrictions when some packing order must be considered. Our goal is the theoretical study of some of these problems, with the development of algorithms for their open cases, emphasizing the study of approximation algorithms. (AU) | |