| 摘要: | 廠房設施規劃問題（The facility layout problem, FLP）是一個長久以來，一直被國內外學者持續探索的研究議題。大致說來，FLP 是將一群「部門」（departments）佈置在一個限定的廠區裡，目標為盡量的降低物料在各部門間運送所需支出的成本。我們在解FLP 的時候，經常得考慮各種需求或限制，比方說，部門的形狀（長方形或非長方形），部門間通道（aisle）的配置，某些特殊部門在廠區內位置的限制等。 Montreuil 是首位提出FLP 數學模型的學者[Mo90]。在他的模型裡面，廠區及所有部門的形狀都是長方形。他並且用0/1 變數來決定部門在廠區內的相對位置，以確保模型在求解後，部門與部門不會相互重疊（亦即，不會佔據相同的區塊）。Montreuil 所提出的是一個混合整數模型（mixed-integer program, MIP），在當時，他的模型能用一般電腦求出最佳解的，最多只能含有七個左右的部門。近年來，由於模型以及O.R.技術的改良，更多部門的FLP 已可求出最佳解。比方說，[SFM03]能解到九個部門，而[MCS07] 更推進到十一個部門（註：它們得到最佳解所需的時間皆為好幾個小時，其中一個問題甚至需要將近二十個小時）。然而，這離現實生活中我們所經常面對的問題大小（二、三十個部門），仍有一段相當大的差距。因此，要利用數學規劃來解現實生活中的FLP，我們仍需搭配啟發式演算法（heuristic algorithms）。FLP 的數學模型裡，最為關鍵的部份，莫過於決定部門在廠區內相對位置的那些變數。以Montreuil 的MIP 為例，一旦所有部門的相對位置被決定了，模型剩餘的部份就只是一個線性模型（linear program, LP），而線性模型要求得最佳解，比起MIP 是要容易的多了。我們的FLP 演算法，主要是利用directed graphs 來進行部門間相對位置的操控。更具體的說，圖形中的節點i 將對應到部門i，而圖形中的節線(i, j)將代表部門i 和部門j 在廠區內的相對位置。我們將採用知名的最優化演算法，諸如退火模擬或是螞蟻演算法，來驅動我們演算法的求解過程。我們的目標是一個具有實用價值的FLP 演算法。當然，在發展過程中，我們將利用那些已知的最佳解，做為修訂我們演算法的依據。 ; The facility layout problem (FLP) is a well-known research topic which has received much attention for several decades. Generally speaking, the FLP is concerned with laying out a number of “departments”in a given area so as to minimize inter-departmental material handling costs. Various requirements or restrictions are considered when solving the FLP, which include, but are not limited to, departmental shapes, aisle structures, departmental locations, and so on. Montreuil proposed the first mathematical model for the FLP [Mo90]. In his approach, departments and the facility are formulated as a rectangle (squares included). In order to prevent departments from overlapping with each other, that is, occupying the same floor space in the facility, 0/1 binary variables are introduced. Therefore, Montreuil’s model is a mixed-integer program (MIP) and could only be solved to optimality for problems with 6 or 7 departments when he proposed it. In recent years, enhanced models with innovative O.R. techniques have been developed, allowing larger problems to be solved. For example, [SFM03] and [MCS07] can solve nine- and eleven-department problems to optimality, respectively (after hours of computer runtime). Still, the practical use of these approaches is limited. The above suggests that some heuristic approach is required to extend the use of math programming to the real-world FLP where the number of departments often exceeds 20. To develop such a heuristic algorithm, observe that when solving a facility layout math model, the most crucial part probably is the determination of the “relative position”for any two departments in the facility, e.g., department i is east of department j, or department j is north of department i. In Montreuil’s MIP model, if all such departmental relative positions are known, the model will become a linear program (LP) and can be solved much faster. Therefore, we are motivated to develop a heuristic algorithm for solving the FLP using math programming, which was started in [Mo90]. We intend to use “directed graphs”or digraphs to represent departmental relative positions in our approach, with each vertex i corresponding to a particular department i and each edge (i, j) representing the relative position for departments i and j. Furthermore, algorithms such as simulated annealing or ant colony optimization (ACO) [KC06] are candidate algorithms to drive the process of finding a good, heuristic solution. Our goal is to develop an algorithm which is capable of identifying high-quality layouts consistently for the real-world FLP, and we will be using optimal solutions available in the literature as reference to guide our algorithm development. ; 研究期間 9711 ~ 9810 |
