Research and Innovation Articles
Published 2010-06-09
Keywords
- Cutting Stock Problem,
- nonlinear Programming,
- discontinuousCost
How to Cite
Salles Neto, L. L., & Moretti, A. C. (2010). A Nonlinear Cutting Stock Problem. Revista Integración, Temas De matemáticas, 28(1), 15–35. Retrieved from https://revistas.uis.edu.co/index.php/revistaintegracion/article/view/2057
Abstract
In this work we introduce a new method to minimize the numberof processed objects and the setup number in a unidimensional cutting stockproblem. A nonlinear integer programming problem can be used to representthe problem studied here. The term related to the minimization of the setupnumber is a nonlinear discontinuous function, we smooth it and generate thecutting patterns using a modified Gilmore-Gomory strategy. Numerical testson a wide range of test problems are very encouraging and the new methodcompares favorably with other methods in the literature.
Downloads
Download data is not yet available.
References
[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