# Cyclic Job shop Scheduling

**URL:** <https://discourse.julialang.org/t/cyclic-job-shop-scheduling/129409>\
**Category:** Optimization (Mathematical)\
**Created:** [May 28, 2025, 1:33pm UTC](https://discourse.julialang.org/t/cyclic-job-shop-scheduling/129409 "2025-05-28T13:33:59Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ely](https://avatars.discourse-cdn.com/v4/letter/e/87869e/32.png) [@Ely](https://discourse.julialang.org/u/Ely)\
**Post date:** [May 28, 2025, 1:33pm UTC](https://discourse.julialang.org/t/cyclic-job-shop-scheduling/129409/1 "2025-05-28T13:33:59Z")

</div>

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](https://laas.hal.science/hal-02318936v1/document) especially equations from 5a to 5f and the example 2.

Attached the code below:

```julia
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 !

---

<div class="post-metadata">

**Author:** ![slwu89](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/slwu89/32/217323_2.png) [@slwu89](https://discourse.julialang.org/u/slwu89)\
**Post date:** [May 28, 2025, 4:15pm UTC](https://discourse.julialang.org/t/cyclic-job-shop-scheduling/129409/2 "2025-05-28T16:15:57Z")

</div>

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.

```julia
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*α)

```

---

<div class="post-metadata">

**Author:** ![Ely](https://avatars.discourse-cdn.com/v4/letter/e/87869e/32.png) [@Ely](https://discourse.julialang.org/u/Ely)\
**Post date:** [May 30, 2025, 1:03pm UTC](https://discourse.julialang.org/t/cyclic-job-shop-scheduling/129409/3 "2025-05-30T13:03:50Z")

</div>

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:

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

```

> [@slwu89](#):
>
> ```julia
> rename!(D, :i_1=>:j)
> D = filter(row -> row.i < row.j, D)
> select!(D, [:i,:j])
> 
> ```

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

---

<div class="post-metadata">

**Author:** ![slwu89](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/slwu89/32/217323_2.png) [@slwu89](https://discourse.julialang.org/u/slwu89)\
**Post date:** [May 30, 2025, 3:02pm UTC](https://discourse.julialang.org/t/cyclic-job-shop-scheduling/129409/4 "2025-05-30T15:02:53Z")

</div>

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.

```julia
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*α)

```

---

<div class="post-metadata">

**Author:** ![Ely](https://avatars.discourse-cdn.com/v4/letter/e/87869e/32.png) [@Ely](https://discourse.julialang.org/u/Ely)\
**Post date:** [June 4, 2025, 12:22pm UTC](https://discourse.julialang.org/t/cyclic-job-shop-scheduling/129409/5 "2025-06-04T12:22:24Z")

</div>

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](https://global.discourse-cdn.com/julialang/original/3X/a/f/afdd809ee0db28767c56f57de54ee16ae5132da3.png)

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

Thanks again !

---

<div class="post-metadata">

**Author:** ![slwu89](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/slwu89/32/217323_2.png) [@slwu89](https://discourse.julialang.org/u/slwu89)\
**Post date:** [June 4, 2025, 3:47pm UTC](https://discourse.julialang.org/t/cyclic-job-shop-scheduling/129409/6 "2025-06-04T15:47:45Z")

</div>

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](https://blog.algebraicjulia.org/post/2025/03/optim-netflow/)

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [June 4, 2025, 9:07pm UTC](https://discourse.julialang.org/t/cyclic-job-shop-scheduling/129409/7 "2025-06-04T21:07:37Z")

</div>

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.