二次規劃法配合全域策略於多種裁切庫存問題之研究

Sequential Quadratic Programming Method with Global Strategy for Multiple Types of Multi-polygon Cutting-stock Problem

余明達

指導教授 ： 洪景華 ； 林聰穎

國立交通大學/工學院/機械工程系所/博士(2009年)

https://doi.org/10.6842/NCTU.2009.00522

摘要

裁切庫存問題是一種有限制條件的最佳化問題，它在討論如何將所欲加工零件的外型排列在材料中，能提高材料的利用率，且沒有重疊。
裁切庫存問題存在於許多的工業中，例如紡織業、成衣業、紙張製造業、造船業及板金業。裁切庫存問題可分為許多類型。例如：方形物件的排列、不規則物件的排列、方形材料的使用、不規則材料的使用、單一材料與多種材料等。本研究將重點集中在不規則物件的排列上，將裁切庫存問題規劃成限制最佳化問題的形式，並利用求解限制最佳化問題常用的序列二次規劃法配合本研究提出的全域搜尋策略，來找到良好的解。並利用虛擬物件的概念將不規則材料問題與多材料問題簡化成單一方型材料問題，使得所提出的搜尋策略能廣泛地應用到多種不同的問題。此外，本研究還提出一種適用於序列二次規劃法的物件重疊的指標，與一簡化的模型以達到簡化限制條件計算的目的。

關鍵字

裁切庫存問題 ； 最佳化

並列摘要

The cutting-stock problem, which considers how to arrange the component profiles on the material without overlaps, can increase the utility rate of the stock, and is thus a standard constrained optimization problem.
The cutting-stock problem is relevant in many industries, such as textile, garment, paper, ship building, and sheet metal industries. The cutting-stock problem can be classified in many types, such as: rectangle object problem, irregular object problem, rectangle stock problem, irregular stock problem, single-stock problem, and multi-stock problem. This study focuses on the irregular object problem, and formulates it as a standard constrained optimization problem. The Sequential Quadratic Programming method, which is famous for solving a constrained optimization problem, is used with the global strategies, which are proposed in this study, for obtaining a good solution. This study also proposes a virtual object strategy to simplify the irregular stock problem and the multi-stock problem as a single rectangular stock problem. Additionally, this study proposes an overlap index, which is suitable for the Sequential Quadratic Programming method, and proposes a simplification model for simplifying the calculation of constraints.

並列關鍵字

Cutting-stock problem ； Optimization

參考文獻

Arora, J.S., (2004). Introduction to Optimum Design, Second edition. Elsevier/Academic Press, London.

Babu, A.R., and Babu, N.R., (2001). A genetic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms, Computer-Aided Design, 22, 879-891.

Bennell, J.A., and Dowsland, K.A., (2001). Hybridising tabu search with optimisation techniques for irregular stock cutting, Management Science, 47, 8, 1160-1172.

Bouganis, A., and Shanahan, M., (2007). A vision-based intelligent system for packing 2-D irregular shapes, IEEE Transactions on Automation Science and Engineering, 4, 382-394.

Burke, E., Hellier, R., Kendall, G., and Whitwell, G., (2006). A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem, Operations Research, 54, 587-601.