caa a22 4500 445838604 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s10951-010-0164-2 doi (NATIONALLICENCE)springer-10.1007/s10951-010-0164-2 On the one-dimensional stock cutting problem in the paper tube industry [Elektronische Daten] [Kazuki Matsumoto, Shunji Umetani, Hiroshi Nagamochi] The one-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems which arises in many industrial applications. Although the primary objective of 1D-CSP is to minimize the total length of used stock rolls, the efficiency of cutting processes has become more important in recent years. The crucial bottleneck of the cutting process often occurs at handling operations in semiautomated manufacturers such as those in the paper tube industry. To reduce interruptions and errors at handling operations in the paper tube industry, we consider a variant of 1D-CSP that minimizes the total length of used stock rolls while constraining (C1) the number of setups of each stock roll type, (C2) the combination of piece lengths occurring in open stacks simultaneously, and (C3) the number of open stacks. For this problem, we propose a generalization of the cutting pattern called the "cutting group,” which is a sequence of cutting patterns that satisfies the given upper bounds of setups of each stock roll type and open stacks. To generate good cutting groups, we decompose the 1D-CSP into a number of auxiliary bin packing problems. We develop a tabu search algorithm based on a shift neighborhood that solves the auxiliary bin packing problems by the first-fit decreasing heuristic algorithm. Experimental results show that our algorithm improves the quality of solutions compared to the existing algorithm used in a paper tube factory. Springer Science+Business Media, LLC, 2010 One-dimensional cutting stock problem nationallicence Paper tube industry nationallicence Open stack nationallicence Local search nationallicence Tabu search nationallicence Matsumoto Kazuki Graduate School of Informatics, Kyoto University, 606-8501, Kyoto, Japan aut Umetani Shunji Graduate School of Information Science and Technology, Osaka University, 565-0871, Suita, Japan aut Nagamochi Hiroshi Graduate School of Informatics, Kyoto University, 606-8501, Kyoto, Japan aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/3(2011-06-01), 281-290 1094-6136 14:3<281 2011 14 10951 https://doi.org/10.1007/s10951-010-0164-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-010-0164-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Matsumoto Kazuki Graduate School of Informatics, Kyoto University, 606-8501, Kyoto, Japan aut NATIONALLICENCE 700 1- Umetani Shunji Graduate School of Information Science and Technology, Osaka University, 565-0871, Suita, Japan aut NATIONALLICENCE 700 1- Nagamochi Hiroshi Graduate School of Informatics, Kyoto University, 606-8501, Kyoto, Japan aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/3(2011-06-01), 281-290 1094-6136 14:3<281 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer