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

Abstract

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

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.