Symmetry breaking: scheduling problems with job duration dependent on ressource allocation

Specific Domains Optimization (Mathematical)
5

Your other option is to consider a column generation/set covering model. I simplified things by removing the exoskeleton stuff (I don’t understand what it’s doing?). But this should point you in the right direction. It’s a nice model, so I should write this up as a tutorial for the documentation.

using JuMP, Gurobi

N_FOREMAN = 1
N_WORKERS = 2

P = [
    Int[],
    Int[],
    [2],
    [1, 3],
    [2],
    [3, 5],
    [4, 5, 6],
    [10],
    [2],
    [1, 3, 9],
    [7, 10],
    [10],
    [2],
    [13, 3],
    [8, 11, 14],
    [15],
    [12, 16],
    [16],
    [8, 11, 12],
    [15],
    [17, 18, 19, 20],
]

Duration = [
    35 missing missing
    missing 35 25
    missing 30 25
    18 missing missing
    15 9 missing
    10 6 missing
    80 60 50
    30 20 missing
    60 50 missing
    missing 40 30
    missing 60 50
    40 30 missing
    20 10 8
    missing 50 40
    missing 60 50
    20 14 missing
    missing 30 25
    6 3 missing
    10 missing missing
    10 missing missing
    1 missing missing
]

# Delays between jobs / quasi-paralellizable jobs
# x axis: Successor ; y axis: Predecessor --> job 3 can start after 20% of job 2 are done
Lag=[
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0.8	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0.8	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0.8	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0.8	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
]

N_JOBS = length(P)
T = sum(minimum(coalesce.(Duration[j, :], 10_000)) for j in 1:N_JOBS)

# Foreman alloc. mandatory for job
F = [0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0]

model = Model(Gurobi.Optimizer)
x = [VariableRef[] for j in 1:N_JOBS]
@variable(model, 1 <= start_times[1:N_JOBS] <= T)
@variable(model, 1 <= finish_times[1:N_JOBS] <= T)
@variable(model, make_span)
@constraints(model, begin
    c_n_workers[1:T], 0 <= N_WORKERS
    c_n_foreman[1:T], 0 <= N_FOREMAN
    c_jobs[j = 1:N_JOBS], 0 == 1
    c_foreman[j = 1:N_JOBS], 0 >= F[j]
    c_start_time[j = 1:N_JOBS], 0 == start_times[j]
    c_finish_time[j = 1:N_JOBS], 0 == finish_times[j]
    # Precedence
    [j = 1:N_JOBS, k = P[j]], start_times[j] >= finish_times[k] + 1 - Lag[j, k] * (finish_times[k] - start_times[k])
    make_span .>= finish_times
end)
@objective(model, Min, make_span)

function add_column(
    model::Model,
    job_id::Int,
    start_time::Int,
    n_workers::Int,
    n_foreman::Int,
)
    c = @variable(
        model,
        binary = true,
        base_name = "x[$job_id,$start_time,$n_workers,$n_foreman]",
    )
    push!(x[job_id], c)
    set_normalized_coefficient(c_jobs[job_id], c, 1.0)
    duration = Duration[job_id, n_workers + n_foreman]
    if n_workers > 0
        for t in start_time:(start_time + duration - 1)
            set_normalized_coefficient(c_n_workers[t], c, n_workers)
        end
    end
    if n_foreman > 0
        for t in start_time:(start_time + duration - 1)
            set_normalized_coefficient(c_n_foreman[t], c, n_foreman)
        end
        set_normalized_coefficient(c_foreman[job_id], c, 1.0)
    end
    set_normalized_coefficient(c_start_time[job_id], c, start_time)
    set_normalized_coefficient(c_finish_time[job_id], c, start_time + duration - 1)
    return
end

# For small problems, we can enumerate very possible column
n = 0
for job_id in 1:N_JOBS, n_foreman in 0:N_FOREMAN, n_workers in 0:N_WORKERS
    n_total = n_foreman + n_workers
    if n_total == 0 || ismissing(Duration[job_id, n_total])
        continue
    end
    duration = Duration[job_id, n_total]
    # Could improve this by computing an earliest start date instead of assuming
    # start_time = 1 for every job. 
    for start_time in 1:(T - duration)
        add_column(model, job_id, start_time, n_workers, n_foreman)
        n += 1
    end
end
@info "Added $n columns"

optimize!(model)
1 Like