Artículo Original
Publicado 2010-06-09
Palabras clave
- Problema de archivo de corte,
- programación no lineal,
- costodiscontinuo
Cómo citar
Salles Neto, L. L., & Moretti, A. C. (2010). Un problema no lineal de archivo de corte. Revista Integración, Temas De matemáticas, 28(1), 15–35. Recuperado a partir de https://revistas.uis.edu.co/index.php/revistaintegracion/article/view/2057
Resumen
En este trabajo presentamos un nuevo método para reducir almínimo el número de objetos elaborados y el número de patrones de corte enun problema de corte unidimensional. Un problema de programación enterano lineal se puede utilizar para representar el problema estudiado. El términorelacionado con la reducción al mínimo del número de patrones de corte esuna función discontinua no lineal, la cual suavizamos y genera los patronesde corte utilizando una estrategia de modificación Gilmore-Gomory. Pruebasnuméricas en una amplia gama de problemas fueron muy alentadores y elnuevo método se compara favorablemente con otros métodos en la literatura.
Descargas
Los datos de descargas todavía no están disponibles.
Referencias
[1] Allowod J.M., and Goulimins C.N., “Reducing the number of patterns in one-dimensional cutting stock problems,” Control Section Report No EE/CON/IC/88/10, Industrial Systems Group, Department of Electical Engineering, Imperial College, London, 1988.
[2] Belov G., Scheithauer G., “The Number of Setups (Different Patterns) in One Dimensional Stock Cutting,” Technical Report MATH-NM -15-2003, Dresden University, 2003.
[3] Chvatal V., “Linear Programming,” Freeman, San Francisco, 1983.
[4] Diegel A., Chetty M., Van Schalkwyk S., and Naidoo S., “Setup combining in the trim loss problem -3-to-2 & 2-to-1,” Working paper, Business Administration, University of Natal, Durban, First Draft, 1993.
[5] Diegel A., Montocchio E., Walters E., Schalkwyk S. van, and Naidoo S., Setup minimising conditions in the trim loss problem, European J. Oper. Res., 95 (1996), 631-640.
[6] Dowsland K. and Dowsland W., Packing Problems, European J. Oper. Res., 56 (1992), 2-14.
[7] Dyckhoff H., A typology of cutting and packing problems, European J. Oper. Res., 44 (1990), 145-159.
[8] Dyckhoff H., and Finke U., “Cutting and Packing in Production and Distribution: A Typology and Bibliography,” Springer-Verlag Co, Heidelberg, 1992.
[9] Eilon S., Optimizing the shearing of steel bars, J. Mech. Eng. Sci. 2 (1960), 129-142.
[10] Foester H., and Wascher G., Pattern Reduction in One-dimensional Cutting-Stock Problems, Internat. J. Prod. Res., 38 (2000), 1657-1676.
[11] Gau T., and Wascher G., CUTGEN1: A Problem Generator for the Standard One -dimensional Cutting Stock Problem, European J. Oper. Res., 84 (1995), 572-579.
[12] Gilmore P.C., and Gomory R.E., A Linear Programming Approach to the Cutting Stock Problem, Oper. Res., 9 (1961), 849-859.
[13] Gilmore P.C., and Gomory R.E., A Linear Programming Approach to the Cutting Stock Problem, Oper. Res., 11 (1963), 863-888.
[14] Haessler R., Controlling Cutting Pattern Changes in One-Dimensional Trim Problems, Oper. Res., 23 (1975), 483-493.
[15] Haessler R., A Note on Computational Modifications to the Gilmore-Gomory Cutting Stock Algorithm, Oper. Res., 28 (1980), 1001-1005.
[16] Hardley C.J., Optimal cutting of zinc-coated steel strip, Oper. Res., 4 (1976), 92-100.
[17] Heuts R., and Deklein J., An (S-Q) inventory model with stochastic and interrelated lead times, Naval Res. Logist., 42 (1995), 839-859.
[18] Hinxman A., The trim loss and assortment problems: a survey, European J. Oper. Res., 5 (1980), 8-18.
[19] Johnston R.E., Rounding algorithms for cutting stock problems, Asia-Pac. J. Oper. Res., 3 (1986), 166-171.
[20] Kantorovich L.V., Mathematical Methods of Organizing and Planning Production, Management Sci., 6 (1960), 366-422.
[21] Krejic M., Martinez J.M. et al., Validation of an Augmented Lagrangian algorithm with a Gauss-Newton
Hessian approximation using a set of hard-spheres problems, Comput. Optim. Appl., 16 (2000), 247-263.
[22] Maia L., Valério de Carvalho L.A., Quassim R., Synthesis of utility systems by simulated annealing, Comp. Chemical Eng., 19 (1995), 481-488.
[23] Martello S., Toth P., Knapsack Problems: Algotithms and Computer Implementations, John Wiley & Sons, New York, 1990.
[24] Martinez J.M., Minimization of discontinuous cost functions by smoothing, Acta Applicandae Mathematical, 71 (2001), 245-260.
[25] McDiamird C., Pattern minimisation in cutting stock problems, Discrete Appl. Math., 98 (1999), 121-130.
[26] Metzger R.W., Stock Slitting. Elementary Mathematical Programming, Wiley, 1958.
[27] Paull A.E., and Walter J.R., “The trim problem: an application of linear programming to the manufacture of news-print paper, Presented at Annual Meeting of Econometric Society, Montreal, 10-13, 1954.
[28] Stadler H., A one-dimensional cutting stock problem in the aluminium industry and its solution, European J. Oper. Res., 44 (1990), 209-223.
[29] Turkay M., and Grossmann I.E., Disjunctive Programming Techniques for the Optimization of Process Systems with Discontinuous Investment Costs-Multiple Size Regions, Ind. Eng. Chem. Res., 35 (1996), 2611-2623.
[30] Umetani S., Yagiura M., and Ibaraki T., One Dimensional Cutting Stock Problem to Minimize the Number of Different Patterns. European J. Oper. Res., 146 (2003), 388-402.
[31] Umetani S., and Yagiura M., One Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics and Linear Programming, Journal of Mathematical Modelling and Algorithms, 5 (2006), 43-64.
[32] Vanderbeck F., Computational study of a column generation algorithm for bin packing and cutting stock problems, Math. Program., 86 (1999), 565-594.
[33] Vanderbeck F., Exact Algorithm for Minimising the Number of Setups in the OneDimensional Cutting Stock Problem, Oper. Res., 48 (2000), 915-926.
[34] Wascher G., and Gau T., Heuristics for the Integer One-dimensional Cutting Stock Problem: a computational study, OR Spek., 18 (1996), 131-144.
[35] Yanasse H.I., and Limeira M., A hybrid heuristic to reduce the number of different patterns in cutting stock problems, Comput. Oper. Res., 33 (2006), 2744-2756
[2] Belov G., Scheithauer G., “The Number of Setups (Different Patterns) in One Dimensional Stock Cutting,” Technical Report MATH-NM -15-2003, Dresden University, 2003.
[3] Chvatal V., “Linear Programming,” Freeman, San Francisco, 1983.
[4] Diegel A., Chetty M., Van Schalkwyk S., and Naidoo S., “Setup combining in the trim loss problem -3-to-2 & 2-to-1,” Working paper, Business Administration, University of Natal, Durban, First Draft, 1993.
[5] Diegel A., Montocchio E., Walters E., Schalkwyk S. van, and Naidoo S., Setup minimising conditions in the trim loss problem, European J. Oper. Res., 95 (1996), 631-640.
[6] Dowsland K. and Dowsland W., Packing Problems, European J. Oper. Res., 56 (1992), 2-14.
[7] Dyckhoff H., A typology of cutting and packing problems, European J. Oper. Res., 44 (1990), 145-159.
[8] Dyckhoff H., and Finke U., “Cutting and Packing in Production and Distribution: A Typology and Bibliography,” Springer-Verlag Co, Heidelberg, 1992.
[9] Eilon S., Optimizing the shearing of steel bars, J. Mech. Eng. Sci. 2 (1960), 129-142.
[10] Foester H., and Wascher G., Pattern Reduction in One-dimensional Cutting-Stock Problems, Internat. J. Prod. Res., 38 (2000), 1657-1676.
[11] Gau T., and Wascher G., CUTGEN1: A Problem Generator for the Standard One -dimensional Cutting Stock Problem, European J. Oper. Res., 84 (1995), 572-579.
[12] Gilmore P.C., and Gomory R.E., A Linear Programming Approach to the Cutting Stock Problem, Oper. Res., 9 (1961), 849-859.
[13] Gilmore P.C., and Gomory R.E., A Linear Programming Approach to the Cutting Stock Problem, Oper. Res., 11 (1963), 863-888.
[14] Haessler R., Controlling Cutting Pattern Changes in One-Dimensional Trim Problems, Oper. Res., 23 (1975), 483-493.
[15] Haessler R., A Note on Computational Modifications to the Gilmore-Gomory Cutting Stock Algorithm, Oper. Res., 28 (1980), 1001-1005.
[16] Hardley C.J., Optimal cutting of zinc-coated steel strip, Oper. Res., 4 (1976), 92-100.
[17] Heuts R., and Deklein J., An (S-Q) inventory model with stochastic and interrelated lead times, Naval Res. Logist., 42 (1995), 839-859.
[18] Hinxman A., The trim loss and assortment problems: a survey, European J. Oper. Res., 5 (1980), 8-18.
[19] Johnston R.E., Rounding algorithms for cutting stock problems, Asia-Pac. J. Oper. Res., 3 (1986), 166-171.
[20] Kantorovich L.V., Mathematical Methods of Organizing and Planning Production, Management Sci., 6 (1960), 366-422.
[21] Krejic M., Martinez J.M. et al., Validation of an Augmented Lagrangian algorithm with a Gauss-Newton
Hessian approximation using a set of hard-spheres problems, Comput. Optim. Appl., 16 (2000), 247-263.
[22] Maia L., Valério de Carvalho L.A., Quassim R., Synthesis of utility systems by simulated annealing, Comp. Chemical Eng., 19 (1995), 481-488.
[23] Martello S., Toth P., Knapsack Problems: Algotithms and Computer Implementations, John Wiley & Sons, New York, 1990.
[24] Martinez J.M., Minimization of discontinuous cost functions by smoothing, Acta Applicandae Mathematical, 71 (2001), 245-260.
[25] McDiamird C., Pattern minimisation in cutting stock problems, Discrete Appl. Math., 98 (1999), 121-130.
[26] Metzger R.W., Stock Slitting. Elementary Mathematical Programming, Wiley, 1958.
[27] Paull A.E., and Walter J.R., “The trim problem: an application of linear programming to the manufacture of news-print paper, Presented at Annual Meeting of Econometric Society, Montreal, 10-13, 1954.
[28] Stadler H., A one-dimensional cutting stock problem in the aluminium industry and its solution, European J. Oper. Res., 44 (1990), 209-223.
[29] Turkay M., and Grossmann I.E., Disjunctive Programming Techniques for the Optimization of Process Systems with Discontinuous Investment Costs-Multiple Size Regions, Ind. Eng. Chem. Res., 35 (1996), 2611-2623.
[30] Umetani S., Yagiura M., and Ibaraki T., One Dimensional Cutting Stock Problem to Minimize the Number of Different Patterns. European J. Oper. Res., 146 (2003), 388-402.
[31] Umetani S., and Yagiura M., One Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics and Linear Programming, Journal of Mathematical Modelling and Algorithms, 5 (2006), 43-64.
[32] Vanderbeck F., Computational study of a column generation algorithm for bin packing and cutting stock problems, Math. Program., 86 (1999), 565-594.
[33] Vanderbeck F., Exact Algorithm for Minimising the Number of Setups in the OneDimensional Cutting Stock Problem, Oper. Res., 48 (2000), 915-926.
[34] Wascher G., and Gau T., Heuristics for the Integer One-dimensional Cutting Stock Problem: a computational study, OR Spek., 18 (1996), 131-144.
[35] Yanasse H.I., and Limeira M., A hybrid heuristic to reduce the number of different patterns in cutting stock problems, Comput. Oper. Res., 33 (2006), 2744-2756