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

Abstract

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

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.