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

Francisco Parreño Torres , M.T. Alonso, Ramón Álvarez Valdés

• 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.