# Job shop scheduling

**URL:** <https://discourse.julialang.org/t/job-shop-scheduling/96938>\
**Category:** Optimization (Mathematical)\
**Tags:** jump, cplex\
**Created:** [April 1, 2023, 9:53am UTC](https://discourse.julialang.org/t/job-shop-scheduling/96938 "2023-04-01T09:53:43Z")\
**Posts on this page:** 5\
**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:** [April 1, 2023, 9:53am UTC](https://discourse.julialang.org/t/job-shop-scheduling/96938/1 "2023-04-01T09:53:43Z")

</div>

I am studying the mixed-integer linear programming formulation for the job shop with makespan minimization proposed by Manne (see Equations (1)-(7) from Ku and Beck (2016) [http://dx.doi.org/10.1016/j.cor.2016.04.006](http://dx.doi.org/10.1016/j.cor.2016.04.006), and my implementation is wrong.

Concerning this test instance:  
[http://jobshop.jjvh.nl/instance.php?instance\_id=6](http://jobshop.jjvh.nl/instance.php?instance_id=6)  
the optimal solution is 55, but my model returns 56. I cannot identify the error.

@variable(model, x[j in 1:N, i in 1:M] \>=0)  
@variable(model, z[j in 1:N-1, k in j+1:N, i in 1:M], Bin)  
@variable(model, Cmax \>=0)  
@objective(model, Min, Cmax)  
@constraint(model, [j in 1:N,h in 2:M], x[j,O[j,h]] \>= x[j,O[j,h-1]] + P[j,O[j,h-1]])  
@constraint(model, [j in 1:N-1, k in j+1:N, i in 1:M], x[j,i] \>= x[k,i] + P[k,i] - V \* z[j,k,i])  
@constraint(model, [j in 1:N-1, k in j+1:N, i in 1:M], x[k,i] \>= x[j,i] + P[j,i] - V \* (1 - z[j,k,i]))  
@constraint(model, [j in 1:N], Cmax \>= x[j,O[j,M]] + P[j,O[j,M]])

---

<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:** [April 2, 2023, 1:35am UTC](https://discourse.julialang.org/t/job-shop-scheduling/96938/2 "2023-04-02T01:35:13Z")

</div>

Nothing immediately stands out as wrong, but it’s hard to tell without the data etc.

You should take a read of: [Please read: make it easier to help you](https://discourse.julialang.org/t/please-read-make-it-easier-to-help-you/14757). It’s easier to help if you can provide a reproducible example that people can copy and paste into their REPL.

Debugging incorrect results can be difficult. See the suggestions in [Debugging · JuMP](https://jump.dev/JuMP.jl/stable/tutorials/getting_started/debugging/#Incorrect-results)

If it’s off by one for every instance, there’s likely a bug in your model. If it’s just wrong for this instance, then there’s likely a typo in the data that you’re using.

---

<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:** [April 2, 2023, 6:16pm UTC](https://discourse.julialang.org/t/job-shop-scheduling/96938/3 "2023-04-02T18:16:19Z")

</div>

Dear Oscar, thank you very much for your attention. The results are different from optimal for several test instances. I have copied the data from the site. For some small-sized test instances (2 or 3 machines), the results from the model are correct. For problems with more machines, the results are wrong. I printed the model, and I did not found any error.

I am sending the source code:

```julia
using DelimitedFiles, JuMP, CPLEX 
P = [1 3 6 7 3 6;
     8 5 10 10 10 4;
     5 4 8 9 1 7;
     5 5 5 3 8 9;
     9 3 5 4 3 1;
     3 3 9 10 4 1]
     
O = [3 1 2 4 6 5;
     2 3 5 6 1 4;
     3 4 6 1 2 5;
     2 1 3 4 5 6;
     3 2 5 6 1 4;
     2 4 6 1 5 3] 

M = size(P,2)
N = size(P,1)
V = sum(P)
zIP = 0
time_limit = 10800

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

# Decision variables
@variable(model, x[j in 1:N, i in 1:M] >=0)
@variable(model, z[j in 1:N-1, k in j+1:N, i in 1:M], Bin)
@variable(model, Cmax >=0)

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

# Constraints
@constraint(model, [j in 1:N, h in 2:M], x[j,O[j,h]] >= x[j,O[j,h-1]] + P[j,O[j,h-1]])
@constraint(model, [j in 1:N-1, k in j+1:N, i in 1:M], x[j,i] >= x[k,i] + P[k,i] - V*z[j,k,i]) 
@constraint(model, [j in 1:N-1, k in j+1:N, i in 1:M], x[k,i] >= x[j,i] + P[j,i] - V*(1 - z[j,k,i]))
@constraint(model, [j in 1:N], Cmax >= x[j,O[j,M]] + P[j,O[j,M]])
optimize!(model)
zIP = objective_value(model)
print(model)

```

---

<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:** [April 2, 2023, 9:29pm UTC](https://discourse.julialang.org/t/job-shop-scheduling/96938/4 "2023-04-02T21:29:54Z")

</div>

This actually took me quite a while to figure out. I thought I was going crazy, because everything looked correct. Then I tried hard-coding one of the solutions, [Job Shop Solutions](http://jobshop.jjvh.nl/solutions.php?instance_id=6), and it was infeasible, so there was definitely a bug in the constraints.

But it turns our your `P` matrix isn’t quite what you think it is: [Job Shop Explanations](http://jobshop.jjvh.nl/explanation.php).

`P[1, 2]` is the time to complete job `1` on machine `O[1, 2]`, not on machine `2`, which is what your constraints assume. You could probably change the constraints around, or you could just re-order the `P` matrix:

```julia
for i in 1:size(P, 1)
    P[i, :] .= P[i, sortperm(O[i, :])]
end

```

---

<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:** [April 3, 2023, 12:52pm UTC](https://discourse.julialang.org/t/job-shop-scheduling/96938/5 "2023-04-03T12:52:40Z")

</div>

Dear Oscar, thank you very much for your attention. I have changed the P matrix (following your suggestion). I have tested the test instance ft06 (as attached in the last message) and the tai01 ([Job Shop Instance](http://jobshop.jjvh.nl/instance.php?instance_id=84)). Now, both results are correct. Thanks again.