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

**URL:** <https://discourse.julialang.org/t/a-time-indexed-milp-model-for-tje-job-shop-with-makespan-minimization/126297>\
**Category:** Optimization (Mathematical)\
**Tags:** jump, optimization\
**Created:** [February 25, 2025, 4:41pm UTC](https://discourse.julialang.org/t/a-time-indexed-milp-model-for-tje-job-shop-with-makespan-minimization/126297 "2025-02-25T16:41:21Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![baprata](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baprata/32/204269_2.png) [@baprata](https://discourse.julialang.org/u/baprata)\
**Post date:** [February 25, 2025, 4:41pm UTC](https://discourse.julialang.org/t/a-time-indexed-milp-model-for-tje-job-shop-with-makespan-minimization/126297/1 "2025-02-25T16:41:21Z")

</div>

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](http://dx.doi.org/10.1016/j.cor.2016.04.006)), 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

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

```

---

<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:** [February 25, 2025, 7:40pm UTC](https://discourse.julialang.org/t/a-time-indexed-milp-model-for-tje-job-shop-with-makespan-minimization/126297/2 "2025-02-25T19:40:11Z")

</div>

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:

```julia
@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`.

---

<div class="post-metadata">

**Author:** ![baprata](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baprata/32/204269_2.png) [@baprata](https://discourse.julialang.org/u/baprata)\
**Post date:** [February 26, 2025, 10:32am UTC](https://discourse.julialang.org/t/a-time-indexed-milp-model-for-tje-job-shop-with-makespan-minimization/126297/3 "2025-02-26T10:32:13Z")

</div>

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