Cyclic Job shop Scheduling

Specific Domains Optimization (Mathematical)
1

Hi everyone, I am trying to work on the cyclic job shop scheduling problem mentioned in the following paper:https://laas.hal.science/hal-02318936v1/document especially equations from 5a to 5f and the example 2.

Attached the code below:

using JuMP
using CPLEX
using DataFrames

T = DataFrame(
    i = [:s,1,2,3,4,5,6,7,:f],
    p = [0,5,4,5,5,4,3,5,0],
    m = [0,1,1,3,1,2,4,3,0]
)

E = DataFrame(
    src = [ :s, 1, 2, 3, 4, :f, :s, 5, 6, 7],
    tgt = [ 1, 2, 3, 4, :f, :s, 5, 6, 7, :f],
    H = [0,0,0,0,0,2,0,0,0,0 ]
)


M=sum(T.p)

model=JuMP.Model(CPLEX.Optimizer)

@variable(model, V)


T.t = @variable(model, t[1:nrow(T)] >= 0)

#5f
T.u = @variable(model, u[1:nrow(T)] >= 0 )



D = Set{Tuple{Int, Int}}()
for i in 1:nrow(T), j in 1:nrow(T)
    m_i = T.m[i]
    m_j = T.m[j]
    id_i = T.i[i]
    id_j = T.i[j]

    if i != j && m_i == m_j && m_i != 0
        
        pair = (min(id_i, id_j), max(id_i, id_j))
        push!(D, pair)
    
    end
end

print(D)


@variable(model, K[i in 1:7, j in 1:7] >= 0, Int)


for (i, j) in D
    idx_i = findfirst(T.i .== i)
    idx_j = findfirst(T.i .== j)
    pi = T.p[idx_i]
    pj = T.p[idx_j]

    
    @constraint(model, T.u[idx_j] ≥ T.u[idx_i] + V * pi - K[i, j])
    @constraint(model, T.u[idx_i] ≥ T.u[idx_j] + V * pj - K[j, i])

    
    @constraint(model, K[i,j] + K[j,i] ≥ 1)
end
    
#5a
for i in eachrow(T)
    if i.p > 0
        @constraint(model, V <= 1 / i.p)
    end
end

#5b
for e in  eachrow(E)
    i = e.src
    j = e.tgt
    hij = e.H
    ui = T[findfirst(T.i .== i), :u]
    uj = T[findfirst(T.i .== j), :u]
    pi = T[findfirst(T.i .== i), :p]
    @constraint(model, uj + hij >= ui + V*pi)
end


@objective(model, Max, V)

optimize!(model)

println(value(V))
println(value(1/V))

Optimal cycle time should be 13, however, current code is still showing 9.5 so it is probably not taking into consideration the disjunctive constraints ( D and K[i,j))

Thanks in advance !

2

Try something similar to the following. The cycle time is coming out as approx 14, so perhaps I’ve entered something wrong, you should double check carefully. But the point is to construct D from the product of T with itself and remove elements we don’t want (just doing what you did but using the data frame interface). Any way to construct that relation correctly should do (D \subset T\times T). The decision variables K_{ij} however seem to need to be (i,j) and (j,i) for all (i,j) \in D hence the way K was made. It’s possible I’ve misinterpreted the set that indexed K however, I’m not that familiar with this particular model.

using JuMP, HiGHS
using DataFrames

# T: set of tasks
T = DataFrame(
    i = [:s,1,2,3,4,5,6,7,:f], 
    p = [0,5,4,5,5,4,3,5,0],
    r = [nothing,1,1,3,1,2,4,3,nothing]
)

# E: set of precedence constraints
E = DataFrame(
    i = [:s, 1, 2, 3, 4, :f, :s, 5, 6, 7],
    j = [1, 2, 3, 4, :f, :s, 5, 6, 7, :f],
    H = [0, 0, 0, 0, 0, 2, 0, 0, 0, 0]
)

# D: set of disjunction constraints
D = crossjoin(T, T, makeunique=true)
deleteat!(D, findall(D.i .== D.i_1)) # i!=j
deleteat!(D, findall(D.i .∈ Ref([:s,:f]))) # no start or finish tasks
deleteat!(D, findall(D.i_1 .∈ Ref([:s,:f]))) # no start or finish tasks
deleteat!(D, findall(D.r .!= D.r_1)) # keep (i,j) that use same machine
rename!(D, :i_1=>:j)
select!(D, [:i,:j])

# K the set of heights of disjunction constraints
K = vcat(
    D,
    DataFrame(i=D.j, j=D.i)
)

# JuMP model and optimizer
model = JuMP.Model(HiGHS.Optimizer)

# 1 / cycle time
@variable(model, τ)

# 5a
for i in eachrow(T)
    if i.i ∈ [:s, :f]
        continue
    else
        @constraint(
            model,
            τ ≤ 1/i.p
        )
    end
end

# 5f and define u (decision variable)
T.u = @variable(model, u[1:nrow(T)] ≥ 0)

