A Multi-Level GA Search with Application to the Resource-Constrained Re-Entrant Flow Shop Scheduling Problem
A Multi-Level GA Search with Application to the Resource-Constrained Re-Entrant Flow Shop Scheduling Problem
复制标题
多级遗传算法搜索及其在资源受限可重入流水车间调度问题中的应用
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
C.K.M. Lee
中科院分区：
文献类型：
--
作者：
D. Lin;C.K.M. Lee
可重入调度是流水车间中一个重要的多约束搜索问题。在文献中，已经研究了从精确方法到元分析的许多方法。本文提出了一种遗传算法，将问题编码为多层染色体，以反映重入可能性和资源消耗的依赖关系。这种新的编码方式既保留了数据的完整信息，又保证了算法收敛到最优解。为了验证该方法的有效性，将其应用于资源受限的可重入流水车间调度问题。计算结果表明，在资源约束、可重入、遗传算法、多级编码等指标上，该算法优于模拟退火算法
Re-entrant scheduling is an important search problem with many constraints in the flow shop. In the literature, a number of approaches have been investigated from exact methods to meta-heuristics. This paper presents a genetic algorithm that encodes the problem as multi-level chromosomes to reflect the dependent relationship of the re-entrant possibility and resource consumption. The novel encoding way conserves the intact information of the data and fastens the convergence to the near optimal solutions. To test the effectiveness of the method, it has been applied to the resource-constrained re-entrant flow shop scheduling problem. Computational results show that the proposed GA performs better than the simulated annealing algorithm in the measure of the makespan Keywords—Resource-constrained, re-entrant, genetic algorithm (GA), multi-level encoding