A matching approach for replenishing rectangular stock sizes

Consider a replenishment problem in which several different rectangular siz es of material are stocked. Customers order rectangles of the material, but the rectangles ordered have a range on specified width as well as on speci fied length. To satisfy the customer requirements, the stock material can b e cut once longitudinally in order to satisfy two customer requirements or not cut at all, that is, an entire stock piece of material is used to satis fy one customer requirement. If an exact match is impossible in the current planning period the unused material must be returned to stock- an expensiv e and undesirable situation. In this paper, a nonbipartite weighted matchin g problem formulation will be given for determining the replenishment requi rements of rectangular stock sizes. Then, a hybrid solution approach, capab le of solving real applications (typically up to 3000 nodes) efficiently, w ill be discussed. This solution was implemented in September 1998 and has o perated successfully since then.