Keywords
greedy algorithm
backtrack algorithm
one-dimensional cutting problem
Heurísticas
algoritmo goloso
algoritmo backtrack
problema unidimensional de cortes
How to Cite
Abstract
This paper reports an approach developed to find a good quality solution for a generalized assignment problem with application to the Dimensional Cutting Problem. The objective at the Cutting Problemis to divide different pools of pieces of the same dimension among different items of available material all having two dimensions, the width and length. The solution is found keeping the largest number of pieces in a single material. Some initial numerical experiences found for the algorithm optimal and suboptimal solutions orinstances of more than 500 pieces at a very low computational cost.
References
Beausoleil, R.P. (1997) “Heuristic algorithm for assignment problem with application in the factory of clothes”, Proceedings of the 13th ISPE/IEE International Conference on CAD/CAM Robotics and Factories of the Future: 995–1000.
Colin, R.R. (1993) Modern Heuristic Techniques for Combinatorial Problems. American Halsted Press, John Wiley and Sons Inc., New York
Golomb, S.W.; Baumert L.D. (1965) “Backtrack programming”, ACM Journal 12: 516–526.
Portela, J.M.; Kuzmich, V. (1989) Modelos Económico-Matemáticos, Tomo I. Editorial Pueblo y Educación.
Simmons, D.M. (1969) “One-dimensional space allocation: an ordering algorithm”, ORSA Journal 17(5): 812–826.