Bun splitting: an online cutting problem with defects from the food industry

In this article we address an online cutting problem with defects that arises in the food industry originally proposed by Glass and van Oostrum ([2010]. “Bun Splitting: A Practical Cutting Stock Problem.” Annals of Operations Research 179: 15–33): the Bun Splitting Problem. The problem involves splitting buns that are baked in large trays into package-size blocks while removing defective buns. Removing defective buns results in small blocks of buns that need to be assembled into package-size blocks at the subsequent packing phase. The primary objective in this splitting process is the minimisation of packing time; however, reducing the number of small blocks awaiting assembly is also a secondary concern. In this study, we relax simplifying assumptions imposed in the previous work to allow for multiple defects in the tray, production switchovers between different package sizes as well as a general defect distribution on the tray. We solve the resulting online cutting problem using a dynamic programming-based algorithm and demonstrate that the algorithm is capable of producing locally optimal solutions in a real-time production environment. We also discuss how the same approach can be adopted to other cutting problems with defects from various industries.