Title :
A pseudo-efficient frontier method for solving two-phase packing problems
Author :
Raz, David ; Sadeh, Arik
Author_Institution :
Manage. of Technol. Fac., HIT - Holon Inst. of Technol., Holon, Israel
Abstract :
Packing problems are very common and popular but typical solution procedures involve computation of numerous feasible solutions even for a small scale problem. These types of problems are commonly categorized as knapsack problem or bin packing problems and many of them are NP complete. An efficient mechanism for finding an exact solution for a two phase packing problem is proposed. The mechanism reduces the number of feasible solutions considered by conducting a naïve search for a pseudo efficient frontier of solutions for the first phase. Furthermore, by conduction the first phase in such a way, evaluating the second phase is made more efficient. An algorithm for the two dimensional case is presented along with proofs of correctness and complexity.
Keywords :
bin packing; optimisation; NP complete; bin packing problems; knapsack problem; pseudo-efficient frontier method; two-phase packing problems; Approximation algorithms; Approximation methods; Complexity theory; Containers; Force; Transportation; Vectors;
Conference_Titel :
Industrial Engineering and Engineering Management (IEEM), 2011 IEEE International Conference on
Conference_Location :
Singapore
Print_ISBN :
978-1-4577-0740-7
Electronic_ISBN :
2157-3611
DOI :
10.1109/IEEM.2011.6117903