Centre for Data Analytics and Cognition, La Trobe University, Australia
Evolutionary Computation Research Group, Victoria University of Wellington, New Zealand
Evol Comput. 2019 Fall;27(3):467-496. doi: 10.1162/evco_a_00230. Epub 2018 Jun 4.
Designing effective dispatching rules for production systems is a difficult and time-consuming task if it is done manually. In the last decade, the growth of computing power, advanced machine learning, and optimisation techniques has made the automated design of dispatching rules possible and automatically discovered rules are competitive or outperform existing rules developed by researchers. Genetic programming is one of the most popular approaches to discovering dispatching rules in the literature, especially for complex production systems. However, the large heuristic search space may restrict genetic programming from finding near optimal dispatching rules. This article develops a new hybrid genetic programming algorithm for dynamic job shop scheduling based on a new representation, a new local search heuristic, and efficient fitness evaluators. Experiments show that the new method is effective regarding the quality of evolved rules. Moreover, evolved rules are also significantly smaller and contain more relevant attributes.
如果手动设计生产系统的有效调度规则，这将是一项困难且耗时的任务。在过去的十年中，计算能力的增长、先进的机器学习和优化技术的发展使得调度规则的自动化设计成为可能，并且自动发现的规则具有竞争力或优于研究人员开发的现有规则。遗传编程是文献中发现调度规则的最流行方法之一，特别是对于复杂的生产系统。然而，庞大的启发式搜索空间可能会限制遗传编程找到接近最优的调度规则。本文提出了一种新的混合遗传编程算法，用于基于新的表示形式、新的局部搜索启发式和高效的适应度评估器的动态作业车间调度。实验表明，新方法在进化规则的质量方面是有效的。此外，进化规则也明显更小，并且包含更多相关属性。
