Job shop scheduling

Specific Domains Optimization (Mathematical)
,
1

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, and my implementation is wrong.

Concerning this test instance:
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]])

2

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. 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

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.

1 Like
3

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:

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)
4

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, 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.

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:

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

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). Now, both results are correct. Thanks again.

1 Like