重置問題之研究

Abstract

重置問題是一個非常實際的排程問題，許多即將動工的房屋改建計劃都必須考慮到這 個問題。它尋求一個排程，能夠保證所有參與計劃的居民在計劃進行過程中都有地方 可住，而且這些居處不是由計劃負責單位臨時提供，就是從新建房屋中撥出，除此之 外，由計劃負責單位臨時提供的住所必須在計劃完成時全數收回也是一個得要考慮的 因素，因此，如何尋找一個滿足上述限制的排程，同時又只需提供最少的臨時住所， 便成為計劃負責單位所必須面對的課題，這也就是所謂的--重置問題。 重置問題非常複雜，致使計劃負責單位也無法迅速地在多項式時間(polynomial time ) 內找到一組最佳的排程，但值得慶幸的是，有些重置問題的子問題欲能夠很快的找 到解答，而且這些子問題在現實情況中都會遭遇到，因此我們投注很多的心力，以限 制條件的形態為基準做分類，仔細地剖析重置問題的複雜程度。我們對於某些能夠在 多項式時間內解答的子問題提出了詳細的解法，而且證明其餘的情況有大部份是屬於 NP-complete。 在考慮完基本的重置問題後，我們提出了兩個重置問題的泛化問題(generalization problem)，一個是依其建構的房屋數多寡做為衡量的依據，另一個是考慮每棟房屋都 有自己的最晚重建期限，同樣地，我們以討論重置問題的方式來討論這兩個泛化問題 。最後我們提出一些其他的泛化情況，做為未來研究的參考。