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
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
Post is closed for comments.
Comments
1 comment