Genetic-based Constraint Programming for Resource Constrained Job
Scheduling
- URL: http://arxiv.org/abs/2402.00459v1
- Date: Thu, 1 Feb 2024 09:57:38 GMT
- Title: Genetic-based Constraint Programming for Resource Constrained Job
Scheduling
- Authors: Su Nguyen and Dhananjay Thiruvady and Yuan Sun and Mengjie Zhang
- Abstract summary: Resource constrained job scheduling is a hard computation optimisation problem that originates in the mining industry.
Off-the-shelf solutions cannot solve this problem satisfactorily in reasonable timeframes.
This paper proposes a genetic programming algorithm to discover efficient search strategies of constraint programming.
- Score: 5.068093754585243
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- Differentiable Combinatorial Scheduling at Scale [18.09256072039255]
We propose a differentiable scheduling framework, utilizing Gumbel-Softmax differentiable sampling technique.
To encode inequality constraints for scheduling tasks, we introduce textitconstrained Gumbel Trick, which adeptly encodes arbitrary inequality constraints.
Our method facilitates an efficient and scalable scheduling via gradient descent without the need for training data.
arXiv Detail & Related papers (2024-06-06T02:09:39Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms.
Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability.
We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
arXiv Detail & Related papers (2023-07-17T20:11:56Z) - Learning a Generic Value-Selection Heuristic Inside a Constraint
Programming Solver [2.8425837800129696]
We introduce a generic learning procedure that can be used to obtain a value-selection inside a constraint programming solver.
This has been achieved thanks to the combination of a deep Q-learning algorithm, a tailored reward signal, and a heterogeneous graph neural network architecture.
arXiv Detail & Related papers (2023-01-05T05:13:48Z) - A Hybrid Evolutionary Approach to Solve University Course Allocation
Problem [0.0]
This paper discusses various types of constraints, difficulties and solutions to overcome the challenges regarding university course allocation problem.
A hybrid evolutionary algorithm has been defined combining Local Repair Algorithm and Modified Genetic Algorithm to generate the best course assignment.
arXiv Detail & Related papers (2022-11-15T09:43:02Z) - An Efficient Merge Search Matheuristic for Maximising the Net Present
Value of Project Schedules [5.10800491975164]
Resource constrained project scheduling is an important optimisation problem with many practical applications.
We propose a new math-heuristic algorithm based on Merge Search and parallel computing to solve the resource constrained project scheduling.
arXiv Detail & Related papers (2022-10-20T13:30:23Z) - Algorithm Selection on a Meta Level [58.720142291102135]
We introduce the problem of meta algorithm selection, which essentially asks for the best way to combine a given set of algorithm selectors.
We present a general methodological framework for meta algorithm selection as well as several concrete learning methods as instantiations of this framework.
arXiv Detail & Related papers (2021-07-20T11:23:21Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together.
The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively.
Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
arXiv Detail & Related papers (2021-03-10T03:16:12Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
Security-constrained optimal power flow (SCOPF) is fundamental in power systems.
Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs.
This paper proposes a novel approach that combines deep learning and robust optimization techniques.
arXiv Detail & Related papers (2020-07-14T12:38:21Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime.
We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive.
In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
arXiv Detail & Related papers (2020-07-06T15:20:17Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms.
We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
arXiv Detail & Related papers (2020-01-29T09:40:58Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.