Beginner | Basic Cyclic Scheduling | New To Julia and Scheduling

[Ely]

Hi, i am trying to work on some cyclic scheduling problems with CPLEX and Julia and i need to admit i am quite new to both.
Any idea please how a similar program can be solved:

With the following data:
Tasks from 1 to 7 with the following processing times: 5 4 5 5 4 3 5
Knowing that the optimal cycle time in the article is equal to 9.5

Thanks in advance ! ( I have tried some code but never was able to reach the optimal/correct result)

[gdalle]

Hi, welcome to the community!
Perhaps you want to take a look at JuMP.jl?

[Ely]

Thanks ! That’s what i am trying to do tbh.

I am tryin to share my code here but it’s not possible. Can i create another topic for that ?

[gdalle]

I think as a new member your link sharing permissions are still restricted for a while. Can you just copy-paste the code into a block with backticks?

[Ely]

Done !
I tried to give this code a try but still not giving the right result.

using JuMP
using CPLEX

T = 1:7
p = [5, 4, 5, 5, 4, 3, 5]  


model = Model(CPLEX.Optimizer)

# start times of each task 
@variable(model, x[i in T] >= 0)

# Cycle time
@variable(model, C >= 0)



# Constraints: Cycle time >= p[i]
for i in T
        @constraint(model, C >= p[i])
end

# precedence constraints
for i in T, j in T 
    if i != j
        @constraint(model, x[j] + C >= x[i] + p[i])
    end
end


@objective(model, Min, C)

optimize!(model)

println("Optimal cycle time is equal to ", value(C)) 

# If anyone has already worked on the cyclic scheduling problem, I'd be grateful for any tips !

[gdalle]

I assume H_{i,j} is some kind of precedence variable? I don’t see it in your model

[Ely]

Exactly, Hij is the height of the precedence constraint.

This is the example i’m trying to test:

I’ve actually tried to add it somehow at the beginning but still didn’t work.

I guess i need to check more articles and see how it goes.

Thanks !

[slwu89]

Hi, welcome to Julia. I found the paper you are referencing (note, it might be nice in the future if you can directly provide us a link) here: https://laas.hal.science/hal-02318936v1/document and I implemented the model you cite in section 2 below, which retrieves the answer given in the paper of a cycle time of 9.5.

Because the paper conceptually uses a graph to structure the sets and constraints it considers, I use 2 DataFrames to store information related to the vertices (T) and edges (E). You will note that we store p, the times associated to each task with the tasks, as well as attach the vector of decision variables t directly to the dataframe so they can be easily retrieved when we write constraint 1b. We store the H variables directly with the dataframe that stores the edges as an edge list format.

One further note, you may find more focused help on optimization topics specifically by posting in the optimization specific forum here Optimization (Mathematical) - Julia Programming Language

using JuMP, HiGHS
using DataFrames

T = DataFrame(
    i = [:s,1,2,3,4,5,6,7,:f], 
    p = [0,5,4,5,5,4,3,5,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]
)

model = JuMP.Model(HiGHS.Optimizer)

# cycle time
@variable(model, α)

# dec var: starting time and 1c
T.t = @variable(model, t[1:nrow(T)] ≥ 0)

# 1a
for i in eachrow(T)
    @constraint(
        model,
        α ≥ i.p        
    )
end

# 1b
for e in eachrow(E)
    i = e.src
    j = e.tgt
    ti = T[findfirst(T.i .== i), :t]
    pi = T[findfirst(T.i .== i), :p]
    tj = T[findfirst(T.i .== j), :t]
    Hij = e.H
    @constraint(
        model,
        tj + α*Hij ≥ ti + pi
    )
end

# obj
@objective(
    model,
    Min,
    α
)

optimize!(model)

# look at optimal vals of dec vars
value(α)
value.(T.t)

[Ely]

Hi, Thanks a lot for the implementation as well as the explanation !
I’ll try to tackle the rest of the paper with a similar approach.

Also well noted regarding the reference, I’ll make sure to have it included in further posts (if needed).

Thanks again !