次經驗法則與固定工作順序條件下之重置問題

Abstract

具有固定工作順序之雙機組重置問題為：有兩個工作群分別被指定到兩台機組上，各自有其執行的順序。兩台機組共用相同的資源；當執行每個工作時會消耗資源，每個工作結束後則會返還資源。如何在滿足資源限制的前提下，達成總延遲時間(total tardiness)最小化是本篇論文探討的主題。為確保能讓所有工作順利執行，利用composite job的概念，計算出所需之最小資源量。我們提出一種解答的編碼方式，並將其運用於本論文所設計之基因演算法(genetic algorithm, GA)與禁忌搜尋法(tabu search, TS)。此外，本論文亦討論擾動(perturbation)機制在TS中對於求解過程與解答品質之影響。實驗程式採用兩種停止條件，其一是固定之總運算次數，其二是當連續數次未改善現行最佳解時結束。實驗結果顯示，禁忌演算法能在比較短的時間內得到解答，所得之目標值在大多時候也比基因演算法來得優異；惟隨著工作數目增加，由禁忌演算法得到的目標值變異程度也增大，基因演算法則呈現相對穩定。

The relocation problem subject to fixed sequences on two dedicated machines is that two sets of jobs are dispatched to two parallel dedicated machines, and each machine processes its jobs abiding by the given job orders. Minimizing the total tardiness under the resource constraint is the problem of concern. To guarantee that all jobs can be processed, we adopt the concept of composite jobs to evaluate the minimum resource level required. We propose an encoding method to represent the solutions. The encoding method is deployed in the genetic algorithm (GA) and tabu search (TS) designed in this study. The effects of perturbation in tabu search are also discussed. There are two stopping criteria in our implementations. One is constant frequency of computation, and the other is to terminate the program while the current best solution is not improved any more within a fixed number of iterations in a row. According to the results of numerical experiments, tabu search takes less time than genetic algorithm, and the quality of solutions obtained by tabu search are better in most test cases. However, the solutions reported by genetic algorithms exhibit a better central tendency when the number of jobs increases.