重置問題之研究---考量資源限制推廣形式之排程

Abstract

重置問題起源於波士頓的社區重建計畫，為作業研究應用在公共政策上的成功案例，此 問題一開始是為了解決社區重建時居民安置的問題。在此問題中，所有建築物要重建前，該建 物的所有居民必須先妥善安置，在建物重建完成之後，也會還回一些資源以供重建計畫使用， 與其他資源限制排程問題不同的是，重置問題中的工作歸還回來的資源數量不一定等同此工作 之前所獲取消耗的資源數量。本計畫中，所要探討的不只是居民是否能獲得安置，還有考量管 理指標之最佳化，包含最短總完工時間與加權完工時間的最小化。在計畫中，我們首先將建立 所考慮的問題的數學模式，證明計算性複雜度，亦即提供 NP-completeness 證明以及設計演算 法；此外，我們也將設計如分支界定與動態規劃等精確解演算法，並設計經驗法則以及近似規 劃，以實驗與數學分析兩種方式進行效能驗證。

The relocation problem was originated from a public housing project in Boston area. It is a successful application of operations research in public issues. All residents in a building should be settled before it was demolished. After construction, some resources (housing units) will be returned. The greatest difference between the relocation problem and other resource-constrained scheduling problems lies in the fact that the amount of resources acquired by a building does not have to be identical to that returned after its completion. In this project, we consider the feasibility of construction but also first minimizing the makespan, i.e. the completion time of all buildings, and second minimizing the weighted sum of total completion times. The uniqueness of our proposal stems from the processing times required by recycling the resources before they can be used. For the studied problems, we shall first develop insight observations on potential optimality properties and settle computational complexities. Solution algorithms will be designed and computationally evaluated. Moreover, we would conduct mathematical a study on performance ratio analysis using techniques PTAS or FPTAS.