The One Dimensional Cutting Stock Problem Using

This paper considers the cutting stock problem with two objectives. The primary objective is to minimize the trim loss in a given piece of metal work requiring metal sections of various lengths. The secondary objective is to organize the cutting so that the maximum quantity of leftovers is accumulated in the last bar(s). This leftover will then be of a length allowing it to be used in the future. An algorithm which provides an optimal solution is presented for this problem. However, it may not be efficient for large problems. Consequently, a heuristic approach is suggested, with the large problem being divided (decom- posed) into smaller ones: the remainder of one problem being used in the next. This model was developed for a small metal workshop in a kibbutz. This paper presents the metal cutting problem using two objective functions. The algorithm sug- gested here was developed for the small workshop of Kibbutz Samar in Israel, and is actually used there. The workshop was originally set up to produce a date harvester invented in the kibbutz. Even- tually, the workshop extended its activities to various types of metal work, such as furniture, pipelines and agricultural implements. The metal stock is composed of various metal bars and pipes, which are purchased in standard lengths (usually 6 m each). The metal units are constructed from sections of various lengths cut from the standard bars, utilizing leftovers from the previous days. Every day the manager of the workshop must figure out how to cut the bars so that the minimum number of standard bars will be used to meet the various length requirements (or minimum trim loss). In addition, he wants to utilize leftovers from previous days and would like the maximum quantity of today's leftovers to be accumulated in the minimum number of bars (for simplicity let us say the last bar(s)). The leftover(s) will then be of a sufficient length to be utilized at a later date. Consequently, there are two objectives: the first, which is the most important, is to minimize the trim loss, that is, to find the minimal number of metal bars required. Then, given the minimal number of standard bars, we want to maximize the amount of leftovers in the last bar(s). This problem is slightly different from the traditional cutting stock problem, where there is only one objective: to minimize the trim loss which is the dominant objective, in our case. Golden' in his review lists four main approaches: column generation, zero one programming, combinatorial heuristics, and subgradient optimization. In his final evaluation of the algorithms, he concludes that 'computational efficiency, objective value accuracy and code availability with respect to all the algorithms considered must be examined before any definitive conclusions are reached.'