考慮起始時間之重置計畫: 完工時間之最小化

Abstract

在生產排程問題中，與重置計畫相關之問題是最近一項被廣泛討論的題目。在這類型的題目中，必須考量每個工作所需要的資源量以及所將釋放的資源量，進而去找尋一組最佳化的可行解。本論文探討的是重置計畫中並結合了起始時間的題目，每個工作都有各自的起始時間，且起始時間的加入會讓問題難度提升許多。儘管在這類型的題目中，許多不同特殊狀況下都是NP-hard但也有一些情況是可以在有效的時間內可解的。在論文中，我們提出了整數規劃的模型以及一些相關演算法的計算。除此之外，也討論了複雜度在一些不同特殊條件的問題，其中也包括了相關的證明。除了理論研究的部分，另外在計算方面也提出了相關的最佳化演算法，設計一種經驗法則計算方式，拿來當作禁忌搜尋法的初始解，並將之與整數規劃之最佳解做比較。最終實驗結果顯示論文中所提出之方法具有不錯的效果。

The relocation problems have received considerable research attention in recent years. This study considers the relocation problem with release dates constraints. A feasible schedule must satisfy the resource constraints and release date constraints simultaneously. The introduction of release dates makes the problem NP-hard in its general form. In this thesis, we present an integer programming model to formulate the problem and propose several solution methods. We indicate whether some different special cases of the problem can be solved in polynomial time or not. If it can, efficient solution algorithms are proposed. On the other hand, if it cannot, proofs are provided to show the NP-hardness. Moreover, tabu search is adopted for handing this hard problem. In order to improve the performance of tabu search, heuristics algorithms are designed to produce initial solutions. We conduct a series of computational experiments to evaluate the effectiveness and efficiency of all of the proposed algorithms.