Un algoritmo para el problema de corte en la industria del vidrio

• Francisco Parreno ^[1] ; María Teresa Alonso ^[1] ; Ramon Alvarez-Valdes ^[2]
  1. [1] Universidad de Castilla-La Mancha

     Universidad de Castilla-La Mancha

     Ciudad Real, España

     
  2. [2] Universitat de València

     Universitat de València

     Valencia, España

     
• Localización: BEIO, Boletín de Estadística e Investigación Operativa, ISSN 1889-3805, Vol. 40, Nº. 2, 2024, págs. 18-27
• Idioma: español
• Enlaces
  • Texto completo
• Resumen

  • The cutting problem proposed by Saint-Gobain Glass France for the ROADEF 2018 international competition is a two-dimensional cutting problem with many specific features: glass sheets can have defects that arise in the production process and therefore each sheet is unique and must be taken in the order of production. The parts to be cut for customers may be partially ordered and this order must be respected in the cutting process. Only guillotine cuts and no more than three cutting stages are allowed, although subsequent trimming is permitted. There are also some technical conditions, concerning the maximum and minimum distance between cuts and preventing the guillotine from cutting through a defect.

    These sets of constraints and the size of the actual instances, involving sometimes hundreds of pieces and tens of sheets, make the problem new and challenging. We have developed a beam search algorithm in which at each node some elements are added to the partial solution by a randomised constructive algorithm. The results obtained in the instances proposed for the competition improve on the best published solutions, reducing the average waste and producing many new best solutions.

• Referencias bibliográficas
  • Afsharian, M., Niknejad, A., and Wascher, G. (2014). A heuristic, dynamic programming-based approach for a two-dimensional ¨ cutting problem...
  • Araya, I. and Riff, M. (2014). A beam search approach to the container loading problem. Computers and Operations Research, 43:100–107.
  • Baldi, M., Crainic, T., Perboli, G., and Tadei, R. (2014). Branch-and-price and beam search algorithms for the variable cost and size bin...
  • Bennell, J., Cabo, M., and Martinez-Sykora, A. (2018). A beam search approach to solve the convex irregular bin packing problem with guillotine...
  • Bennell, J., Lee, L., and Potts, C. (2013). A genetic algorithm for two-dimensional bin packing with due dates. International Journal of Production...
  • Birgin, E., Ferreira, J., and Ronconi, D. (2020). A filtered beam search method for the m-machine permutation flowshops cheduling problem...
  • Chen, Q., Cui, Y., and Chen, Y. (2016). Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged...
  • Dusberger, F. and Raidl, G. (2015). Solving the 3-staged 2-dimensional cutting stock problem by dynamic programming and variable neighborhood...
  • Knopp, S., Dauzere-Peres, S., and Yugma, C. (2017). A batch-oblivious approach for complex job-shop scheduling problems. European Journal...
  • Martinez-Sykora, A., Alvarez-Valdes, R., Bennell, J., Ruiz, R., and Tamarit, J. (2017). Matheuristics for the irregular bin packing problem...
  • Parreno, F., Alonso, M. T., and Alvarez-Valdes, R. (2020). Solving a large cutting problem in the glass manufacturing industry. ˜ European...
  • Polyakovskiy, S. and M’Hallah, R. (2018). A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due...
  • Puchinger, J. and Raidl, G. (2007). Models and algorithms for three-stage two-dimensional bin packing. European Journal of Operational Research,...
  • Silva, E., Alvelos, F., and de Carvalho, J. V. (2010). An integer programming model for two- and three-stage two-dimensional cutting stock...
  • Tlilane, L. and Viaud, Q. (2018). Challenge ROADEF/EURO 2018. Cutting Optimization. Problem Description. http://www. roadef.org/challenge/2018/files/Challenge_ROADEF_EURO_SG_Description.pdf....