1
$\begingroup$

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 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).

Some more concrete information and my approach: The size is relatively small: 5 servers, each with 8 cores and 70 tasks one has to schedule. Each task is between 1000 and 10000 seconds and needs either 1, 2, or 4 cores.

For the photovoltaic energy, we get a specified number of watts each minute which we can use for our servers / store in a battery.

I tried to model the problem with a fundamental 3D binary matrix x[t][j][c]. So for each job j I store if it is scheduled at time t on the core c.

This is probably excessive to have a variable t for each time slot, but I can't find another way to keep the time in account to add the solar energy.

Now I formulated all my constraints based on the scheduling matrix.

I set t to one minute each until 12 hours, so I have 720 time slots to schedule. In total x has about 2 million entries / variables. I at first thought this would be fine for Gurobi but it does not finish in reasonable time.

Do you have any other idea how I can model this problem without storing every time slot explicitly?

This is my current approach:

x = {}
for t in range(1, NUM_TIMESTAMPS + 1):
    for j in range(NUM_TASKS):
        for c in range(TOTAL_NUM_OF_CORES):
            x[(t, j, c)] = model.addVar(vtype=GRB.BINARY, name=f"x_{t}_{j}_{c}")

delta_energy = []
battery_status = []

tmp_battery = []
tmp_min_battery = []

buy_state_energy = []
energy_bought = []

for t in range(NUM_TIMESTAMPS + 1):
    delta_energy.append(model.addVar(lb=-GRB.INFINITY, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name=f"d_{t}"))
    battery_status.append(model.addVar(lb=-GRB.INFINITY, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name=f"b_{t}"))

    tmp_battery.append(model.addVar(lb=-GRB.INFINITY, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name=f"tmp_battery"))
    tmp_min_battery.append(model.addVar(lb=-GRB.INFINITY, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS, name=f"tmp_min_battery"))

    buy_state_energy.append(model.addVar(vtype=GRB.BINARY, name=f"s_{t}"))
    energy_bought.append(model.addVar(lb=-GRB.INFINITY, ub=GRB.INFINITY, vtype=GRB.CONTINUOUS))

model.addConstr(battery_status[0] == MAX_BATTERY_LEVEL)
model.addConstr(energy_bought[0] == 0)

# Assure that jobs are actually running.
for j in range(NUM_TASKS):
    model.addConstr(sum([x[(t, j, c)] for t in range(1, NUM_TIMESTAMPS + 1) for c in range(TOTAL_NUM_OF_CORES)]) == tasks[j].time * tasks[j].num_cores,
        name="constraint 1")


# Check that the number of required cores are being used.
for t in range(1, NUM_TIMESTAMPS + 1):
    for j in range(NUM_TASKS):
        num_active_cores = sum([x[(t, j, c_prime)] for c_prime in range(TOTAL_NUM_OF_CORES)])

        for c in range(TOTAL_NUM_OF_CORES):
            model.addConstr(tasks[j].num_cores * x[(t, j, c)] == x[(t, j, c)] * num_active_cores,
                name="constraint 3")


# Only one job per core.
for t in range(1, NUM_TIMESTAMPS + 1):
    for c in range(TOTAL_NUM_OF_CORES):
        model.addConstr(sum([x[(t, j, c)] for j in range(NUM_TASKS)]) <= 1,
            name="constraint 4")


# Store the free energy not needed by the solar panels.
for t in range(1, NUM_TIMESTAMPS + 1):
    model.addConstr(delta_energy[t] == solar_data[t] - get_server_energy_consumption(sum(x[t, j, c] for j in range(NUM_TASKS) for c in range(TOTAL_NUM_OF_CORES))))
    model.addConstr(tmp_battery[t] == battery_status[t - 1] + delta_energy[t])

    # Set battery status at time t to max(min(tmp_battery, MAX_BATTERY), MIN_BATTERY) to ensure it is the maximum 
    # but is in the interval [MIN_BATTERY_LEVEL, MAX_BATTERY_LEVEL]
    model.addConstr(tmp_min_battery[t] == gp.min_(MAX_BATTERY_LEVEL, tmp_battery[t]), name="Reducing battery level to MAX_BATTERY_LEVEL")
    model.addConstr(battery_status[t] == gp.max_(tmp_min_battery[t], MIN_BATTERY_LEVEL), name= "Keeping battery level above MIN_BATTERY_LEVEL")


# Buy state energy if battery tmp battery is negative, e.g.
# buy_state_energy = 1 if tmp_battery < 0 else 0
for t in range(1, NUM_TIMESTAMPS + 1):
    model.addConstr(LARGE_CONSTANT * buy_state_energy[t] >= -tmp_battery[t])

    # Buy the needed energy if necessary 
    model.addConstr(energy_bought[t] == buy_state_energy[t] * -1 * tmp_battery[t])

# Constraint 7:
# Battery has a lower and upper limit.
for t in range(NUM_TIMESTAMPS + 1):
    model.addConstr(battery_status[t] >= MIN_BATTERY_LEVEL)
    model.addConstr(battery_status[t] <= MAX_BATTERY_LEVEL)


