Resource constrained job scheduling is a hard combinatorial optimisation
problem that originates in the mining industry. Off-the-shelf solvers cannot
solve this problem satisfactorily in reasonable timeframes, while other
solution methods such as many evolutionary computation methods and
matheuristics cannot guarantee optimality and require low-level customisation
and specialised heuristics to be effective. This paper addresses this gap by
proposing a genetic programming algorithm to discover efficient search
strategies of constraint programming for resource-constrained job scheduling.
In the proposed algorithm, evolved programs represent variable selectors to be
used in the search process of constraint programming, and their fitness is
determined by the quality of solutions obtained for training instances. The
novelties of this algorithm are (1) a new representation of variable selectors,
(2) a new fitness evaluation scheme, and (3) a pre-selection mechanism. Tests
with a large set of random and benchmark instances, the evolved variable
selectors can significantly improve the efficiency of constraining programming.
Compared to highly customised metaheuristics and hybrid algorithms, evolved
variable selectors can help constraint programming identify quality solutions
faster and proving optimality is possible if sufficiently large run-times are
allowed. The evolved variable selectors are especially helpful when solving
instances with large numbers of machines.

提出了一种遗传规划算法，用于发现资源约束作业调度的约束规划的高效搜索策略，通过进化程序表示变量选择器，并通过质量评估方案确定其适应度，结果显示进化的变量选择器能够显著提高约束规划的效率。