# Job Shop Scheduling Problem

Hello,

I want to solve a job shop scheduling problem. I got n Jobs i that have to be scheduled on m Machines k. 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. 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. 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 have the following code: I got 15 Jobs but I often just show the data for 2 Jobs so the code example is not so long. In my real code I got the correct indents.

#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 k in Machines for J in Operations), 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 k in Machines for J in Operations), name="6")

Model.optimize()

Any help is much appreciated!! Thanks in advance!!

Hanna

Please sign in to leave a comment.

## Comments

0 comments