A matching approach for replenishing rectangular stock sizes
- PDF / 147,668 Bytes
- 5 Pages / 595 x 842 pts (A4) Page_size
- 39 Downloads / 155 Views
#2000 Operational Research Society Ltd. All rights reserved. 0160-5682/00 $15.00 http://www.stockton-press.co.uk/jors
A matching approach for replenishing rectangular stock sizes FJ Vasko1,2*, JA McNamara2, RN Parkes2, FE Wolf 2 and LR Woodyatt2 1
Kutztown University, Kutztown, USA; and 2Bethlehem Steel Corporation, Bethlehem, USA
Consider a replenishment problem in which several different rectangular sizes of material are stocked. Customers order rectangles of the material, but the rectangles ordered have a range on speci®ed width as well as on speci®ed length. To satisfy the customer requirements, the stock material can be 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 satisfy one customer requirement. If an exact match is impossible in the current planning period, the unused material must be returned to stockÐ an expensive and undesirable situation. In this paper, a nonbipartite weighted matching problem formulation will be given for determining the replenishment requirements of rectangular stock sizes. Then, a hybrid solution approach, capable of solving real applications (typically up to 3000 nodes) ef®ciently, will be discussed. This solution was implemented in September 1998 and has operated successfully since then. Keywords: graph matching; practice of OR; cutting stock; heuristics
Introduction In this paper, an application will be discussed in which the replenishment requirements for rectangular stock material must be determined. This application is interesting because customers specify an acceptable range on both the width and length of their rectangular requirements. The customer requirements are mapped into the stock material such that, at most, two customer requirements can be satis®ed from one stock piece of material. The material length for both the customer orders and the stock sizes is much longer than it is wide, that is, there is only one orientation for cutting the material. Therefore, at most, one longitudinal cut is made in the stock material. A severe limitation of this application is that the stock piece must be used completely, that is, there can be no scrap loss other than that caused by the cut. If an exact match is impossible in the current planning period, then the unused material must be returned to stockÐ an expensive and undesirable situation. For productivity and yield reasons at the producing facility, the production of wide stock material is desired. For this reason, the majority of stock material is cut longitudinally into two customer requirements (both requirements can be for the same customer). Typical cutting patterns are given in Figure 1. Firstly, the problem will be described and the initiallyimplemented replenishment system will be reviewed. Then, the application of customer requirements to stock sizes *Correspondence: Dr FJ Vasko, Homer Research Laboratories, Bethlehem Steel Corporation, Bethlehem, PA 18016, USA E-mail: [email protected]
will be formulated as a nonbiparti
Data Loading...