# 5e and define K_ij (decision variable)
K.Kij = @variable(model, [1:nrow(K)], Int)

# 5b
for e in eachrow(E)
    ui = T[findfirst(T.i .== e.i), :u]
    p_i = T[findfirst(T.i .== e.i), :p]
    uj = T[findfirst(T.i .== e.j), :u]
    Hij = e.H
    @constraint(
        model,
        uj + Hij ≥ ui + τ*p_i 
    )
end

# 5c
for d in eachrow(D)
    ui = T[findfirst(T.i .== d.i), :u]
    p_i = T[findfirst(T.i .== d.i), :p]
    uj = T[findfirst(T.i .== d.j), :u]
    Kij = K[findfirst(K.i .== d.i .&& K.j .== d.j), :Kij]
    @constraint(
        model,
        uj + Kij ≥ ui + τ*p_i
    )
end

# 5d
for d in eachrow(D)
    Kij = K[findfirst(K.i .== d.i .&& K.j .== d.j), :Kij]
    Kji = K[findfirst(K.i .== d.j .&& K.j .== d.i), :Kij]
    @constraint(
        model,
        Kij + Kji == 1
    )
end

# obj
@objective(
    model,
    Max,
    τ
)

optimize!(model)

α = value(1/τ)
value.(T.u*α)
2 Likes
3

Hi, thanks again for your help !
Your approach does seem quite reasonable, i did double check and still can’t find out what’s wrong.

In my case (and i guess according to the paper), D should only contain once the same pair of tasks linked by disjunction constraints so i added the follwoing line to avoid redundancy:

D = filter(row -> row.i < row.j, D)

But it kinda made it worse as i returned to getting an optimal cycle time = 9.5

4

I think D should be defined with “redundancy” because the K variables are actually supposed to be part of it. They state \mathcal{D} = \{(i,j)|R(i)\cap R(j)\neq \emptyset\} where the indices are coming from (i,j)\in \mathcal{T}^2, i\neq j. You can see for example in the graph associated with the example that both (7,3) and (3,7) are in \mathcal{D}. That being said the mathematical notation in the paper is not very clear (e.g. sometimes writing K_{i,j} sometimes using K(i,j), I guess they are supposed to be the same). They also don’t bother to really define clearly the red labels in the graph, oh well.

See a slightly edited version below.

using JuMP, HiGHS
using DataFrames

# T: set of tasks
T = DataFrame(
    i = [:s,1,2,3,4,5,6,7,:f], 
    p = [0,5,4,5,5,4,3,5,0],
    r = [nothing,1,1,3,1,2,4,3,nothing]
)

# E: set of precedence constraints
E = DataFrame(
    i = [:s, 1, 2, 3, 4, :f, :s, 5, 6, 7],
    j = [1, 2, 3, 4, :f, :s, 5, 6, 7, :f],
    H = [0, 0, 0, 0, 0, 2, 0, 0, 0, 0]
)

# D: set of disjunction constraints
D = crossjoin(T, T, makeunique=true)
rename!(D, :i_1=>:j)
deleteat!(D, findall(D.i .∈ Ref([:s,:f]))) # no start or finish tasks
deleteat!(D, findall(D.j .∈ Ref([:s,:f]))) # no start or finish tasks
deleteat!(D, findall(D.i .== D.j)) # i!=j
deleteat!(D, findall(D.r .!= D.r_1)) # keep (i,j) that use same machine
select!(D, [:i,:j])

# JuMP model and optimizer
model = JuMP.Model(HiGHS.Optimizer)

# 1 / cycle time
@variable(model, τ)

# 5a
for i in eachrow(T)
    if i.i ∈ [:s, :f]
        continue
    else
        @constraint(
            model,
            τ ≤ 1/i.p
        )
    end
end

# 5f and define u (decision variable)
T.u = @variable(model, u[1:nrow(T)] ≥ 0)

# 5e and define K_ij (decision variable)
D.K = @variable(model, [1:nrow(D)], Int)

# 5b
for e in eachrow(E)
    ui = T[findfirst(T.i .== e.i), :u]
    p_i = T[findfirst(T.i .== e.i), :p]
    uj = T[findfirst(T.i .== e.j), :u]
    Hij = e.H
    @constraint(
        model,
        uj + Hij ≥ ui + τ*p_i 
    )
end

# 5c
for d in eachrow(D)
    ui = T[findfirst(T.i .== d.i), :u]
    p_i = T[findfirst(T.i .== d.i), :p]
    uj = T[findfirst(T.i .== d.j), :u]
    Kij = d.K
    @constraint(
        model,
        uj + Kij ≥ ui + τ*p_i
    )
end

# 5d
for d in eachrow(D)
    Kij = d.K
    Kji = D[findfirst(D.i .== d.j .&& D.j .== d.i), :K]
    @constraint(
        model,
        Kij + Kji == 1
    )
end

# obj
@objective(
    model,
    Max,
    τ
)

optimize!(model)

α = value(1/τ)
value.(T.u*α)