臺灣博碩士論文加值系統

不規則(Irregular)物件之切割與排列(Cutting and Packing，C&P)問題是工業界裡常見的一個問題。諸如：製鞋/皮革業、紡織業、鋼鐵業、服裝製造業，...，等。此乃因各工業的物料成本雖不相同，但其物料成本卻均在總成本中佔相當大的比例。在競爭激烈的環境裡，企業想突破瓶頸、再創高峰，勢必要從提昇原物料的使用率、降低其浪費量著手。　　基於上述因素，本研究之主要目的乃在以科學化方法來演算出一最佳切割/排列方式。由於此類決定不規則物件之最佳切割/排列問題為一組合最佳化問題(Combinational Optimization Problem)，其本質類屬NP-Complete級，無法在合理時間內獲致最佳解。而且，目前對於此類問題，並無一確切的求解技術可以求取其最佳解。因此，本研究發展一改良式左下優先(BottomLeft，BL)啟發式(Heuristics)演算法則，藉以迅速求取此類問題之最佳或近似最佳解。 本研究以所發展之啟發式演算法求解此類問題，演算過程為先將單一及兩兩聚合之不規則物件進行最小方形包覆，然後將不規則物件轉成方形。由於考慮不規則物件之需求量不同，所以必須以一轉換需求量之數學模式，將不規則物件之個別需求量轉換成各個方形之需求量，直接以發展之改良式左下優先啟發式演算法則求解。冀望本研究所發展之演算模式，可提供工業界處理此類相關問題一快速之途徑，並達成節省營運成本之企業目標。

packing and cutting irregular objects are difficulties frequently faced by the industries, such as shoes making, textile, steel, clothing,and furniture, etc. As it is known, cutting down material cost would make enterprise more competitive. Many researchers hence devote on developing algorithms to solve this so called cutting and packing problem, in order to obtain a good (optimal or near optimal) pattern in an acceptable time. Due to its being NP hard-type problem, optimization approach can hardly solve a real sized problems. Heuristic approaches are hence favored by researchers and practitioners. A bottom-left based heuristic algorithm is proposed in this research to solve this sort of problem. During the bottom-left based heuristic algorithm, the minimum enclosure rectangles for each irregular object is first calculated. Grouping analysis is next performed. For those grouped objects having better utilization rate, minimum enclosure rectangle is then generated. The entire bottom-left based heuristic algorithm is proceeded by packing these minimum enclosure rectangles. A real example from shoe industry is used for the illustrative purpose.