IEEE Trans Cybern. 2022 Sep;52(9):8603-8616. doi: 10.1109/TCYB.2021.3062799. Epub 2022 Aug 18.
Resource constraint job scheduling is an important combinatorial optimization problem with many practical applications. This problem aims at determining a schedule for executing jobs on machines satisfying several constraints (e.g., precedence and resource constraints) given a shared central resource while minimizing the tardiness of the jobs. Due to the complexity of the problem, several exact, heuristic, and hybrid methods have been attempted. Despite their success, scalability is still a major issue of the existing methods. In this study, we develop a new genetic programming algorithm for resource constraint job scheduling to overcome or alleviate the scalability issue. The goal of the proposed algorithm is to evolve effective and efficient multipass heuristics by a surrogate-assisted learning mechanism and self-competitive genetic operations. The experiments show that the evolved multipass heuristics are very effective when tested with a large dataset. Moreover, the algorithm scales very well as excellent solutions are found for even the largest problem instances, outperforming existing metaheuristic and hybrid methods.
资源约束作业调度是一个具有许多实际应用的重要组合优化问题。该问题旨在在满足几个约束条件（例如，优先级和资源约束）的情况下，为机器上的作业制定一个调度计划，同时最小化作业的延迟。由于问题的复杂性，已经尝试了几种精确、启发式和混合方法。尽管它们取得了成功，但可扩展性仍然是现有方法的一个主要问题。在这项研究中，我们开发了一种新的遗传编程算法，用于资源约束作业调度，以克服或缓解可扩展性问题。所提出算法的目标是通过代理辅助学习机制和自竞争遗传操作来进化有效的多遍启发式算法。实验表明，所提出的多遍启发式算法在处理大型数据集时非常有效。此外，该算法的扩展性非常好，即使是对于最大的问题实例也能找到出色的解决方案，优于现有的元启发式和混合方法。
