カッティングストック問題
読み方：かってぃんぐすとっくもんだい
【英】：cutting-stock problem
【英】：cutting-stock problem
板取り問題ともいう。長さが35, 60, 100, 150の板には, それぞれ500, 700, 450, 200枚以上の需要があり, これらを長さ1000の板から取り出したい. このとき, 使用する長さ1000の板の総枚数が最小になるように, どのような取り出しパターンで, 各何枚必要かを求めるような問題. 取り出す板の種類が増えると, 取り出しパターンも爆発的に増加するため, 数理計画法的定式化の陽な記述は難しいが, 改訂単体法の応用である列生成法を用いることによって, 効率よく解かれている.
板取り問題
板取り問題
(cutting-stock problem から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/11/05 09:53 UTC 版)
オペレーションズ・リサーチにおける板取り問題（いたどりもんだい、英: cutting stock problem）、またはカッティングストック問題とは、定形の母材（ストック（stock）とも。例えばロール紙や板金）から廃材の量が最小になるように特定の大きさの製品群を切り出す問題である。産業上の応用から生じた数学的な最適化問題の1つであり、また計算複雑性理論においてはナップサック問題に還元されるNP困難問題の1つである。整数計画問題として定式化することができる。
- ^ Wäscher, G.; Haußner, H.; Schumann, H. An Improved Typology of Cutting and Packing Problems. European Journal of Operational Research Volume 183, Issue 3, 1109-1130
- ^ M.P. Johnson, C. Rennick & E. Zak (1997), Skiving addition to the cutting stock problem in the paper industry, SIAM Review, 472-483
- ^ Raffensperger, J. F. (2010). “The generalized assortment and best cutting stock length problems”. International Transactions in Operational Research 17: 35. doi:10.1111/j.1475-3995.2009.00724.x.
- ^ L. V. Kantorovich Mathematical methods of organizing and planning production. Leningrad State University. 1939
- ^ Kantorovich L. V. and Zalgaller V. A. . (1951). Calculation of Rational Cutting of Stock. Lenizdat, Leningrad
- ^ Gilmore P. C., R. E. Gomory (1961). A linear programming approach to the cutting-stock problem. Operations Research 9: 849-859
- ^ Gilmore P. C., R. E. Gomory (1963). A linear programming approach to the cutting-stock problem - Part II. Operations Research 11: 863-888
- ^ Goulimis C (1990). Optimal solutions for the cutting stock problem. European Journal of Operational Research 44: 197-208
- ^ de Carvalho V (1998). Exact solution of cutting stock problems using column generation and branch-and-bound. International Transactions in Operational Research 5: 35–44
- ^ S. Umetani, M. Yagiura, and T. Ibaraki (2003). One dimensional cutting stock problem to minimize the number of different patterns. European Journal of Operational Research 146, 388–402
- ^ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk and S. Naidoo (1996). Setup minimizing conditions in the trim loss problem. European Journal of Operational Research 95:631-640
- ^ C. McDiarmid (1999). Pattern Minimisation in Cutting Stock Problems. Discrete Applied Mathematics, 121-130
- ^ Maria Garcia de la Banda, P. J. Stuckey. Dynamic Programming to Minimize the Maximum Number of Open Stacks. INFORMS Journal on Computing, Vol. 19, No. 4, Fall 2007, 607-617.
[続きの解説]
「板取り問題」の続きの解説一覧
- 1 板取り問題とは
- 2 板取り問題の概要
- 3 ガラス製造において
- 4 参考文献
「cutting-stock problem」の例文・使い方・用例・文例
- cutting-stock problemのページへのリンク
