Un problema no lineal de archivo de corte

• Autores: L. L. Salles Neto, A. C. Moretti
• Localización: Integración: Temas de matemáticas, ISSN 0120-419X, Vol. 28, Nº. 1, 2010 (Ejemplar dedicado a: Revista Integración), págs. 15-35
• Idioma: español
• Títulos paralelos:
  • A Nonlinear Cutting Stock Problem
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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.

  • English

    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.

     

• Referencias bibliográficas
  • Citas [1] Allowod J.M., and Goulimins C.N., “Reducing the number of patterns in one-dimensional cutting stock problems,” Control Section...
  • [2] Belov G., Scheithauer G., “The Number of Setups (Different Patterns) in One Dimensional Stock Cutting,” Technical Report MATH-NM -15-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,...
  • [5] Diegel A., Montocchio E., Walters E., Schalkwyk S. van, and Naidoo S., Setup minimising conditions in the trim loss problem, European...
  • [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,...
  • [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.,...
  • [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...
  • [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...
  • [30] Umetani S., Yagiura M., and Ibaraki T., One Dimensional Cutting Stock Problem to Minimize the Number of Different Patterns. European...
  • [31] Umetani S., and Yagiura M., One Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics...
  • [32] Vanderbeck F., Computational study of a column generation algorithm for bin packing and cutting stock problems, Math. Program., 86 (1999),...
  • [33] Vanderbeck F., Exact Algorithm for Minimising the Number of Setups in the OneDimensional Cutting Stock Problem, Oper. Res., 48 (2000),...
  • [34] Wascher G., and Gau T., Heuristics for the Integer One-dimensional Cutting Stock Problem: a computational study, OR Spek., 18 (1996),...
  • [35] Yanasse H.I., and Limeira M., A hybrid heuristic to reduce the number of different patterns in cutting stock problems, Comput. Oper....