可分離回收行程之最小化總和完工時間單機重置問題

Minimizing the total completion time in the relocation problem with separate resource recycling operations

蔡旻翰(Min-Han Tsai)

指導教授 ： 林妙聰

國立交通大學/管理學院/資訊管理研究所/碩士(2014年)

https://doi.org/10.6842/NCTU.2014.00289

摘要

本論文主要是在探討在重置問題中，當各個工作的回收資源行程與處理行程處於可分離的情況下，如何去求出單一機器下的最小化總和工作完工時間。重置問題最早是源於在波斯頓的社區重建計劃，亦可被視作為資源限制下的排程問題。在問題中，每一個工作均有回收資源行程與處理行程，工作在執行處理行程前需要從資源池消耗資源，而在執行資源回收行程後會還回資源至資源池，且所有的工作都共用同一個資源池，資源池內的資源種類為單一種資源。在本篇論文中，我們利用二元變數的整數規劃針對此問題形成數學敘述式，以作為萬用演算法的實驗數據之比較對象。同時，我們也利用改善過的禁忌搜尋法作為本論文主要實驗的方法，並提出參數設定、與最佳解的距離，以及起始解的改善程度等實驗結果比較。

關鍵字

重置問題 ； 資源限制下的排程問題 ； 可分離回收行程 ； 整數規劃 ； 禁忌搜尋法

並列摘要

This thesis studies the minimization of total completion time in the relocation problem with separable recycling operations (RPRO) on a single machine. The relocation problem, based on a public housing project in Boston, is a generalized resource-constrained scheduling problem in which each job has processing and recycling operations, then each operation requires an associated execution time. Resource pool will reduce the resource level to perform processing operation at the beginning and finally obtain the resource level from performing recycling operations. In this thesis, we give a formal mathematical formulation through two binary integer programmings and provide computational results with tabu search.

並列關鍵字

Relocation Problem ； Resource-constrained Scheduling ； Separate Recycling Operation ； Integer Progarmming ； Tabu Search

參考文獻

[1] J. Błażewicz. Scheduling under Resource Constraints: Deterministic Models,

volume 7. JC Baltzer, 1986.

[3] E. Burke and M. Pinedo. Journal of Scheduling (2013). Journal of Scheduling,

production and consumption of resources: A list-scheduling based algorithm.

Discrete Applied Mathematics, 157(17):3631–3642, 2009.