Genetic-based Constraint Programming for Resource Constrained Job Scheduling
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.
Code (0)
등록된 구현이 없습니다.
Tasks
SchedulingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Domain-Independent Dynamic Programming with Constraint Propagation
There are two prevalent model-based paradigms for combinatorial problems: 1) state-based representations, such as heuristic search, dynamic programming (DP), and decision diagrams, and 2) constraint and domain-based repr…
Proactive and Reactive Constraint Programming for Stochastic Project Scheduling with Maximal Time-Lags
This study investigates scheduling strategies for the stochastic resource-constrained project scheduling problem with maximal time lags (SRCPSP/max)). Recent advances in Constraint Programming (CP) and Temporal Networks …
SchedulingTime Resource Networks
The problem of scheduling under resource constraints is widely applicable. One prominent example is power management, in which we have a limited continuous supply of power but must schedule a number of power-consuming ta…
ManagementSchedulingMAP-Elites based Hyper-Heuristic for the Resource Constrained Project Scheduling Problem
The resource constrained project scheduling problem (RCPSP) is an NP-Hard combinatorial optimization problem. The objective of RCPSP is to schedule a set of activities without violating any activity precedence or resourc…
Combinatorial OptimizationDiversitySchedulingResource-constrained multi-project scheduling with activity and time flexibility
Project scheduling in manufacturing environments often requires flexibility in terms of the selection and the exact length of alternative production activities. Moreover, the simultaneous scheduling of multiple lots is m…
Scheduling