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

  1. Francisco Parreno 1
  2. María Teresa Alonso 1
  3. Ramon Alvarez-Valdes 2
  1. 1 Universidad de Castilla-La Mancha
    info

    Universidad de Castilla-La Mancha

    Ciudad Real, España

    ROR https://ror.org/05r78ng12

  2. 2 Universitat de València
    info

    Universitat de València

    Valencia, España

    ROR https://ror.org/043nxc105

Revista:
BEIO, Boletín de Estadística e Investigación Operativa

ISSN: 1889-3805

Any de publicació: 2024

Volum: 40

Número: 2

Pàgines: 18-27

Tipus: Article

DIALNET GOOGLE SCHOLAR lock_openAccés obert editor

Altres publicacions en: BEIO, Boletín de Estadística e Investigación Operativa

Resum

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.

Referències bibliogràfiques

  • Afsharian, M., Niknejad, A., and Wascher, G. (2014). A heuristic, dynamic programming-based approach for a two-dimensional ¨ cutting problem with defects. OR Spectrum, 36:971–999.
  • 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 packing problem with optional items. Annals of Operations Research, 222:125–141.
  • Bennell, J., Cabo, M., and Martinez-Sykora, A. (2018). A beam search approach to solve the convex irregular bin packing problem with guillotine cuts. European Journal of Operational Research, 270:89–102.
  • Bennell, J., Lee, L., and Potts, C. (2013). A genetic algorithm for two-dimensional bin packing with due dates. International Journal of Production Economics, 145:547–560.
  • Birgin, E., Ferreira, J., and Ronconi, D. (2020). A filtered beam search method for the m-machine permutation flowshops cheduling problem minimizing the earliness and tardiness penalties and the waiting time of the jobs. Computers and Operations Research, 114:104824.
  • Chen, Q., Cui, Y., and Chen, Y. (2016). Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns. Optimization Methods and Software, 31:68–87.
  • Dusberger, F. and Raidl, G. (2015). Solving the 3-staged 2-dimensional cutting stock problem by dynamic programming and variable neighborhood search. Electronic Notes in Discrete Mathematics, 47:133–140.
  • Knopp, S., Dauzere-Peres, S., and Yugma, C. (2017). A batch-oblivious approach for complex job-shop scheduling problems. European Journal of Operational Research, 263:50–61.
  • Martinez-Sykora, A., Alvarez-Valdes, R., Bennell, J., Ruiz, R., and Tamarit, J. (2017). Matheuristics for the irregular bin packing problem with free rotations. European Journal of Operational Research, 258:440–455.
  • Parreno, F., Alonso, M. T., and Alvarez-Valdes, R. (2020). Solving a large cutting problem in the glass manufacturing industry. ˜ European Journal of Operational Research, 287:378-388.
  • Polyakovskiy, S. and M’Hallah, R. (2018). A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates. European Journal of Operational Research, 266:819–839.
  • Puchinger, J. and Raidl, G. (2007). Models and algorithms for three-stage two-dimensional bin packing. European Journal of Operational Research, 183:1304–1327.
  • Silva, E., Alvelos, F., and de Carvalho, J. V. (2010). An integer programming model for two- and three-stage two-dimensional cutting stock problems. European Journal of Operational Research, 205:699–708.
  • 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. Accessed on 2018-03-15.
Fuente de los datos: Dialnet