标题: 重置問題之研究---考量資源限制推廣形式之排程
The Relocation Problem---Scheduling with Generalized Resource Constraints
作者: 林妙聰
Lin Bertrand Miao-T
國立交通大學資訊與財金管理學系
关键字: 排程理論;重置問題;資源限制;計算性複雜度;效能分析;Scheduling Theory;Relocation Problem;Resource Constraints;Computational Complexity;Performance Analysis
公开日期: 2007
摘要: 重置問題起源於波士頓的社區重建計畫,為作業研究應用在公共政策上的成功案例,此
問題一開始是為了解決社區重建時居民安置的問題。在此問題中,所有建築物要重建前,該建
物的所有居民必須先妥善安置,在建物重建完成之後,也會還回一些資源以供重建計畫使用,
與其他資源限制排程問題不同的是,重置問題中的工作歸還回來的資源數量不一定等同此工作
之前所獲取消耗的資源數量。本計畫中,所要探討的不只是居民是否能獲得安置,還有考量管
理指標之最佳化,包含最短總完工時間與加權完工時間的最小化。在計畫中,我們首先將建立
所考慮的問題的數學模式,證明計算性複雜度,亦即提供 NP-completeness 證明以及設計演算
法;此外,我們也將設計如分支界定與動態規劃等精確解演算法,並設計經驗法則以及近似規
劃,以實驗與數學分析兩種方式進行效能驗證。
The relocation problem was originated from a public housing project in Boston area. It is
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.
官方说明文件#: NSC96-2416-H009-012-MY2
URI: http://hdl.handle.net/11536/88939
https://www.grb.gov.tw/search/planDetail?id=1462803&docId=262104
显示于类别:Research Plans