Resumen

Consideramos el problema de empaquetado de tiras bidimensionales con cortes de guillotina. El problema consiste en empaquetar un conjunto de elementos rectangulares en una tira de anchura W y altura infinita. Los elementos empaquetados sin solaparse deben ser extraídos mediante una serie de cortes que van de un borde al borde opuesto (restricción de guillotina). Para resolver este problema, utilizamos un algoritmo dicotómico que utiliza un límite inferior, un límite superior y un algoritmo de prueba de viabilidad. El límite inferior se basa en la resolución de un programa lineal introduciendo nuevas desigualdades válidas. Para calcular el límite superior se utiliza una nueva heurística. Los resultados computacionales muestran que el algoritmo dicotómico, utilizando los nuevos límites, da buenos resultados en comparación con los métodos existentes.

• Materias:Algoritmos (Computadores) Ecuaciones Sistemas de empaque clasificado Transporte urbano Algoritmos (Matemáticas)
• Subjects:Computer algorithms Equations Order picking systems Urban transport Agorithms (Math)
• Palabras claves:Algoritmo dicotómico, cota superior, problema de empaquetamiento de tiras, nueva desigualdad válida, serie de corte, algoritmo de prueba de viabilidad, programa lineal, buenos resultados, nueva heurística, resultados computacionales
• Keywords:dichotomic algorithm, upper bound, strip packing problem, new valid inequality, series of cut, feasibility test algorithm, linear program, good results, new heuristic, computational results