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*α)
1 Like
5

Hi, sorry for the late reply and thanks for your answer !

Just to follow up, it turns out that the issue (apparently) was due to an inconsistency in the processing time of Task 4. While it was initially mentioned to be 5 in the paper, the scheduling diagram below and the next FCJSP example seem to treat it as 4. After adjusting the value to 4, optimal cycle time of 13 was obtained.

Scheduling_CJSP
Scheduling_CJSP791×366 20.9 KB

I do hope this is actually the reason tho because i’ve spent a lot of time double-checking the code lmao

Thanks again !

2 Likes
6

Nice, I’d bet that was the problem. Typos abound in papers.

As your models get more complex (complex indexing over more sets), you might consider some more formal way to construct those sets and their indices. I wrote about using something similar to in-memory database structures for the multi-commodity network flow problem here JuMP-ing with AlgebraicJulia II: A practical optimization model – AlgebraicJulia blog

2 Likes
7

Just chiming in to say good sleuthing! I didn’t reply earlier because the discussion seemed to be progressing positively.

With scheduling problems (or really, most problems), visualizing the solution is hugely important. It can often make it much easier to spot errors in the constraints (like two task overlapping, or inconsistencies in the task dependencies) and data (like this example!) than looking at the raw numbers.

2 Likes