A time-indexed MILP model for tje job shop with makespan minimization

Specific Domains Optimization (Mathematical)
,
1

Dear colleagues,
I am coding the time-indexed model for the job shop scheduling problem as presented by Hu and Beck (Equations (10)-(15) in Redirecting), but the solution is not correct. I successfully implemented all the other MILP models in this paper, and the correct makespan is 31 units. On the other hand, in this time-indexed formulation, the makespan returned is 32 units. What is the problem with it? Thank you very much, Bruno

using JuMP,CPLEX


P = [2 5; 6 4; 2 3; 5 4; 6 7; 4 3; 6 5]
O = [1 2; 2 1; 2 1; 1 2; 2 1; 1 2; 1 2]
M = size(P,2)
N = size(P,1)
H = 100

model = Model(optimizer_with_attributes(CPLEX.Optimizer,"CPX_PARAM_TILIM" => time_limit,  "CPX_PARAM_THREADS" => 1))

 # Decision variables
@variable(model, Cmax >= 0)  # Tempo de conclusão total
@variable(model, C[j in 1:N] >= 0)  # Tempo de conclusão de cada job
@variable(model, x[i in 1:M, j in 1:N, t in 1:H], Bin)  # x[i,j,t] = 1 se a operação j na máquina i começa no tempo t

# Objective function
@objective(model, Min, Cmax)

# Constraints
@constraint(model, [j in 1:N, i in 1:M], sum(x[i,j,t] for t in 1:H) == 1)
@constraint(model, [j in 1:N, i in 1:M], C[j] >= sum((t + P[j,i]) * x[i,j,t] for t in 1:H))
@constraint(model, [j in 1:N], Cmax >= C[j])
@constraint(model, [i in 1:M, t in 1:H], sum(x[i,j,t_] for j in 1:N, t_ in max(1, t - P[j,i] + 1):t) <= 1)
@constraint(model, [j in 1:N, h in 2:M], sum((t + P[j,O[j,h-1]]) * x[O[j,h-1],j,t] for t in 1:H) <= sum(t * x[O[j,h],j,t] for t in 1:H))

optimize!(model)

zIP = objective_value(model)

println("Makespan: ", zIP)
2

I don’t have access to the paper, so I can’t confirm, but you almost certainly have a typo somewhere in your formulation.

Perhaps you meant:

@constraint(model, [j in 1:N, i in 1:M], C[j] >= sum((t + P[j,i] - 1) * x[i,j,t] for t in 1:H))

Note the - 1. Otherwise you are measuring the start time as t = 1 instead of t = 0.

1 Like
3

Thank you very much, the solution is correct now. Bruno

1 Like