# Store when the last job finishes.
# max t s.t. x[t, j, c] == true for all j, c
last_job = model.addVar(vtype=GRB.INTEGER, name="last_job")
for t in range(1, NUM_TIMESTAMPS + 1):
    for j in range(NUM_TASKS):
        for c in range(TOTAL_NUM_OF_CORES):
            model.addConstr(last_job >= t * x[(t, j, c)])


model.setObjectiveN(sum(buy_state_energy), 0, 99)
model.setObjectiveN(sum(energy_bought), 2, 5)
model.setObjectiveN(last_job, 1, 4)
```
$\endgroup$
5
  • $\begingroup$ Welcome to OR.SE. As you correctly pointed out, by using time_indexed formulation it injects a huge number of binary variables into the model. I am not aware of the rest of your constraints, but column generation can be a good idea for that. (I should say It actually needs some advanced skills). Is it possible to suppose that minimizing the required energy is equivalent to minimizing the number of cores used? I mean can we drop the constraints related to the energy-consuming and focus only on the scheduling problem to minimize the number of cores? $\endgroup$
    – A.Omidi
    Nov 29, 2023 at 13:01
  • $\begingroup$ The number of cores used is directly related to the energy consume. However only minimizing the number of cores is not enough since if we have a large solar energy output at a time $t$, we can utilize more cores at the same time without needing to buy energy. $\endgroup$
    – wind.leon
    Nov 29, 2023 at 14:29
  • $\begingroup$ Thanks for your comments. A) Is it possible to use multiple servers to do a task? (I mean e.g. core_1 of server 1 and core_3 of server 4?) B) It seems you have some non-linear terms, particularly "constraint 3", in your formulation. As it is a product of a bunch of binary variables, Gurobi has some internal options to linearize this kind of term. Do you try that? $\endgroup$
    – A.Omidi
    Nov 29, 2023 at 16:34
  • $\begingroup$ A) I think strictly it is not allowed, but since each task can only require 1, 2, or 4 cores and each server has 8 cores, there should also be a way to later on switch the cores such that each task only runs on one server. So I did not add this constraint for now B) This sounds good and I haven't tried it. Do you mean setting the parameter NonConvex = 2 or could you point me into the internal options you meant? Thanks for your help:) $\endgroup$
    – wind.leon
    Nov 29, 2023 at 16:48
  • 1
    $\begingroup$ For the second please, see this link. For the first, I add some comments asap. $\endgroup$
    – A.Omidi
    Nov 29, 2023 at 17:00

1 Answer 1

0
$\begingroup$

Using this link (kind of constraint programming), lets define $ s_{j}$ as start time for task $j$ over a domain of $ T =\{1,2,...720 \}$ mins on core $c$ with $d_j$ being the processing time for a task $j$, binary $x_{j}^c = 1$ if task $j$ is assigned to core $c$

Obj $\min_{s} \sum_{j} (s_{j} + d_j)$

Constraints
$ s_{j} + d_j \le 720$
You can avoid above constraint if you define $s_j$ over $\{1,2,...T \}$ where $T=720 -$ shortest task duration.

$\sum_c x_{j}^c = 1 \quad \forall j $

If each core $c$ has only 1 task at a time then you'd need a binary variable $y_{t}^c$ with $t$ over $T$ & constraints; in other words you'd need $720\times c$ binaries.

$ s_j + M(x_{j}^c - 1) \le ty_{t}^c \quad \forall c, t$: where $M = \max \{T,J,C \}$ with $J, C$ being number of tasks & cores.

$ d_j(y_{t}^c +x_{j}^c - 1) \le \sum_{k=t+1}^{t+d_j-1} y_{k}^c$

Also for power bought, you can straight away use continuous var (p) with
$-tmp_t \le p_t$ : Make power bought positive. Since power bought is to be minimized solver will make $ 0 \le \sum_t p_t$ reduced to $0$ wherever it can.

$\endgroup$
4
  • $\begingroup$ Could you elaborate on $t_0 = 16, t_1 = 32$? How does it schedule a good solution if a job needs 17 minutes? Just wait 15 minutes until we can schedule the next one at $t_1 = 32$? $\endgroup$
    – wind.leon
    Nov 29, 2023 at 4:17
  • $\begingroup$ @wind.leon I am using time slots of 16 mins. Try using linear constraints with time unit of 1 min then. Sometimes non convex constraints could be problem. If that doesn't improve then we'd explore further. $\endgroup$ Nov 29, 2023 at 4:47
  • $\begingroup$ Sorry I am not sure if I can follow you here. When each time slot represents a period of 16 minutes, how do I use the linear constraints of a time period of 1 minute? If each time slot is 16 minutes then I can't represent anything less than 16 minutes, right? $\endgroup$
    – wind.leon
    Nov 29, 2023 at 15:00
  • $\begingroup$ @wind.leon I've updated the answer. $\endgroup$ Nov 30, 2023 at 3:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.