An Exact Algorithm for Large-Scale Unconstrained Three Staged Cutting Problems with Same-Size Block Requirement

Jun Ji; Yi-Ping Lu; Jian-Zhong Cha; Jia-Qing Yu; Yao-Dong Cui

doi:10.6186/IJIMS.2012.23.1.4

山西大学，您好！

感谢采购，人社期刊库｜人社论文库，期间：2025/01/01~2025/12/31

感谢试用，科学期刊库｜科学论文库，期间：2024/10/20~2025/01/20

浏览高级检索

关闭
检索检索高级检索出版物检索
浏览期刊主题浏览核心期刊浏览期刊拼音浏览

关闭

查询符号(半角)	查询符号意义说明
空格	表示为「AND」两个查询词之交集
双引号 ( " " )	片语以双引号标示开始及结束，而且只寻找出现顺序相同的字词，例： " image process "
?	表示一个字母切截，输入两个?表两个字母，依此类推，例：输入「Appl?」，查得结果应为appl e , appl y … ( 常用于英文字查询 )
*	表示不限字母切截，由0~n. 例：输入「appl*」，查得结果应为appl e , appl es , appl y , appl ied , appl ication … ( 常用于英文字查询 )
AND、OR、NOT	布尔逻辑组合关键字，用来扩大或缩小查询范围的技巧。 (1) AND ：缩小查询范围 (2) OR ：扩大查询范围(3) NOT：排除不相关的范围

DOI 是数位物件识别码（ D igital O bject I dentifier ）的简称，
为物件在网路上的唯一识别码，可用于永久连结并引用目标物件。

使用DOI作为永久连结

每个DOI号前面加上「 http://dx.doi.org/ 」便成为永久网址。
如以DOI号为 10.5297/ser.1201.002 的文献为例，此文献的永久连结便是： http://dx.doi.org/ 10.5297/ser.1201.002 。
日后不论出版单位如何更动此文献位置，永久连结所指向的位置皆会即时更新，不再错失重要的研究。

引用含有DOI的文献

有DOI的文献在引用时皆应同时引用DOI。若使用APA、Chicago以外未规范DOI的引用格式，可引用DOI永久连结。

DOI可强化引用精确性、增强学术圈连结，并给予使用者跨平台的良好使用经验，目前在全世界已有超过五千万个对象申请DOI。如想对DOI的使用与概念有进一步了解，请参考（）。

ACI:

数据来源：Academic Citation Index，简称ACI

台湾最大的引用文献资料库，目前收录台湾与港澳地区所出版的人文学、社会学领域学术期刊之书目资料与参考文献，总期刊量超过690种，每年定期公布收录期刊的影响指数(Impact Factor)等指标给大众，并提供专家学者与学术单位实用的计量与分析功能。

五年影响指数（5-Year Impact Factor）：某一期刊前五年所出版的文章在当年度的平均被引用次数。

公式：（前五年发表论文在统计年的被引用次数）÷（前五年论文产出论文总篇数）

例如：A期刊2017年之五年影响指数

(A期刊2012-2016年发表论文在2017年的被引总次数)/(A期刊2012-2016年发表的论文总数)

什么是预刊文章？

为提供读者最前线之学术资讯，于期刊文献获同意刊登后、纸本印制完成前，率先于网路线上发表之文章即为预刊文章。预刊文章尚未有卷期、页次及出版日期资讯，但可藉由DOI号识别。 DOI号是文献的数位身份证字号，不论预刊或正式出版皆不会改变，读者可点击DOI连结，或于DOI号前面加上「 http://dx.doi.org/ 」连结到文献目前最新版本。

如何引用预刊文章？

请使用预刊文章的线上发表日期及DOI号来引用该篇文献。

引用范例(视不同引文格式规范可能有所差异)：

作者姓名。文章篇名。期刊名称。 YYYY/MM/DD线上预先发表。

doi:DOI 号

来源数据

P59 - 78

基础与应用科学 > 资讯科学
社会科学 > 管理学

DOI： 10.6186/IJIMS

书目管理工具

相关连结

问题回报

全文下载

An Exact Algorithm for Large-Scale Unconstrained Three Staged Cutting Problems with Same-Size Block Requirement

Jun Ji ； Yi-Ping Lu ； Jian-Zhong Cha ； Jia-Qing Yu ； Yao-Dong Cui

International Journal of Information and Management Sciences ； 23:1 (2012 / 03 / 01) ， P59 - 78

英文 DOI： 10.6186/IJIMS.2012.23.1.4

Cutting problems ； dynamic programming ； knapsack problem ； same-size block

0 个人觉得这篇文章赞

摘要 │ 参考文献 (17) │ 被引用文献 (1) │ 国际计量

并列摘要〈TOP〉

This paper deals with the two-dimensional cutting problem, in which a set of small rectangular pieces are cut from a large rectangle for the purpose of maximizing the total value of the pieces included. The two-dimensional cutting problem is a very hard problem to solve, for which optimal algorithms exist but tackle large-scale problems inefficiently. Cutting patterns usually not only come from real-world production demands, but also can simplify a problem into some sub-problems. The pattern algorithm for each sub-problem can be constituted with much higher running speed, and serve as approximate algorithms to the optimal algorithms. This paper proposes an exact algorithm for generating three staged same-size block cutting pattern. This algorithm uses knapsack approach combined with a dynamic programming recursion. The algorithm is compared with the well-known threestage algorithm and the T-shape homogenous block algorithm through large-scale instances. The experiment results illustrate that the material usage of this paper's algorithm is higher than above algorithms within reasonable computational time.

参考文献 ( 17 ) 〈TOP〉

Agrawal, P. K.(1993).Minimizing trim loss in cutting rectangular blanks of a single size form a rectangular sheet using orthogonal guillotine cuts.European Journal of Operational Re-search,64,410-42.
Alvarez-Valdés, R.,Rarajón, A.,Tamarit, J. M.(2002).A tabu search algorithm for large-scale guillotine (un)constrained two dimensional cutting problems.Computers & Operations Research,29,925-947.
Arslanov, M. Z.(2000).Continued fractions in optimal cutting of a rectangular sheet into equal small rectangles.European Journal of Operational Research,125,239-248.
Cintra, G. F.,Miyazawa, F.K.,Wakabayashi, Y.,Xavier, E.C.(2008).Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation.European Journal of Operational Research,191,61-85.
Cui, Y.(2004).Generating optimal T-shape cutting patterns for rectangular blanks.Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture,218,857-866.

被引用文献 ( 1 ) 〈TOP〉

Zhang, Wen-Zeng,Xing, Fei-FeiCui, Yao-Dong,Ji, Jun(2018).An Exact Rectangular Two-Segment Layout Algorithm with Optimal Same-Shape Strip Generation.International Journal of Information and Management Sciences,29(2),191-204.

国际计量

〈TOP〉

E-mail ：

文章公开取用时，将寄通知信至您填写的信箱地址