具時間週期性的連續隨機需求之一維剩餘物料裁切問題之研究

A Study on Solving One Dimensional Residual Cutting Stock Problem with Periodic-time and Consecutive Stochastic Orders

徐家賢(Chia-Hsien Hsu)

指導教授 ： 周信宏

長榮大學/資訊暨工程學院/資訊管理研究所/碩士(2010年)

https://doi.org/10.6833/CJCU.2010.00016

摘要

本論文中，我們考慮「具時間週期性的連續隨機需求之一維剩餘物料裁切問題」。物料裁切視為工廠例行的作業，訂單以連續週期（每日、每週或每月）的方式產生，裁切計畫除了要能滿足訂單需求外，還要達到公司降低廢料和成本等目標。在本問題模型中，未來訂單的確切需求未知，裁切過後部分使用且有再利用價值的原料，稱為不標準原料，將被儲存起來供以後需求使用。問題目標在於減少廢料和成本。部分使用的原料將依其長度是否超過門檻值決定是否視為廢料或不標準原料。在本研究中，我們提出一個基因演算經驗法則演算法來預估能獲得最少花費的最佳門檻值。

關鍵字

最佳化問題 ； 物料裁切問題 ； 廢料 ； 基因演算法 ； 一維剩餘物料裁切問題 ； 連續隨機需求

並列摘要

In this thesis, we consider One Dimensional Residual Cutting Stock Problem with Periodic-time and Consecutive Stochastic Orders. Stock cutting is treated as a routing process in a factory in which orders in consecutive time periods (daily, weekly or monthly) need to be fulfilled while obtaining certain company goals such as minimal trim loss, minimal costs, etc. In this model, exact demands for future orders are not available in advance. The partly utilized and useful stock lengths left after fulfilling current order, called non-standard materials, are stored and used later. The goal is the reduction of trim loss and costs over a broader time period. To sort out a partly utilized stock length as a trim loss is decided by a threshold value. It means that if a partly utilized stock length is shorter than the threshold value, it will be treated as trim loss; otherwise it will be stored as a non-standard material. In this research, we propose a heuristic genetic algorithm to estimate the best threshold value which derives minimal cost.

並列關鍵字

Optimization Problem ； Cutting Stock Problem ； Trim Loss ； Genetic Algorithm ； One Dimensional Residual Cutting Stock Problem ； Consecutive Stochastic Orders

參考文獻

[1] G. Belov and G. Scheithauer, "A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths," European Journal of Operational Research, vol. 141, pp. 274-294, 2002.

[2] C.-L. S. Chen, S. M. Hart, and W. M. Tham, "A simulated annealing heuristic for the one-dimensional cutting stock problem," European Journal of Operational Research, vol. 93, pp. 522-535, 1996.

[3] M. Christopher, "Logistics and Supply Chain Management: Strategies for Reducing Cost and Improving Service(Second Edition) " in International Journal of Logistics Research and Applications. vol. 2 London: Taylor & Francis, 1999, pp. 103 - 104.

[4] P. C. Chu and J. E. Beasley, "A Genetic Algorithm for the Multidimensional Knapsack Problem," Journal of Heuristics, vol. 4, pp. 63-86, 1998.

[5] E. G. David, Genetic Algorithms in Search, Optimization and Machine Learning: Addison-Wesley Longman Publishing Company, 1989.