涵蓋問題與其應用在工件加工體積選擇問題之探討

The Investigation of Set Covering Problems and Its Application in the Selection of Machinable Volumes

林聰穎(Lin Tsong-Yiing)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/碩士(1992年)

摘要

在一般日常生活周遭的許多問題，如航空公司飛行航線的安排問題、以及
消防站的設置數量與坐落問題等，皆可轉換為涵蓋問題的模式而獲得解決
。近年來已經有許多學者致力於涵蓋問題的求解，對於密度較稀疏的涵蓋
問題可求得其最佳解，但是面對密度較高的大型涵蓋問題，則無法在可容
許的時間範圍之內求得其最佳解。在無法求得最佳解的情況之下，只好退
而求其次，用啟發式的方法來求解該問題。一個良好的啟發式方法，其所
求得的可行解會相當接近最佳解。本研究的重點之一是：考慮密度較高的
涵蓋問題具有那些特性，尋求一個良好的啟發式方法，以便有效率的解決
密度較高的大型涵蓋問題。另一項研究重點是：將涵蓋問題應用到工件加
工體積選擇問題上面，探討在製程規劃過程當中，工件應切除體積的加工
方法應該如何選取。除了加工成本因素之外，本研究同時考慮加工時間因
素，配何基因演算法的技術來求解其最低加工成本與最短加工時間。

關鍵字

涵蓋問題 ； 工件加工體積選擇問題 ； 基因演算法

並列摘要

There are many problems that can be transferred into set
coveirng problems (SCP's), such as the airline crew scheduling,
and the location of emergency service facilities. Earlier
researches have focused on solving the SCP's and optimal
solutions of the SCP's with sparse densities have been found.
However, the optimal solutions of the large-scale, high-density
SCP's are still not available during the admittable solving
time. The feasible solution found by a heuristic method with
good performance measure is needed to be further developed. The
efforts exerted in this research comprised the following: 1).
Examine the properties of the high-density SCP's and find a
good approximation method to solve the large- scale, high-
density SCP's efficiently and effictively. 2). Apply the SCP's
to the selection of machinable volumes of a part during the
process planning. In addition to the factor of machining cost,
we consider another important factor, the machining time. The
technique of genetic algorithms is employed to solve the bi-
criteria problem: minimizing the total machining cost and the
total machining time.

並列關鍵字

set covering problems ； the selection of machinable volumes ； genetic algorithm