Two dimensional guillotine cutting stock and scheduling problem in printing industry

Abstract

We address a two-dimensional cutting stock problem combined with production scheduling that arises in paper printing industry where printing orders arrive daily, together with their specifications and desired delivery dates The planner has to decide the printing patterns, their quantities to be printed, and their production dates. The printing pattern should comply with guillotine cuts having three stages. The objective is to minimize the total printing cost composed of paper and plate costs. For plates containing orders with print on both sides, two printing options exist. With the printing options and the option of placing copies of orders in only one pattern, the problem differs from previous studies and becomes challenging to be solved by a mathematical model. We develop a nonlinear integer programming (NIP) model to obtain exact solutions for small-sized instances and an efficient Genetic Algorithm (GA) to solve real-sized problems. We design packing routines that generate balanced printing patterns by putting multiple copies of items in one pattern. The GA also takes advantage of complex heuristics for production scheduling and pattern reduction. We evaluate the performance of the GA against the NIP model. Computational experiments on large-sized real-world data demonstrate the efficiency of the GA.