多尺寸方形排列問題啓發式解法之硏究

摘要

切割/排列問題在工業界中出現頻繁，如紡織業、玻璃業、製鞋/皮革業、傢俱業及鋼鐵/造船業。業者莫不絞盡腦汁，發展出快速的解決之道。本研究以過去文獻中所提出之左下優先演算法(Bottom Up Left Justified，BL) 爲基礎，提出更精細之演算法，IBLA(Improved BL Algorithm) 。期望IBLA能在方形排列問題中迅速地找到“好的”或“近似最佳”的切割/排列方式以節省成本及提昇原物料使用率。本研究除了探討單一物料原片排列之問題外，亦延伸至多張物料原片排列問題之分析。最後，並與文獻中出現之最佳化數學模式及數個啓發式解法解題時效及解答品質上之表加以比較。

Abstract

This paper proposes an improved algorithm, IBLA, based on the BL(Bottom-Up Left-Justified) heuristic appeared in the literature for packing boxes with different sizes in a single material plate. This algorithm can be easily revised and hence applied to the cases involving multiple material plates. Examples adopted from literature were used to compare the proposed algorithm with the results from both exact model and other heuristics in terns of the solution quality. The corresponding running time information-was also provided.

關鍵詞:

• 方形排列問題
• 切割問題

Keywords:

• Rectangular Packing
• Cutting Problem