Job Shop Scheduling Problem: jobs are scheduled on the same machine at the same time

Question

I want to solve a job shop scheduling problem. I got $n$ Jobs that have to be scheduled on $k$ Machines. A Job $i$ has 2 or 3 Tasks $j$, and there is a known sequence of the Tasks of a Job. One Machine can only handle one Task at a time. A Job can only start at or after its Release date. Every Job has a Duedate. The goal is to minimize the tardiness of all Jobs.

I got a working model for my problem. Only the last two constraints (constraints 5 and 6) are not working properly (or maybe more constraints). They should ensure that only one task is scheduled on a machine at a time. But in reality, several Tasks are scheduled on the same machine at the same time.

I got 15 Jobs, but I show the data for 2 Jobs, so the code example is not too long. In my real code, I got the correct indents. I use Python with the solver Gurobi. I have the following code:

#Create model.
Model = gp.Model("Job_Shop_Scheduling")

#Number of Jobs i.
Jobs = range(1, 16)
#Number of Operations j.
NumofOperations = 3
Operations = range(1, NumofOperations+1)
#Number of Machines k.
NumofMachines = 5
Machines = range(1, NumofMachines+1)

#Processing Times pij.
P = { #(Job_ID, Task_ID): Processing time
(1, 1): 2, (1, 2): 2, (1, 3): 1,
(2, 1): 3, (2, 2): 2, (2, 3): 2,
}
Release = { # Job_ID : Release
1:2,
2:1,
}
Duedate = { # Job_ID : Duedate
1:3,
2:8,
}

#Predecessor is 1, if Task J form Job i follows Task j from the same job; 0 otherwise.
Predecessor = { #(Job_ID, Task_ID, TaskFollower_ID: 1 or 0
(1, 1, 1): 0, (1, 1, 2): 1, (1, 1, 3): 0,
(1, 2, 1): 0, (1, 2, 2): 0, (1, 2, 3): 1,
(1, 3, 1): 0, (1, 3, 2): 0, (1, 3, 3): 0,
(2, 1, 1): 0, (2, 1, 2): 1, (2, 1, 3): 0, 
(2, 2, 1): 0, (2, 2, 2): 0, (2, 2, 3): 1, 
(2, 3, 1): 0, (2, 3, 2): 0, (2, 3, 3): 0,
}

#L is a big number.
L = 100

#Completion of Job i.
Completion = {}
for i in Jobs:
  Completion[i] = Model.addVar(vtype=GRB.CONTINUOUS, lb = 0, name="Completion(%s)" % (i))
#Tardiness of Job i.
Tardy = {}
for i in Jobs:
  Tardy[i] = Model.addVar(vtype=GRB.CONTINUOUS, lb = 0, name="Tardy(%s)" % (i))

#X is 1 if Task J of Job I follows Task j of Job i on Machine k; 0 otherwise.
X = {}
for i in Jobs:
  for j in Operations:
    for I in Jobs:
      for J in Operations:
        for k in Machines:
          X[i,j,I,J,k] = Model.addVar(vtype=GRB.BINARY, name="X(%s,%s,%s,%s,%s)" % (i,j,I,J,k))
#Starting time of Job i.
S = {}
for i in Jobs:
  for j in Operations:
    S[i,j] = Model.addVar(vtype=GRB.CONTINUOUS, lb = 0, name="S(%s,%s)" % (i,j))

Model.setObjective(quicksum((Tardy[i]) for i in Jobs), sense=GRB.MINIMIZE)
#Constraints.
#1)
Model.addConstrs((Tardy[i] >= (Completion[i] - Duedate[i]) for i in Jobs), name="1")

#2)
Model.addConstrs((Completion[i] >= S[i,j] + P[i,j] for i in Jobs for j in Operations), name="2")

#3)
Model.addConstrs(((S[i, 1] >= Release[i])for i in Jobs), name="3")

#4)
Model.addConstrs(((S[i,j] + P[i, j]) * Predecessor[i, j, J] <= S[i, J]\
for i in Jobs for j in Operations for J in Operations), name="4")

#5)
Model.addConstrs(((S[i, j] + P[i, j] - (1 - X[i, j, I, J, k]) * L) <= S[I, J]\
 for I in Jobs for i in Jobs if i != I for J in Operations for j in Operations if j != J for k in Machines), name="5")

#6)
Model.addConstrs(((S[I, J] + P[I, J] - X[i, j, I, J, k] * L) <= S[i, j]\
 for I in Jobs for i in Jobs if i != I for J in Operations for j in Operations if j != J for k in Machines), name="6")

Model.optimize()

This model works, but some tasks are scheduled at the same time at one machine. How can I solve this problem?

Answer 1

Based on what you mentioned, you have two jobs with three operations for each. As you do not determine which processing time goes on the specific machine, I assume that each job is processed sequentially on the machines. For minimizing the tardiness of all jobs, one possible schedule is as follows:

(Solution with $C_{max} = 11$, $T_{max} = 4$ and $\sum{T_{i}} = 7$).

Please noted that, in the shopping schedule models like this, if all of the jobs do have a specific route, the problem can be reduced to the flow shop scheduling and it might be solved in less time than the job shop problem. I recommend you took a look at the following reference, $P89$:

• Applications of optimization with Xpress-MP