0

I'm looking for some advice for an optimization problem regarding scheduling jobs in a datacenter.

So I have a list of jobs and each job has a required time for finishing and a number of cores it has to run on, e.g. job 1 needs 10 seconds and has to run on 4 cores. The task is now to schedule all jobs on n servers where each server has 8 cores and I have to optimize it such that the time until all jobs are finished is minimal.

I also have an energy component, meaning the fictional data center has some photovoltaic support and for each minute we get some sort of energy input, which we need to run our servers. The more cores a server is currently using, the more energy it needs. If the generate more energy then required we can store the rest in a battery and if we need more than it produces and the battery is empty, we can buy more energy from the state.

The objective is now to optimize on the one hand the required time for all jobs but also to minimize the amount of bought energy.

I first tried to solve it with Gurobi and a Linear Programming Model. It works fine for small inputs, but for larger settings it needs to long to find a solution (I cancelled after 3 hours).

So my next idea was to try to use a genetic algorithm approach. However, I am having trouble to generate a model of chromosomes representing a solution and further when doing crossovers and mutations, how to ensure that the constraints are satisfied. In the literature I mostly found genetic programming approaches to be used on unconstrained problems, but not on problems with many constraints.

Is there anything you could point me to on how to solve or approach genetic algorithms for constrained optimization problems? How do I crossover two solutions while having the offspring also fulfill the constraints?

Throwing away offsprings after a crossover / mutation, which do not satisfy the constraints, does not seem like a good approach to me.

Improve this question
3
  • 2
    This question will likely be closed because it isn't about a specific coding issue and appears to be "opinion based." You are describing a job-shop scheduling LP, and there are a ton of examples/reference material on this. If you wish to update your post with a small reproducible example of how you coded the LP and some info on the size that it starts to falter on, you'll probably get some specific advice. Commented Nov 28, 2023 at 20:30
  • 1
    I asked on the operations research stackexchange. I guess it might be more fitting there. Commented Nov 28, 2023 at 22:38
  • MIP solvers often find very good solutions early on. So when stopping early (say on a time limit), a MIP solver will give you a good solution. The gap % gives feedback on the quality (how much you could be away from the global optimum). Meta-heuristics also give good solutions (they don't know about optimality), but no information about the gap. Commented Nov 29, 2023 at 14:53
Related questions
1
Does translating the genes in a chromosome for a genetic algorithm for a combinatorial function increase the diversity of candidates?
2
Handling duplicates when using Partially Matched Crossover for Genetic Algorithm
2
Evolving a matrix using a genetic algorithm
Load 4 more related questions Show fewer related questions

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.