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

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

• Welcome to OR.SE. Do you try using a valid MP model that has been published in the academic/industry article? Is it possible to share it? As you mentioned in the code, you define $15$ jobs while actually you have two jobs with three operations for each that. Commented Mar 31, 2021 at 19:50

(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$$: