| 摘要: | 多年期（動態）的廠房設施規劃問題（the dynamic facility layout problem, DFLP）是 1986 年由Rosenblatt 所提出的[R86]。DFLP 是單一時期廠房設施規劃問題（the facility layout problem, FLP）的延伸，其目標在於建置一整組的設施佈置（一個時期搭配一種佈置），並在所有需求與限制均被滿足的情況下將總成本(所有時期成本的加總) 盡量的壓低。DFLP 除了必須考慮部門之間的物料輸送成本之外，它另外還得考慮部門「重新配置」（relocation）的成本。這個成本是部門在下一個時期因座落位置的改變而必須的支出。很明顯的，物料輸送成本與部門重新配置的成本，兩者之間該如何來做取捨，考驗著吾人的智慧：將部門移至一個新的位置有可能會降低物料運送的成本，但其代價是必須付出部門重新配置的成本。並且，DFLP 尚須面對的是，部門面積可能會因時期不同而有所改變（增加或是減少），新的部門將在某些時期誕生，或是舊的部門將逐漸的從廠區裡消失。這些變化均使DFLP 成為一個非常具有挑戰性的問題。 Montreuil 是第一個提出（單一時期）FLP 數學模型的學者[Mo90]。他的模型是一個混合整數模型（mixed-integer program, MIP），其整數變數的使用，是為了避免一個部門的面積與另外一個部門的面積產生相互重疊。Montreuil 的MIP 代表了「理論上」的最佳解，因為在現實的情況中，要求得這些混合整數模型的最佳解是極為困難的。時至今日，吾人所能求得最佳解的最大MIP，也不過僅有11、12 個部門而已[MCS07]。因此，數學規劃對DFLP 的實用程度是極為有限的。事實上，目前DFLP 相關的論文，大多數是針對其下一個特殊的情況所做的研究：亦即所有部門皆有相同的佔地面積（因此在求解過程當中可以將之忽略），以及所有部門可能座落的位置皆為已知。此一特殊情形即為動態版的二重指派問題（dynamic quadratic assignment problem, DQAP）。目前，各種不同的啟發式演算法已被運用來求解DQAP，例如基因演算法[BC00, BCCL03]、退火模擬演算法[BG01, MSK06]、螞蟻演算法[MS06, BDS06]等。我們在此欲提出一個運用數學規劃以及啟發式演算法來求解一般性DFLP 的國科會計畫。這個計畫將以目前我們正在進行的計畫（專案編號NSC 97-2218-E-008-015）為基礎，亦即利用圖形來表示部門之間的相對位置，藉以解除MIP 的整數解限制。（註：相對位置即部門於廠房內位置上的相對關係）。利用這個方法，我們便可將FLP 與DFLP 以線性模型來求解，而不需要借助運算極為龐大而耗時的MIP。我們預期將運用退火模擬、螞蟻等演算法來驅動我們的求解過程。我們也預期，有可能會需要調整上述演算法的邏輯及參數，以便得到良好的演算結果。我們這個計畫預計將伴隨完成另一項成果，亦即一個可用來做動態廠房設施規劃的商用電腦系統原型版（commercial prototype）。這個系統目前正在進行函式庫（library）的部份，完成之後，我們將隨即運用這個函式庫來求解單一時期的廠房設施規劃。本計畫若是申請獲准，我們將會把動態規劃的功能加諸於該系統。事實上，我們有一個長遠的構想：開發一個可做不同類型廠房設施規劃的電腦系統，而這個系統所仰賴的共用資源（方法和附程式），都可得自目前正在開發的函式庫。有關這個構想的詳細說明，敬請參考表C012-2，謝謝。The (single-period) facility layout problem (FLP) is a classic research topic which has been studied for several decades. Generally, the FLP is concerned with laying out a number of “departments”in a given area, with goal to minimize inter-department material handling costs. Usually, various requirements need to be considered and satisfied when solving the FLP, including department areas and shapes, aisle structures, departmental locations, and so on. The multi-period, or “dynamic,”facility layout problem (DFLP) was proposed by Rosenblatt in 1986 [R86]. It extends from its single-period counterpart in that the DFLP is concerned with creating a set of layouts, one for each period, such that the overall cost (summed across all the periods) is minimized while all the requirements are met. In addition to material handling costs incurred between departments, the DFLP needs to further consider the cost for department “relocation.”Such costs are incurred when departments change their location in the facility during the next period. Quite obviously, there is a tradeoff to be made between these two costs: moving departments to a new location may reduce the cost for material handling, it will incur relocation costs. Also, the (general) DFLP needs to face the situation where departments change their area (expansion or shrinkage) from one period to the next and some new departments are born in some period while others are phased out (disappear from the facility). All these make the DFLP a very challenging problem. Montreuil proposed the first math model for solving the single-period FLP with different department areas [Mo90]. His model is a mixed-integer program (MIP) in which integer variables are used to prevent departments from overlapping their floor space with each other. This MIP represents the theoretically optimal solution. In reality, however, it (and others of similar kind) is very hard to be solved to optimality—today only problems with up to 11 or 12 departments can be solved optimally [MCS07]. This makes math programming little practical use in the multiple-period situation. In fact, most of the DFLP papers seen today are research results for a special case of the problem: all departments have the same floor space (thus can be ignored) and all potential department locations are known a priori. This special case is the dynamic version of the classic quadratic assignment problem (DQAP). Various heuristic algorithms have been proposed for solving the DQAP, including genetic algorithms [BC00, BCCL03], simulated annealing [BG01, MSK06], and ant colony optimization algorithms [MS06, BDS06]. We propose a heuristic approach for applying math programming to solve the general DFLP in our view. This algorithm will be developed based on the research being conducted and supported by the NSC (project number NSC 97-2218-E-008-015), that is, using a graph representation of the departmental relative positions (i.e., how departments are located relative to each other in the facility) to relax the integer constraints of the MIP. By doing so, we can solve the math models for the FLP as well as the DFLP as linear programs (LP), rather than the computationally difficult MIPs. We expect to utilize such meta-heuristics as simulated annealing and ant colony optimization algorithms to drive our heuristic search. We may need to derive a modified version of these meta-heuristics to deliver a satisfactory performance in our DFLP setting. 研究期間 : 9808 ~ 9907 |
