以圖對為基礎之啟發式演算法，探討實際設施規劃問題 ; Exploring practical facility layout planning with a graph pair-based heuristic

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Electronic Thesis & Dissertation > Item 987654321/44010

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/44010

Title:	以圖對為基礎之啟發式演算法，探討實際設施規劃問題;Exploring practical facility layout planning with a graph pair-based heuristic
Authors:	林義彬;Yi-bin Lin
Contributors:	工業管理研究所
Keywords:	圖對;設施規劃系統;混合整數規劃;模擬退火演算法;設施規劃問題;facility layout system;mix integer programming;simulated annealing algorithm;facility layout problems;graph-pairs
Date:	2010-07-12
Issue Date:	2010-12-08 14:45:52 (UTC+8)
Publisher:	國立中央大學
Abstract:	自Koopmans與Beckmann提出設施規劃問題已五十多年。在業界以及學術界均受到重視：在業界，有效率的物料搬運及設施規劃，可降低企業10%至30%的總生產成本，由此可知，設施規劃對於生產活動之重要性可見一般；在學術界，設施規劃問題求解困難，因此，許多在作業研究及管理科學領域的研究人員對此問題進行廣泛的探討。設施規劃為NP-complete問題，許多學者已發展相關啟發式演算法協助求解，例如，模擬退火、基因、螞蟻等。本研究發展模擬退火演算法來求解靜態設施規劃問題，以Montreuil在1990年提出的模型為基礎，並以圖對來表示模型中的二元變數值，將其轉換為線性模型。先以初始的廠房佈置為起始解，經過模擬退火演算法的程序來獲得相對最佳解，即物流成本較小。在求解相對最佳解同時，本研究亦考慮設施規劃者需求；並針對使用者的需求，開發相關的功能來運用，其功能包含：改善目前廠房佈置。本研究亦提出兩種求解動態設施規劃問題之方法。最終目的為發展一套實用化的設施規劃系統雛型以方便設施規劃人員使用。Since Koopmans and Beckmann proposed facility layout planning problem has been 50 years. It has been considered very important in both academia and industry. In the industry, efficient material handling and facilities layout planning could reduce the total production cost from 10 to 30 percent. Therefore, the facilities layout planning for the production is very important; in academics, facing the solving difficulties of the facilities layout planning problem, many researchers in the field of operations research and management science have extensively discussed the issue. Facilities layout planning is a NP-complete problem. Many researchers have developed heuristic algorithms to help solving this problem. For example, simulated annealing algorithms, genetic algorithms, ants algorithms and so on. This study develops static simulated annealing algorithm to solve facilities layout planning. Based on the Montreuil’s model (1990), we will use graph-pair to represent the value of the binary variables, and convert it to the linear model. First, we use the original layout planning to be the initial solution, and via simulated annealing procedures to obtain the better solution, that is, less flow costs. With solving the better solution, this study also considers the demand for facility layout planners, focuses on the needs of users, and develops the corresponding functions. Its features include: improving the facility layout. This study also proposed two methods of solving the dynamic facility layout problem. Ultimately, the objective is to develop a practical prototype of the facility planning system.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	872	View/Open

社群 sharing

Loading...