1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – A.Omidi Mar 31 at 19:50
1
$\begingroup$

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:

enter image description here (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$:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.