應用NFP演算法於船用大型材排版問題

APPLICATION OF NFP ALGORITHM TO NESTING PROBLEM IN SHIPBUILDING FOR LARGE SHAPES

所謂不規則切割問題是探討在一大片平面母材上如何盡量切割出許多不規則外形的型材，讓剩餘的完整母材越大越好，下次可再利用。因為船舶尺寸非常大，所以造船業所面對的排版型材，尺寸大而且外型多樣，使得這類問題較其他工業所面臨的問題更複雜。根據作者研究[18]發現，大型材比小型材更難排版。根據船廠實例發現，大型材長度長、外形凹，不易緊密排版。為此，本論文應用臨界多邊形演算法（no-fit polygon algorithm, NFP），設計開放式臨界多邊形（open nesting based on NFP, ONFP）排版法，專用於排版大型材。本論文利用三個船廠實例來測試，先用ONFP排版大型材，再用NEST排版軟體[2]排版小型材以填補空隙；整體而言，測試結果優於NEST軟體排版結果[18]。 Two-dimensional irregular cutting stock problem discusses how to arrange a material sheet to cut out as many shapes as possible. Ships are large products so that the needed shapes are very large. The author [18] has found that large shapes makes nesting problem difficult. On a material sheet, large shapes are better arranged at 90, 180, 270 degrees of rotation, while small shapes can be arranged at any rotation angle. Thus, in the paper, we develop a nesting method ONFP (open nesting based on NFP) based on no-fit polygon (NFP) algorithm. Large shapes are nested by ONFP while small shapes are used to fill in scattered spaces by well-developed software NEST. Three practical cases in shipbuilding are chosen as case studies. Apparently, the results are better than nesting all by NEST shown in [18].