标题: 次经验法则与固定工作顺序条件下之重置问题
Meta-heuristics for Solving Relocation Scheduling Subject to Fixed Sequences
作者: 江秉陽
Chiang, Ping-Yang
林妙聰
Lin, Miao-Tsung
資訊管理研究所
关键字: 重置问题;固定工作顺序之双机组;资源限制;总延迟时间;基因演算法;禁忌搜寻法;relocation problem;fixed sequences on two machines;resource constraint;total tardiness;genetic algorithm;tabu search
公开日期: 2011
摘要: 具有固定工作顺序之双机组重置问题为:有两个工作群分别被指定到两台机组上,各自有其执行的顺序。两台机组共用相同的资源;当执行每个工作时会消耗资源,每个工作结束后则会返还资源。如何在满足资源限制的前提下,达成总延迟时间(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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079934520
http://hdl.handle.net/11536/50144
显示于类别:Thesis