Context:
I am dealing with a kind of scheduling problem, in which I have a set of tasks and machines. All tasks must be assigned to machines (not necessary all of them). In addition to that, I must calculate the cost of transferring the product between two machines.
For starting, I based my problem in the nurses assignment: https://developers.google.com/optimization/scheduling/employee_scheduling
However, I do not know how to obtain the cost of changing machine, it means, take the material from one machine to another.
To consider the task assignment with the process sequence I established the binary variable X[w, o, j], where w is the machine, o is the operation and j is the position on the process plan.
For calculating the cost of changing machine I also established another binary variable T[w1, w2, j-1, j], that states if there is a material transition from one machine to another in two followed positions on the process plan.
Some code:
# Create the decision variabl
X = {}
for w in range(num_machines):
for p in range(num_operations):
for j in range(num_operations):
X[w, p, j] = model.NewBoolVar('X_{}_{}_{}'.format(w + 1, p + 1, j + 1))
T = {}
for w1 in range(num_machines):
for w2 in range(num_machines):
for j in range(1, num_operations):
#if w1 != w2:
# T[w1, w2] = model.NewBoolVar(f'T_{w1}_{w2}') # using f-string notation
T[w1, w2, j-1, j] = model.NewBoolVar('T_{}_{}_{}_{}'.format(w1 + 1, w2 + 1, j, j + 1))
B = model.NewBoolVar('B') # declaring an intermediate variable
I've tried to implement some constraints:
1) The number of transitions must be equal the number of operations -1
number_transitions = sum(
T[(w1, w2, j-1, j)]
for w1 in range(num_machines)
for w2 in range(num_machines)
for j in range(1, num_operations)
)
model.Add(number_transitions == num_operations - 1)
So to establish the relation between X and T I tried 2 different ways, but any of them worked.
1st way:
# Implementing B == [X1 + X2]
for w1 in all_machines:
for w2 in all_machines:
for p1 in all_operations:
for p2 in all_operations:
for j in range(1, num_operations):
model.Add(X[w1, p1, j-1] + X[w2, p2, j] == 2).OnlyEnforceIf(B)
model.Add(X[w1, p1, j-1] + X[w2, p2, j] != 2).OnlyEnforceIf(B.Not())
# Reinforcing the value of T
for w1 in all_machines:
for w2 in all_machines:
for j in range(1, num_operations):
model.Add(T[w1, w2, j-1, j] == 1).OnlyEnforceIf(B)
model.Add(T[w1, w2, j-1, j] == 0).OnlyEnforceIf(B.Not())
2nd way:
for p in all_operations:
for w1 in all_machines:
for w2 in all_machines:
for j in range(1, num_operations):
model.Add((X[w1, p, j-1] + X[w2, p, j]) == T[w1, w2, j-1, j] + 1)
In both of ways, when I run the code, it returns as result just solutions that do not do transitions between two machines, meaning that these constraints are not being read correctly.
I would like to know if there is a better way to solve this problem by establishing the relation between variables X and T.
I guess that it could be possible to solve like a TSP, but in my case, not all nodes are visited, but just nodes(machines) required to do a task.
Someone know how could I solve this problem? Or maybe do you have an example to send me?
I asked the same question here: https://stackoverflow.com/questions/58709914/tsp-problem-traveller-does-not-visit-all-nodes-google-or-tools
